| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | |
| 結果 | AC | AC | AC | AC | AC |
全体感想
5問正解で、76位。
RE, WA, TLE で3ペナルティ。これはちょっとずつ反省ポイント。
Eがノート上で解けたのは、残り12分時点でした。そこから実装して残り2分でAC。
あと1箇所計算式をミスしていたら、バグ取り切れずタイムアップしていたでしょうｗ
分かったぶんがきちんと点数に反映できると、後悔が少ないですね。
Fも、実例構成すれば終わりで実装力は要らなさそうだったので30分以上考えたけど解けず。
全体でも正解者が7人の難問だったようです。
問題B – Picking Up
コスト1節約できる回数を最大化するゲーム。
$(p,q)$ を選ぶと可能性がある節約は全部実現できる。
よって、$(p,q)$が差となっている2点を数えればよい。
逆にいうと、2点の差$(p,q)$の出現回数を集計して最頻値をとる。
出現回数の集計はCounterあるいはdefaultdictあたりで書くのが簡単でしょうか。（参考：■）
出現回数の最大値を取るところで、$N=1$だと空集合のmaxをとってしまい、1RE。
問題C – Successive Subtraction
など。2式が$c$の符号を変えただけになっていることからも、雑にいうと1つの数の係数を好きに決められてしまうという自由度の高さが読み取れます。
・全ての数が$\pm 1$倍されて足される。
・「全部$+$」「全部$-$」が作れないことの証明：初手に$x-y$をやったとする。以降どうやっても$x,y$の係数は逆の符号
実際のアルゴリズムの例：
・$1, 2, 3, 4, 5$ → $1-2-3-4, 5$ → $5-(1-2-3-4)$.
実装も3つに分けて、上述の例で確認しながら実装しました。
問題D – Squirrel Merchant
一度誤読しました。「1つ操作を選び、それを任意回数行う」ではなく「1つ操作を選び行う、ことを任意回数行う」でした。（前者の場合、1種の金属しか扱わなくなって、簡単な問題3回。600点だと流石にそんなことないですね、その辺の感覚もうちょっとなじませないと…）。
換金し放題なので、各時点で「一番価値が高い状態を目指す」問題です。「価値を最大化」という漠然としたイメージを突き詰めると、「次の段階のどんぐり換算での貨幣価値」として定式化できました。あとは同種のdpを2回です。
1回あたり$O(N)$だからかなり雑でも通るだろうと思っていたのですが、TLEを食らいます。
よく考えると、worst caseは、
・[A] どんぐり $N$ → 金 $N$
・[B] 金$N$ → どんぐり$N^2$ → ？
なので、2回目のdpは$O(N^2)$です。
計算量を誤解して提出していた恥ずかしいやらかしですが、PyPyで提出して1TLEのみで事無きを得ました。
問題E – Balanced Piles
$H$方向でdpだというのは想像がつくけれど、かなり難しかった。
最初の本質的な気付きは、「途中経過で現れる最大値の個数」ごとに同じ計算になりそうだということ。例えば、「$0, 2, 3, 4$」が最大値として現れる場合と、「$0, 1, 3, 4$」が最大値として現れる場合は、等しく扱える。着地点の条件$[M, M+D]$はあくまで$M$のみから定まっているので、一度最大値$3$に到達しているのであれば、$4$段目に進めるかどうかは$2$段目以下の高さ関係なく決まる。「気付き」というか当たり前のことではあるのだが…。
最大値「$0, 1, 2, 3$」というようなルートに固定しても、上手く計算できない。最小値で並んでいる状態から、操作順の並べ替えが存在するからだ。今度は、「$y=0$を経由する人数」「$y=1$を経由する人数」などを固定してみる。すると、いじる$y$座標の順番は確定するので、場合の数が階乗の積で計算できる。
今度は、各$y$座標を経由する人数の分布としてどういうものがありうるかを考えてみる。
例えば、最大値が$0, 1, 2, 3$と更新されるルートの場合、全員が最大値$0$を経由する。$y=1$, $y=2$については、$1$人から$N$人まで自由に決められる。ということは、この最大値集合の場合の答は、$N! * (1! + 2! + \cdots + N!)^2$だ。
あとは最大値集合ごとに…と思ったが、「$k$ステップで$H$段に到達する方法の個数」を各$k$に対して求める…$k=1,2,\ldots,N$の値を持ってdpしていく？？$O(NH)$で全然ダメ。
よく考えると、$M$段目から$M+k$番目に遷移するとき場合の数が$(1!+2!+\cdots+N!)$倍になるというルールだったので、
\[ dp[h] = (1!+2!+\cdots+N!)\sum_{k=1}^D dp[h-k]\]
というような漸化式が立った。
漸化式が立っても今度は普通にやると$O(HD)$でやっぱりアウト。そこでdpの累積和も一緒に更新しておき、dpの区間和はそこから計算する。これは過去問で経験があったため、すぐに対応できた。
最後の発想も難しくはないが、結果論としてあと3分悩んでいたらアウトだったため、過去問を練習していなかったらアウトだったと思われる。練習が少しずつ実力につながっているのか。
