$\mathrm{Nim}_K$ のお気持ち証明メモ
経緯
学校の数学テーマ学習で、なんやかんやあって $\mathrm{Nim}_K$ についての研究(?)をすることになりました。
班員 $1$ が先行研究を見つけてきて、班員 $2$ であるところの Forested が証明込みの この記事 を持ってきてくれたのですが、証明の解読に時間がかかりました(結局解読に成功した Forested に教えてもらいました)。
あとで思い出したときなどのために、メモ的なものとしてお気持ちを記しておきます。直感的な理解のために利用してください。厳密性は全く気にしません。
$\mathrm{Nim}_K$ の概要
$\mathrm{Nim}_K$ とは、以下のようなルールで行われる二人零和有限確定完全情報ゲームです:
- 石の山を $N$ 個用意する。各山の石の個数を順に $A_1,A_2,\ldots,A_N$ とする。
- 自身の手番において、各プレイヤーは以下のような操作を行う。
- 山を $1$ 個以上 $K$ 個以下 任意に選択する。
- 選んだそれぞれの山について、$1$ 個以上任意の個数取る。
- 最後の石を取った方の勝ちである。
例えば、一般的な Nim は、$\mathrm{Nim}_1$ に相当します。
さて、このゲームの勝敗判定を高速に行いたいです。何か良い方法はないものでしょうか。一般的な Nim は、XOR を利用していましたが……
$\mathrm{Nim}_K$ の勝敗判定法
天下り的にも程がありますが、結論から言えば、以下のような方法で勝敗を判定することが出来ます:
- まず、$A_1,A_2,\ldots,A_N$ を二進数(というか、$01$ 列)に変換したものを $B_1,B_2,\ldots,B_N$ とする。
- これを、桁ごとに足し合わせる。$10$ 以上の値が出てきても、ひとまず無視して、数列として扱うことにする。この数列を(上の桁から順に見て) $S_1,S_2,\ldots,S_d$ と置く($d$ は $B$ の最大桁数)。
- 数列 $S'$ を、$S'=(S_1 \bmod (K+1), S_2 \bmod (K+1), \ldots, S_d \bmod (K+1))$ と定義する($a \bmod b$ は $a$ を $b$ で割ったあまり)。
- $S'=(0,0,\ldots,0)$ であれば、後手必勝。それ以外は、先手必勝。
以下、これを示すことを目標とします。ここからがお気持ちパートです。以下では、$S'=(0,0,\ldots,0)$ となるような盤面を「特別な盤面」と呼ぶことにします。
$\mathrm{Nim}_K$ の勝敗判定法の証明
ちょっとした言い換え
めんどくさいので、証明することをすり替えます。示したいことは、以下の二つに分けられます:
- 特別な盤面に対して $1$ 回どのような操作を行っても、特別でない盤面しか作ることができない。
- 特別でない盤面に $1$ 回適切に操作を行えば、必ず特別な盤面を作ることができる。
また、操作は各山について分離させて考えるものとします。つまり最終的に、示したいことはこう書けます:
- 特別な盤面の山を再び特別な盤面にするには、必ず $K+1$ 個以上の山の石を取り除く必要がある。
- 特別でない盤面の $K$ 個以下の山の石を適切に取り除くことで、特別な盤面にできる。
以下、これを示すことを目標とします。
本題
「特別でない盤面の $K$ 個以下の山の石を適切に取り除くことで、特別な盤面にできる」ことの証明
先ほど用意した $S'$ について、$S'=(S'_1,S'_2,\ldots,S'_d)$ とします。
出来るだけ少ない数の山の石を取ることで、$S'$ を特別にしたいです。
前から順に、$S'_i$ の値を $0$ にすることを目指します。
$S'_i \neq 0$ なる最小の $i$ を取ります。当然のことですが、$A_1,A_2,\ldots,A_N$ の内には、上から $i$ 番目の bit が立っている数が少なくとも $S'_i$ 個あります。
これら $S'_i$ 個を選んで、とりあえずそれぞれ石の個数を「上から $i$ 番目の bit が立たない最小の数」 に置き換えてみましょう(これは暫定的なもので、あとからさらに数を減らすこともあります)。
すると、以下のようなことが分かります:
- 選んだ $S'_i$ 個の山の石の数について、「$i+1$ 番目以降の bit を立てるかどうか」がこれ以降自由に決められる。
そして、ここで $S'$ を再計算すると、$S'_i \neq 0$ なる最小の $i$ の値は増加します。
これに、今行ったのと同様の操作を行うことを考えましょう。
$S'_i \neq 0$ なる最小の $i$ を取って、$S'_i = 0$ とすることを目指します。
ここで、先ほどと異なる、非常に重要なポイントがあります。
「既に選んで少しでも石取った山については、今見ている桁を自由に $1$ 減らせる」ということです。
ですから、既に石の数を変更した山を優先しながら今見ている桁の bit を減らすことで、「節約」をすることができます。
この事実から、今までに石を取ったことのある山の数を $x$ として、ある $i$ について $S'_i$ を $0$ にしたとき、$x = \max(x,S'_i)$ のように更新できることが分かります。
よって、結局、すべての $S'_i$ を $0$ とするために必要な「石を取る山の数」は、最小で $\max(S')$ 個に抑えられることが分かりました。
定義より、$S'_i \leq K \ (1 \leq i \leq d)$ ですから、特別でない盤面は、$K$ 回以下の操作で特別な盤面に作り替えられることが示せました。
「特別な盤面の山を再び特別な盤面にするには、必ず $K+1$ 個以上の山の石を取り除く必要がある」の証明
正直さっきと同じなのであまり説明は必要ないと思います。
一言で言うなら、「どこかしらの桁は $\bmod (K+1)$ で一周しなきゃいけないので、最低でも $K+1$ 回操作が必要だよね」的な感じです。
おわり
この判定法思いついた人のエスパー力すげーな、って思いました
$2$ 進数を桁ごとに足して $\bmod (K+1)$ をとるとか直感的に嫌じゃないですか?
おまけ
うにむく
ゲーム問題の Um_nik、Unim_k
— NatsubiSogan (@NatsubiSogan) 2022年3月30日
Um_nik さん、普通にコンテストに出てますが身の安全は確保できたのでしょうか
yukicoder で単独コンテストをやった話
前回
(前回よりも作問の腕は上がっている……はず)
作った問題の一覧
これまでの傾向
数え上げ: 5
構築: 3
その他数学: 1
最適化: 1
はじめに(ここから本題)
yukicoder contest 326 で単独 writer を務めさせていただきました、NatsubiSogan です。ご参加ありがとうございました。
単独回はいつかやってみたいなあと思っていたので、非常に嬉しいです。お楽しみいただけたのであれば、こちらとしても嬉しい限りです。
テスターを引き受けてくださった SugSugar さん、Cyanmond さん、first_vil さん、Forested さん、nok0 さん ならびに、全体テスターとして問題文や難易度のチェックをしてくださった penguinman さんに、心より感謝申し上げます。本当にありがとうございました。
以下、ポエムです。読む価値はないので、読みたいところを目次からお読みください。
目次
コンテスト開催まで
まず、コンテスト開催までの振り返りをします。
単独回を開きたい!(技術室奥コン終了後)
前々から思ってはいましたが、本格的に単独回のための作問を始めたのは技術室奥コンが終わった後(つまり、9 月以降)です。
問題を作ろう!(9 月~10 月初頭 / 11 月~)
あの手この手で問題を作りました。
前回(すべて「問題設定から生やして解いた」)とは作問方法を変えました。具体的には、設定から生やすのに加えて、解法から生やす、「このアルゴリズムをもとに考察を進める問題が作れないか?」と考える、いい性質を見つけたのでどう問うか考える…などの手法を取りました。
没になったやつもいくつかあります。
10 月の間作問に時間が取れていないのは、文化祭準備のためです。(本校生には、私含め文化祭に命を懸けているような人が多くいるので、これは仕方ないです)
準備!(生え次第)
社畜なので 正直この作業はかなり楽しいです。
- 分かりやすそうでよさげな問題文(制約などを含めて)を書き、
- 想定解を書いて、提出し、
- ケースと想定出力を生成し、
- バリデータを書き、入力をチェックする
これだけなので、頑張れば一問あたり 30 分でできました。
問題文についてですが、基本的には、自分の読みやすいように書けば問題ないと思います。ただ、それでも分かりづらくなってしまう場合はあるので、いったん頭を真っ新にして問題文を読んでみる、テスターさんの意見を仰ぐ、といったプロセスは必要不可欠です。
想定解はバグらせないようにしましょう(今回、一度やらかしました。Forested、ごめん)
ケース生成に関して、今回はだいぶサボってしまいました。具体的には、
- ケース生成が楽な数え上げを置く
- 面倒そうなやつは、複数ケース形式にして誤魔化す
- あとはランダム
みたいな感じです。大体はこれで何とかなったんですが、Yes/No とか最適化だとちゃんと作らないとまずいことになると思います。強いケースの作り方、誰か教えてくれ~
バリデーションについては、yukicoder だと testlib.h が簡単に使えるので、積極的に利用してきましょう。入力チェックをするだけなら仕様もだいぶ簡単です。
あと、難易度は過大評価気味の方がいいです。(過去に何度も過小評価でやらかしています)
テスターさんを呼ぼう!(準備終了次第)
今回は、準備が終わり次第テスターさんを募集しました。
基本的には、Twitter で「募集します!」と呟けば、(yukicoder 公式さんもリツイートしてくれるので)数日以内には見つかると思います。yukicoder Slack で募集するのもアリです。
テスターさんには本当にお世話になりました。A では、ケースが弱かったのを修正してもらいました。
全体テスターさんを呼ぼう!(12 月末 / 問題が出揃った後)
出題する問題が出揃ったところで、前項と同じように、全体テスターさんを募集しました。
全体テスターの penguinman さんにも色々なアドバイスを頂きました。具体的には、全体テスターさんの指摘で C, E の難易度が 0.5 上がり、C の問題文の赤字部分を強調することになりました。
テスターさんの指摘は、受け入れた方がクオリティの向上につながると思います。
問題ごとの講評など
A: Summer Day (★1)
tester: SugSugar さん
FA: SSRS さん
私は夏日です。(それだけ)
暑すぎる夏って嫌ですよね。
一問目には簡単なのを置いた方がいいと思っているので、本当に簡単なのを作りました。
さっきも言ったんですが、めちゃくちゃ適当にケースを作ったせいで、テスターさんに「ケースめちゃくちゃ弱いと思います」みたいなことを言われてしまいました。すぐさん、ごめん……
B: Random XOR (★2)
tester: Cyanmond さん
FA: heno239 さん
数え上げ / 期待値 枠が一つはないとアイデンティティを喪失しそうだったので入れました。
「夏日さんコンだし一個は期待値が出そう」みたいな言及があったんですが、はい。
XOR を見て「ビットごとに考える」という方針に走ってみるのは割と典型だと思います。二項係数の公式を知らないと辛そうです。そういう意味では、割と「典型+知識」に寄っている問題かも……
C: Segment Game (★2.5)
tester: first_vil さん
FA: 沙耶花 さん
ゲームです。初めて出しました。複数テストケースで、生成をサボりました
とは言っても、慣れている人からしたらだいぶ典型寄りの問題だと思います。そもそもこの問題自体、「対称性に注目する」という手法に感動して、解法から作った問題なので……
Nim の必勝法の話が分かっていれば発想は難しくない……かも?
D: Range Score Query for Bracket Sequence (★3)
tester: Forested さん
FA: hitonanode さん
クエリ処理です。これも初めて出しました。「NatsubiSogan ってクエリとか出す writer だっけ……」と驚かれた方もいるかもしれません。
括弧列をいじっていたら生えました。「操作回数」をうまく特徴づけてやるのが本質で、あとは実装を頑張るだけです(ここは典型)。
幅を持ったものを数えるので、実装が(セット内の他の問題と比較して)重くなってしまっていますが、お許しください。
想定解をバグらせたのはこれです。些細なミスではあったんですが、Forested、ごめん……(2 回目)
E: Remainder of Sum (★3.5)
tester: nok0 さん
FA: hitonanode さん
最適化です。出すのは二回目ですが今回は $\mathrm{O}(1)$ です。最適化系って生やすの難しくないですか?
「特殊なグラフの最小全域木を求める問題が作りたいなあ」と思って、まず最小全域木の問題として作ったものを、適当な操作に言い換えました。ちょっとしたカムフラージュなので一瞬で見破った方もそれなりにいそうですね……
基本的にはクラスカル法の要領で考察を進めていくだけなんですが、割と頭が壊れます。解説はかなりごちゃごちゃしているので、とりあえずいろんなパターンで実験をしてみてください。言いたいことが伝わる……かもしれません。
頭が壊れるので、こどふぉにありそうな算数パズルみたいな感触になってしまいました。楽しいとは思うんですが、もうちょっと後味の悪くない最適化の問題を生やしたいです……
F: Intersection of LIS (★3.5)
tester: nok0 さん
FA: tute7627 さん
割と特殊な見た目の問題です。実は、このセットの中で一番最初に作った問題にして、一番の自信作です。これを出すために他を作ったまであります(流石にない)
完全に問題設定から生やしました。「すべての○○に含まれる要素を列挙せよ」みたいな問題を作りたいとは前々から思っていたので、かなり綺麗な形になって嬉しい限りです。
「取り得る最小値と最大値を求め、比較する」というのは、かなりの発想力を要求すると思います。私自身、この解法が降ってくるまでに数日間を要したので……
あと、LIS の復元を書いたことがない人がそれなりにいるんじゃないかなあと思いました。頑張ってググると出てくるので、覚えておいて損はないと思います(説明箒🧹)
penguinman さんに「Yutori に似ている」という指摘を受け、「たしかに」となりました。
このテクって意外と典型だったりするんですかね……
おわりに
- 構築がねーじゃん!→ ごめんなさい、普通に作れませんでした
- 過去の自分、ごめん
- 4 問目までの問題名の頭文字を
SSRS
にする案があったんですが、やめました。SSRS さん、本当にごめんなさい - ごめんなさいしか言ってない
- 次回はパ研合宿のコンテストでお会いすることになる……かもしれません
JOI 2021/2022 二次予選 参加記
動機
ここ で「書くぜ」って言ったのに書いていなかったので
本番前
多分だらけてました、あと Twitter にいました(いつものこと)
一年に数回しかできない「じょい」をツイートし、コンテストが始まりました。
本番中
00:00 A を開く。
問題文が「stack 使え」と叫んでいるので、数十秒後くらいから書き始める。
01:13 A を AC。B を開く。
12:03 親の顔より見たグリッド上の BFS を書いて、B を AC。C を開く。
ちょっと考えても全然分からないので D に行く(自明部分点は後で取ることにした)。
愚直な DP が生えたので書く。
40:51 書き上げて、D の部分点(51 点)を取る。
DP 配列を出力して、にらめっこすると、どう考えても無駄なところがあるので、削ろうとする。
ここでめちゃくちゃ時間を食う。
111:29 バグを何度も生やしつつ、D の満点を取る(遅すぎる)。DP めちゃくちゃ苦手なのでこれは仕方ない。思考過程は ここ に書いた。
もう一度 C を開いて、親の顔より見た bit 全探索を書き始める。
120:24 C の部分点(26 点)を取る。もっと親の全探索見ろ
よく見ると C の小課題 1 は約数列挙で行けるので、書く。
123:10 書き終えて、場合分けして、小課題 1(12 点)も取る。合計 38 点。
満点解は分かりそうになかったので、いったん放棄🧹して E の部分点を取りに行く。
小課題 1, 2 ともに一瞬で解法が生えたので、書く。
143:49 ちょっとバグらせてしまったが、なんとか両方の小課題を通して、16 点を得る。
それ以降は一向に分からないし、見るからにヤバそうだったので、C の満点解を取りに行くことを考える。
分からん、なんだこれ、と唸っていると、小課題 1($H=1$ の場合)の約数列挙する方針をうまく二次元に落とし込んでやればいいんじゃね?と思いつく(詳細は ここ)。
鬼のような実装量になりそうだとは思ったが、とにかく書く。
166:03 約 1700 byte を書き上げ、C で満点を獲得。ここでようやく勝ちを確信する。
その後 E も考えてみたが、全く分からず。難しすぎる。
本番後
「流石に通っただろ!w」と安心していたが、思っていた以上に満点と同点が多くて若干怖かった。
E の解説を見たら「Undo 可能 Union-Find」みたいな文字列が見えて、泣きながらそっ閉じした。
非公式難易度表の投票で、「C は難易度 5」と主張している人がいて泣いてしまった。流石にそんなことはないと思います
数日後
A ランクでした。(本選 160 人なこともあってボーダーがだいぶ低いですね)
まあ、416 点取っていれば流石に 80 人でも通っていたとは思いますが…
自分含め、同期 6 人が本選行きらしいです(すごい)。本名特定は「出来るもんならやってみてください」という感じです。
頑張ります(いい加減まともに C++ を書けるようになりたい、というかならないといけない)。
体感難易度
3 / 5 / 8 / 8 / (不明)
最終戦績
A: 100
B: 100
C: 100
D: 100
E: 16
合計: 416 / 500
参考(去年の)
おわりに
足跡、残してぇ~~
20211213 JOI 2021/2022 二次予選 D 「飴 2 (Candies 2)」
なぜ
正直書くかどうかは迷ったんですが(公式解説とほぼ同じなので)、思考過程だけでも残しておこうと思ったので書きました
DP は大の苦手なので、後から「過去の自分、どんな天才をしたらこれを思いつけたんだ……?」みたいに何もわからなくなりそう
問題ページ
小課題 $3$
$3$ 次元 DP をしろと制約が訴えかけてくるので DP を組みます。
$\mathrm{dp}[i][j][k]:=i$ 番目まで見て、最後に取った飴が $j$、最後から $2$ 番目に取ったのが $k$ のときのおいしさの合計の最大値
とします。便宜上、$j$ または $k$ が $0$ であるときは、それをまだ取っていないことを指すことにします。
配る DP 的な感じで書くと、
$$ \mathrm{dp}[i + 1][i + 1][j] = \max(\mathrm{dp}[i + 1][i + 1][j], \mathrm{dp}[i][j][k] + a[i]) $$
$$ \mathrm{dp}[j][k] = \max(\mathrm{dp}[i + 1][j][k], \mathrm{dp}[i][j][k]) $$
みたいな遷移が出来上がります。
満点解法
ここで、DP テーブルを出力させてみました。すると、こんなものが出てきました。
直感します。「$i$ の情報要らなくね?」
ということで DP を組みなおします。
$\mathrm{dp}[i][j]:=$ 最後に取った飴が $i$、最後から $2$ 番目に取ったのが $j$ のときのおいしさの合計の最大値
とします。今度は貰う DP で考えてみます。
いま、$\mathrm{dp}[i][j]$ を更新しようとしているとします。$i$ 番目の飴を取るとき注目すべきは、$\mathrm{dp}[j][*]$ です。$i$ との距離が $K$ 以上である必要があるので、$\mathrm{dp}[j][i-K]$ 以左からしか遷移できません。よって、
$$ \mathrm{dp}[i][j] = \max_{k=0}^{\max(0,i-K)} \mathrm{dp}[j][k] + a[i] $$
これは愚直にやるとまだ $\Theta(N^3)$ かかってキツいですが、DP テーブルの累積 max を取ってあげると高速に処理できます。
よって、この問題を $\Theta(N^2)$ で解くことが出来ました。
AC コード
感想
DP が大の苦手だったんですが、DP テーブルとにらめっこしていたら解けて嬉しい(添え字ガチャに成功)
難易度 7 はあるし、あっとこなら青 diff はあると思います(主張)
おわりに
C, D をどちらも通せたのでよかった……と思ったら 416 点が多すぎた
A ランクの基準点が出たら参加記も書きます
JOI 2021/2022 二次予選 C 「国土分割 (Land Division)」
問題ページ
私が取った解法
$H=1$ の場合(小課題 $1$)
この場合は簡単です。
$S=\displaystyle \sum_{i=1}^{W} A_{i}$ として、$S$ の約数 $d$ を列挙したうえで、$\displaystyle \frac{S}{d}$ 個に分割出来るか判定すればよいです。これは、左から貪欲に取っていけばできます。
一般の場合
小課題 $1$ の解法を応用することを考えます。
$i$ 行目の要素の総和を $R_i$、$j$ 列目の要素の和を $C_j$ とします。また、$S=\displaystyle \sum_{i=1}^{H} \sum_{j=1}^{W} A_{i,j}$ とおきます。
$R, C$ それぞれについて、$H=1$ の時の手法を適用します。すると、「縦方向に入れて大丈夫な切れ込みの組み合わせ」と「横方向に入れて大丈夫な切れ込みの組合せ」が列挙できます。
よって、縦方向と横方向のそれぞれから切り方を $1$ つずつ取ってきて、全通りについて「和が全て等しいか」を判定すればよいです。これは頑張ればできます(説明箒🧹)。
計算量は、
$n$ 以下の整数の約数の個数のうち最大のものを $d(n)$ として、$O(\sqrt{S} + d(S) HW)$ となります。$50 \times 50 \times 100000 = 250000000$ 以下で最大の高度合成数は $245044800245044800$ で、その約数の個数は $1008$ です。よって、計算回数は最大でも $2.5 \times 10^{9}$ 回程度であることが分かりました。
あれ?
助けてください
実際は $H=1$ の時の答えがそんなに大きくならないので爆速で通ってると思うんですが、どうやったらうまく抑えられるか分かりませんでした
助けてください
追記
「$d$ 個分割する方法は高々 $1$ つで、$d$ の取り得る値は $1$ から $W$(ないし $H$)なので結局 $H^2 W^2$ では?」みたいな指摘を受けました ありがとうございます 僕がバカでした
AC コード
感想
難しすぎる、難易度 7 は最低でもある 8 でもいい でもパンケーキほどではないし……うーん
体感的には低めの青 diff くらい?
おわりに
D 問題についても書くかは未定です(こっちは解法が想定と異なったから書いていますが、D は想定とそう変わら無さそうなので)
yukicoder で共同コンテストをやった話
はじめに
yukicoder contest 297 で aspi(@aspirator_) とコンテストを開きました。
実は同校同期の 6 人(NatsubiSogan, aspi, AndrewK, Forested, kozy, seven_three)での共同作問だったのですが、原案として使うことになったのは我々 2 人のものだけでした。考察・準備等の一部は Writer 以外の 4 人にも協力してもらいました。
★3.5 以上の問題がなかなか生えずずっと唸っていたのですが、今回このようにしてコンテストを開催することが出来、嬉しい限りです。(aspi のおかげです)
以下ポエムです。読む価値はありません。
振り返り
原案
すべて設定から生やしました。解法を指定して面白い問題を作れるほどの実力はありません…
数え上げと構築しかないのも恐らくそのせいです(デ/ア 問題は…作れない!)
どの問題もそこそこ綺麗にまとまるようになっていますが、恐らくたまたまです(まとまらない問題を解けていないだけかもしれませんが)
準備
まあまあ楽しいので、A~G のケース生成、解説執筆などはほとんど私がやっています。
特に語ることはないですが、Validation における testlib.h の使い方をある程度心得たのは、かなりの収穫という感じです。制約違反や、末尾に余分な空白がある、などの不備はなかったので、よかった。
本番
祈るような思いでコンテストページを眺めていました。
全問題、順当な時間で FA が出て一安心していたのですが、その後逆転が発生したり、A と B の崖がすごいことになったり……と大変でした。
Clar は全体で一件のみでした。H の「単調増加」についての質問でしたが、$a_1,a_2,\cdots,a_N$ が相異なるというのは問題文の方にも書いておいた方がよかったな……と反省しています。
それぞれの問題について(Natsubi 担当分)
B: Simple Combinatorics (★1.5 -> ★2.5)
ご め ん な さ い
適当な設定を考えていたら生えた問題です。
「Simple という文字列だけで嫌な予感がしてしまいますが、実際は簡単枠ですね、AtCoder で出たら茶 diff 下位かな」……と思っていたらかなりの虐殺問になっていました。やっぱり Simple Math の呪いかな……(いいえ)
aspi は「これが 1.5 はヤバいだろ」と最後まで主張していたので、本当にごめんなさい
主客転倒入門の問題みたいな感じがあります(本当か?)
自戒も込めてですが、自作問の考察過程で主客転倒に気づくと、そこから問題が超自明にしか見えなくなるので、気を付けましょう。
C: Diversity (★2)
塾で鳩ノ巣原理の話題が出てきて、「グラフの次数の種類数は頂点数とは一致し得ない」みたいなのを示す問題を出されたので、「じゃあ種類数最大のグラフを構築させようかな~」みたいに考えていたら、出来ました。
かなりの有名事実だとは思うんですが、具体的な構築方法まで言及しているものは見つからなかったので出した、という感じです(まあ知ってたら考察をだいぶスキップ出来るんですが)
D: Zigzag Sum (★2.5)
ふと、ジグザグを数え上げてみたいという衝動に駆られました。
「こんなん数えられるか!NP 困難だろ」みたいな見た目をしているけれど、こういった総和計算になるとめちゃくちゃ綺麗にまとまる、みたいなやつです。
数え上げ問題の答えが綺麗な二項係数の式に落とし込めた時の喜びを共有するための問題です。fav が 5 ついているので少しよかった。
若干発想が難しそうなので、★2.5 ということになっています。
Wolfram に投げて通した人が一定数いたみたいで、そこはかなり反省です。(こっちで確認したときは出てこなかったはずなんですが……)
Forested が(なぜか)解けなかったため、★3.5 ということになりかけたヤバイ過去を持ちます。(もしあのまま出してたらこの問題まで大炎上していた……)
G: +/- Tree (★3)
元ネタ(?)は +/- Rectangle です
Forested が天才をして、いくつかのパターンでの構築方法を示してくれましたが、その他の場合の構成/証明が出来ず、長いこと作問サーバーに眠っていました。
その後どうやっても証明が出来なかったため、そのままテスターさんを募集することになりました。テスターの nok0 さんには感謝してもしきれません…(本当にありがとうございます)
非想定がたくさん出てきて驚いたんですが、その中に嘘解法もいくつか紛れ込んでいたみたいです(!?)どなたか強いケースの作り方を教えてください……(今回に関しては、小さいケースを大量に入れておけばよかったみたいですが)
それぞれの問題について(aspi 担当分)
A: Party Location (★1)
1 問目なので簡単です。比を取る嘘解法を誘発するためにサンプルが意地悪になっているみたいです。意地悪すぎ。何人か引っかかっていて、aspi が喜んでいました(えぇ……)
E: Playing Musical Chairs Alone (★2.5)
典型だけど難しいだろ……と思っていたらめちゃくちゃ通されました。D より遥かに難しいと思っていました。どうしてこんなことに。
「行列累乗を ★2.5 で出していいのか」で割と議論が起こりました。結果的に出しちゃってますが、流石にこのくらいが妥当かなという感じの結果になりました。
$K$ の制約は「行列累乗を制約エスパーされたくない」という aspi の意思によるものです。
制約、かなりのところまで上げられるみたいです。びっくり(解法をちゃんと理解していないので、誰かブログに書いてくれないかな……などと)
E、N<=1e5、K<=1e9で解けるね
— PCT (@PCTprobability) 2021年5月28日
F:Unfairness (★2.5)
このセットの aspi 問の中で一番面白いと思います。
ナップサック問題への帰着、天才的過ぎませんか?という感じが。aspi と得意分野が違いすぎる…
貪欲法的考察をベースにしているため、正当性がだいぶ不安でしたが、本人がちゃんと証明してくれたので、感謝です。
H:Upward Mobility (★4)
なんですかこれ?笑
私の理解が及ぶ領域ではありません。全然分かりません。なんですかこれ?(2 回目)
全体 tester の Nachia さんがすごい解法を編み出していました(100ms 切るとは……)。
意味が分からないので手も一切付けていません。嗚呼恐ろしや。世界の闇の部分を垣間見ました。
今年の JOI 春で既出だったらしいです(完全に想定外でした)が、彼はこれを春合宿前に作問していたので、もしかしたら爆破できたってことも……(いいえ)
セット全体について
6 問目くらいまでは標準的な ABC と同じかそれより簡単くらいの水準だと思っていました(過去形)
diff だけ見ると ARC でもいいかもというレベルですね、どうして……
B が想像以上に虐殺問になってて、本当にごめんなさい
G がけっこう重い枠です。H はとにかくめちゃくちゃ重いと思います。
ちなみに 8 問中 6 問が入力定数個なんですよね、な~んでだ?
入力定数個が全てを解決する
— NatsubiSogan (@NatsubiSogan) 2021年5月4日
おわりに
いかがでしたでしょうか。(ブログ定型文)
お楽しみいただけたのならば嬉しい限りです。
致命的な不備こそなかったものの、反省点がかなり残るコンテストとなってしまいました。
腕を上げて、必ず帰ってきます。とりあえず、次回は 技術室奥プロコン #6 でお会いしましょう。
ご参加下さった皆さん、そして tester の皆さん、本当にありがとうございました!
おまけ
これになってほしい
すべて典型の競プロ、嫌すぎる やっぱり数え上げと構築をだな
— 私は自作問の難易度評価をバグらせました (@NatsubiSogan) 2021年5月21日
AtCoder水になっている場合となっていない場合があるぞい 2
色変記事 Advent Calendar で色変宣言をしておいて、見事に失敗し、クソダサい記事を書いた NatsubiSogan(AtCoder水になっている場合となっていない場合があるぞい - 夏日・真夏日・猛暑日)。 彼は今度こそ水コーダーになれたのでしょうか…?
なれたんですか?
なれました!!!!!
かなり嬉しいです。これからも頑張っていきたいと思っています
この先、見る価値のない話が続くので、読み飛ばすことを推奨します
緑で半年くらい停滞した話
レート推移を見てわかる通り、緑色で半年くらい停滞していました
原因はだいたいARCで激冷えを重ねたことなんですが、正直かなり辛かったです
AtCoderの問題を1500問以上解いてもレートは上がる気配すらなく、毎週のように「お前AtCoder向いてないからやめろよw」みたいに言われているように感じ、周囲の人々がどんどん水以上になっていくのを見上げて…といった感じです
色変記事の「水色になるまでにやったこと」ももはや何の参考にもならず、行き止まっていました
(非常によくないんですが、「なんで私より精進していないこの人のレートが私より高いのか」みたいな感情も、正直ありました)
それでも、こうして水コーダーになることが出来ました!ということで、「水コーダーへの最短経路を紹介!私が水色になるまでにやったこと・精進の方法など」をまとめていきたいと思い
ません!!!
結局何が言いたいのかというと
- メンタルが死ぬとかなりまずいです
- 他人と比較しすぎるとメンタルが死にますが、停滞しているとどうしても比べてしまいます これってどうすればいいんでしょうか…私にはわかりません(少なくとも、わざわざすることはないと思います)
- 「これは履修しておいた方がいい」みたいな意見はたぶん聞いた方がいいですが、「これさえやれば〇色には簡単になれると思います」みたいな主張は無視しましょう 主にメンタル面で死にます(「簡単になれる」って言われてるのに私は…みたいな思考に陥ってしまうので)
- この記事も「こうすれば水色になれる」「水色になるまでにやったこと」とかは書いてません 参考にはしないでください
- 「停滞しても必ず努力は報われる!」みたいな無責任なことを言うことはできません 1か月前の私がそれを言われたとしてもおそらく信じないと思います とは言っても、挑戦を続けてみるだけの価値はあると思います
色変記事なんてものあてにしてはいけません
今後の話・まとめ
もちろん、次に目指すのは青色です
とはいっても、やはり私は今後も停滞し続けると思います なんならまた緑コーダーに戻ってしまうかもしれません こんな人の色変記事見る価値なんてありません もっと強い人の色変記事を読みましょう