PAST5 PAST202012 アルゴリズム実技検定 第五回 アルゴリズム実技検定 - AtCoder
70点、中級でした。
初めて受験した第三回もその次の第四回も中級で、今度こそ上級になりたいなとPAST過去問練習202012して臨んだのだけども、点数はむしろ下がってしまった。
受験中に考えたことを書いておく。まだ過去問としての公開がされてないので問題文や解説を確認できない。個別の問題の詳しい解法はそれが出てから別途書く。 過去問の公開がされたので順にやっていく
- E〜の解説
- HのTLEの原因確認
- Jの解説見ないでのときなおし
- LMNOの解説の確認
A〜D
- 特に何もメモせずに淡々と解いた
- 素朴に全探索すれば良い
- はみださないように全探索するために、スタンプでない側にスタンプの幅分の番兵をつけた
- 番兵をつけるコード自体は既に書いてあった
- 回転は想定してなかったので今回新たに書いた
- 回転時に縦横の長さが交換される、スタンプの側だけを交換するべきだが取り違えててWAした
- 2 ** 14 == 16384
- 14 * 13 * 12 == 364
- これは全探索して良いサイズ
- 問題条件を勘違いしてWA
- 一触即発状態での「既に混ぜた薬品の数」ではない
- 「一触即発状態のルールの数」でもない
- 「一触即発状態のルールの、まだ追加してない薬品」の集合のサイズ
- グラフを作って各頂点を始点として「すべての頂点を通るパス」をDFS
- 長さが1の時、グラフにならないのがコーナーケース
ここまでで1時間25分。ここでまず残りすべての問題に目を通すことにした。下記の「初回考察」がそれ。
- 初回考察
- 動かせるか判定
- グラフを構築して、各始点から「ゴールにたどり着けるか」をDFS
- 頂点数10^6、大丈夫？
- スタートがたくさん、ゴールは一つ
- グラフを逆辺で作っておき、ゴールを始点として到達可能頂点を探索する。
- 各頂点高々4本の辺しか持たないのでO(N)で間に合う
- 考察完了
- 初回考察
- 初回考察
- 素朴に出力はできない
- 各繰り返しのブロックのサイズを前計算しておけば、クエリの値を徐々に剰余とっていくことで解決するだろう
- 考察完了
- 初回考察
- 出現箇所は複数あり、どちらを優先して消すかによって最良の結果になったりならなかったりする
- うーん、なんらかのグリーディな決め方が存在する？
- オーバーラップしてない場合にはどちらからやっても変わらない？
- それでも最悪33個オーバーラップしてる。33の階乗は無理
- 非決定オートマトンでいい感じに処理できないかな
- 保留
- 初回考察
- 切る切らない2^Nは、Nが10^5とか大きいのでダメ
- 2NのDPになる？
- 無理そう
- 一旦最大限に長く刻んで、その刻みを1つずつ前に移動するスタイルではどうか
- しゃくとり法的な、解のありそうなところだけを探索するアプローチ
- 下限が徐々に上がっていく、下限より小さくなるところは探索しなくても良いので割と探索空間小さめにならないかなー
- 初回考察
- バスの辺に年齢の上限、下限があり、与えられた年齢がその範囲に収まっているときだけ辺が存在するとみなして到達可能範囲を求める問題
- 年齢軸を時間軸にする
- 二次元の片方を時間軸にする
- 下限でつなぎ、上限で外せば良い
- クエリは先読みして、混ぜてソートする
- PAST2NではRange Addだったけど、今回はそうではない、どうするか？
- 繋がってる範囲の右端と左端が高速に得られれば良い
- 右端を持つフェニック木と左端を持つフェニック木を用意すれば良い
- ある位置が与えられた時に、そこより左にある最も近い左端を見つけるのは二分探索で対数オーダー
- 見つけた左端より右で最も近い右端を見つければ範囲がわかる
- クエリで与えられた位置がその範囲に入ってれば、それが答え
- 考察完了
- 初回考察
- プッシュでもプルでも最悪10^5になるので10^5回のクエリでは破綻する
- (補足: 通知発生時に受領者の値を変更する「プッシュ」の場合、フレンドの10^5人いる人が通知を10^5回送るとダメ。逆に通知確認の時にフレンドの誰が送ったか確認しにいく「プル」の場合はフレンドの多い人が通知確認をしまくるとダメ)
- フレンドがルートN以上の人の処理だけ遅延させる
- こういう人は高々ルートN人
- 通知確認時にこれらの人xだけプルする
- xの発生させた総通知数をxが持つ
- yがxから受信した総数をyが持つ。高々ルートN
- この二つを引けばxからの新しい通知の数がわかる
- 考察完了
一通り考察して、残り3時間。
- Lがまったくわからない
- M, Oが解けそうな気がするが「一見解けそうに見えて、解いてみると見落としが発見されるパターン」だろうなと思う
- コンテストと違って難しい問題を優先して解いてもレートが上がるわけじゃないからな(むしろ点数は低い)
- 頭から順番に解いて、改めてLを見返す方針でやろう
この後の出来事
- H、18分で提出してWA、修正するも3回TLE、35分まで掛かって解決しないので保留して次へ
- I、ダイクストラする、9分でAC
- J、落ち着いて実装するべきだったのに混乱してしまう
- 一つズレのバグを解決してようやくサンプルが通ったのが56分後
- しかしTLE
- 繰り返しの単位になる文字列を切り出して使ってたけども、元の文字列のどこから開始するかだけを待てば良いと考える
- さらに16分使ってまたTLE、それどころかMLEもある
- どういうことか？！
- 例えば9がたくさん続いた時に「繰り返しブロックのサイズ」はとても大きな数になる、これを意識せずにそのままやってたのが問題
- リアルタイムでは「まったく方針が間違ってたということか？」と思って諦めた
- 一晩寝て起きたら、クエリとして渡される数が10^15以下だと制限されてるので、それを超えた時点で文字列のパース処理を打ち切ってしまって良いと気づいた
- K、期待値DPする、19分でAC
- この時点で残り45分、方針の立ってないLに挑戦できる状態ではない、TLEになってるHを解決しよう
- H、30分使ってさらに3回TLEして、残り15分でようやくAC
- グラフを陽に構築しないスタイルに書き換えた
- DFSを再帰呼び出ししないバージョンにした
時間で整理すると
- 72分使って無得点のJが酷い
- 80分使ってようやくACしたHもいまいち
- Iが9分、Kが19分なのと比べると落差が激しい