AtCoder Regular Contest 091
Updated:
Source codes
Solutions
C - Flip,Flip, and Flip……
$N \leq M$ として良い。$N, M \geq 2$ のとき、 $(N-2)(M-2)$ 。$N = M = 1$ のとき、 $1$ 。$N = 1$ 、 $M \geq 2$ のとき、 $N-2$ 。
D - Remainder Reminder
問題は $1 \leq a, b \leq N$ かつ $a \% b \geq K$ を充たす整数解 $(a, b)$ の個数を求めよということである。
$b$ を固定する。簡単のために $0 \leq a \leq N$ とし、 $K \geq 1$ とする。有限列 ${ a \% b }_{0 \leq a \leq N}$ は、 $0, 1, \dots, b-1$ が $p$ 回含まれており、かつ最後は $0, 1, \dots, r$ で終わっている。周期 $0, 1, \dots, b-1$ の中に $b - \min(b, K)$ 個 である。 $N = pb + r$ (商と余り) の関係があるので、終わりも $r - \min(r, K)$ であるとわかる。だからここは $O(1)$ で計算できる。最後は $K+1 \leq b \leq N$ で回せば良いので $O(N)$ である。また、 $K = 0$ のとき、答えは $N^2$ である。
ポイント
解説放送、 $b - \min(b, K)$ 個のところがスムーズだなーと思った。この質問を rng さんにしてくださった方は GJ だった。
E - LISDL
まず必要条件を書き下す。まず、 $N \geq A + B - 1$ である。その証明： LIS に含まれる元に赤、 LDS に青をつける。仮に $2$ つ以上の元 $a, b$ に両方の印がついたとすると $a < b$ かつ $a > b$ が成立することになる。これはおかしい。ゆえに両方に印がつく元は $1$ 個以下である。次に、 $N \leq AB$ である。各場所まででの LIS の長さを書き出してみる。例えば、 \[ 3, 6, 1, 2, 5, 4 \] であると、それぞれ \[ 1, 2, 1, 2, 3, 3 \] となる。同じ数字のついた元だけ並べてみると、そこは減少列になっていることになるなぜなら、増加している場所があるとすると、もはや後ろは同じ数字がつかないからである。
実は十分条件になっている。以下、この $2$ つの条件が揃っているときにどのように生成するかを議論する。まず $N = AB$ のときは、以下のように作るとよろしい。 $A = 4, B = 5, N = 20$ の時は、 \[ (17, 18, 19, 20), (13, 14, 15, 16), (9, 10, 11, 12), (5, 6, 7, 8), (1, 2, 3, 4). \] とする。 $N < AB$ の時は、「最初のカッコは全部のこす」「カッコの中は 1 つは残す」として削除していき座標圧縮する。
ポイント
私の解法を示しておく。まず $N \geq A + B - 1$ はすぐにわかった。問題は $N \leq AB$ の方で、こちらは時間かかった。全く手も足も出なかったので、実験するプログラムを書こうとした。つまり $O(N!)$ のやつで総当たり。そして $N = 2, 3, 4, 5, 6, 7, 8, 9$ までやってようやく $N \leq AB$ に気がつく。気づいた後は $N = AB$ の場合のやり方はすぐに思いついた。こちらは最初から座標圧縮をかけるつもりだった。その後 $N < AB$ も後ろを打ち切ればいいと思っていたがこれは WA であった。そこで、以下のように生成することにした。
本問題では整数はそもそも ll で扱うべきなので($AB$ がオーバーフロー)、 $M = 10^{17}$ とする。以下を $N$ 項作るまでやって打ち切る。
- 最初の $A$ 項は $M$ から $1$ を足していく。
- 次の $B-1$ 項は $-M$ から $1$ を引いていく。
- 次からは $0$ からスタートして $B-1$ 回ループを回し、その中で $A-1$ 回ループを回す。内側では $1$ を足していき、外側では $4A$ くらいの数字を引く。
$A + (B-1) + (A-1)(B-1) = AB \geq N$ より必ず途中で終わる。座標圧縮。
F - Strange Nim
解説放送
まず実験。 $K$ を固定して、手計算かプログラムで grundy 数を求めにいく。 すると、 \[ 0, 0, 1, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 5, 0, 8, 4, 9, 2, \dots \] となる。偶数番目だけみると、 \[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \dots \] となる。これはわかりやすい。奇数番目だと、 \[ 0, 0, 1, 2, 1, 3, 0, 4, 2, \dots \] である。これは元の数列と一致している。 $K = 3$ だと \[ 0, 0, 0, 1, 0, 1, 2, 0, 1, 3, 2, 0, 4, 1, 3, 5, \dots \] であり、類比的である。すなわち、 $g(A, K)$ は \[ g(A, K) = \begin{cases} A/K & (A\%K = 0) \\ g(A - 1 - A/K) & (\text{otherwise}) \end{cases} \] で定義される。 $A\%K =0$ の場合は簡単なので、 $A \mapsto A - 1 - A/K$ が $K$ の倍数になるまで繰り返す行為を簡略化するとよろしい。 $A/K = d$ と一定値である区間、すなわち $A \geq Kd$ の区間では \[ A \mapsto A - (d+1) \mapsto A - 2(d+1) \mapsto A - 3(d+1) \mapsto \dots \] となるので、等差数列で減っていくところを一気に飛ぶ(等差数列で減る区間を出るまで飛ぶ)ことを考察する。ここまで解説放送も editorial も終わっていて「？」となっていたので、以下じっくり議論する。
以降の解説
これらの数字の $K$ で割った余りはどうなっているかを考察しよう。だんだん減っていくはずである。仮に $A - x(d+1) = 0$ in $\mathbb{Z}/K\mathbb{Z}$ となる $x$ に「たどり着いた」とする。この場合は問答無用で答えは $d$ である。というのも、答えは $g(A - x(d+1), K) = (A-x(d+1))/K$ であるのだか、そもそも「$A/K = d$ と一定値である区間」で遷移していたのだから、そりゃ答えは $d$ のままである。したがってこの条件は $x$ の存在だけが重要なので、 $(A \% K) \% (d+1) = 0$ が条件である。
そうでない場合には、「余り」を「またぐ」ことになる。この際に何が起こるのかを考察する。またぐ直前の $A$ は $A - x(d+1)$ の形であるが、別の形に書き換える。こいつを $K$ で割った余りは $(A \% K) \% (d+1)$ に他ならない。「またぐ直前」なのだから。では商はどうか？ これは $d$ である。「$A/K = d$ と一定値である区間」で遷移していたのだから。だから、 $A - x(d+1)$ と書くのではなく $dK + (A \% K) \% (d+1)$ と書くことにする。この値から $(d+1)$ を引くと何が起こるのかを考察しているのだった。 $(A \% K) \% (d+1) < (d+1)$ であるので、必ず $dK$ 未満の数になっている。この値を $K$ で割ると(整数の割り算)、 $d$ 未満になる。これは何を意味しているかというと「$A/K = d$ と一定値である区間、すなわち $A \geq Kd$ の区間」を「外れた」ことを意味している。しかも直前までは入っていたのだから、まさにこれが「等差数列で減っていくところを一気に飛ぶこと」に相当しているのである。だから $g(dK + (A \% K) \% (d+1) - (d+1), K)$ に遷移すればよろしいということになる。
計算量
計算量は、ずっと上の遷移をくりかえすとすると遷移の回数は最大でも $A/K$ 回である。この遷移は $A$ が大きい時はダイナミックに行える。そのとき $A$ の値がだいたい $(1 - 1/K)$ 倍になるので、だいたい $O(K \log A)$ くらい。どちらで数えてもそこそこいやなのは $K \approx \sqrt{A}$ の場合なので $O(\sqrt{A} \log A)$ 回くらいであるというのが解説放送。より正確に議論すると $O(\sqrt{A})$ らしい。だからこれを $N$ 回やっても間に合う。
ポイント
時間内には解けないだろう。
Others
提出時刻を見てもらえればわかる通り、 700 点は得られたはずだった。敗因を記録しておく。
- まず自動提出機が Chrome の version update により相対的に古くなってしまった。これにより自動提出ができなかった。
- ここに書いてある通りだった。
- 直接の原因ではないが、
gem updateをサボっていたのがよくなかった。 - 本番前に動くかどうかチェックしておくべきだった。
- (調べた限り、
selenium-webdriverでは Safari は profile の指定ができない、そもそもないようなので、 Chrome を使い続けるしかない)
- 次に睡眠時間がずれてしまった。
- 昨日素直に睡眠薬を飲んでおくべきだった。起きたのは 20 時だった。
- 目覚ましで起きたから体調は良くなかった。
- 最後に、途中で歯磨きをしてしまった。
- 適切な分量のご飯を用意しておくべきだった。
- コンテスト前は、万全の体制で座るべきだ。
コンテストに人生を賭けるつもりはない。しかし、状態に最善を尽くすべきだ。プロ棋士だと対局前に睡眠時間も整え、座布団の様子もチェックし、食べ物も飲み物も揃える。そういう基本的なところを怠っていた結果 700 点を失うということになったのだと思う。猛省している。