第4回アルゴリズム実技検定（PAST）体験記

2020/10/25（日）に第4回アルゴリズム実技検定（PAST）のリアルタイム受験をやりました。結果から述べますと、4時間55分かけて94点を取り、ギリギリでエキスパートになることができました。ちなみに検定当時のAtCoderのレーティングは1893（青）です。今は1874で下降気味ですね？おかしいなあ……。

当然ながら大量にネタバレを含むので、まだ受けてない人は受けてから読むとよいかと思います。というか受けてないとおそらく意味不明です。過去問扱いになったので無料で受けることができます。休みの日にでも是非。

atcoder.jp

A 中央値

やるだけ。（1m31s）

B 電卓

誤差が怖い。こういうのはdecimalでやると良いんですよね。C#サイコー。投げる。WA。四捨五入ではなく切り捨てという条件を見逃していた。切り捨てならとintに書き直す。WA。世界一業プロが下手。焦りながらdecimalで切り捨て処理を行う。AC。これはひどい。（7m52s）

C 隣接カウント

やるだけ。（11m34s）

D 分身

制約が小さい。全探索で良さそう。右と左を間違えてバグらせる。今日あんまり調子よくないな？（20m39s）

E アナグラム

制約が小さい。脳死next_permutationをする。okフラグとngフラグを逆にしてバグる。もうだめだ。（28m02s）

F 構文解析

Dictionary<string, int>で出現回数を数えてからソートすればいい、はずだったのだが焦りもあって迷走する。初級問題で23分溶かす青コーダー。このあたりで上級止まりを覚悟する。（51m00s）

G 村整備

DFSで連結成分を求めておいて、各壁を壊したときに連結になるか調べれば良さそう。実装する。AC。ちょっと冷静になる。（1h00m52s）

H マス目のカット

。電卓を取り出す。が間に合いそう。全探索。（1h07m14s）

I ピザ

しゃくとりベースで行けそう。番目と番目を跨ぐケースが面倒そうなので配列を2個繋げる。実装する。サンプルが合わない。よく見ると1ループでleft++が2回出てきている。普段しゃくとり書かないからと言い訳しつつAC。にぶたんの方がよかったかも。（1h24m03s）

J ワープ

ワープ用の頂点を作って有向辺を張ってダイクストラ。これはすんなり。（1h33m20s）

K 転倒数

訝しみつつもだからFenwick Treeで愚直にやっても間に合うと盛大に勘違いする。そんなわけはない。実装が終わったタイミングで気付く。しばらく考えると、「各数列の中の転倒数」と「数列をくっつけたときに増える転倒数」に分けて考えるとよいことに気付く。似たような問題を前にも見たような気がする。実装。AC。（1h59m40s）

L マンションの改築

最近やったPAST第1回過去問のH - まとめ売りが頭をよぎる。似たノリで「奇数番目のかさ上げ量」と「偶数番目のかさ上げ量」を管理しておくと良さそう。あとは奇数番目、偶数番目それぞれについて、高さがhであるマンションの個数をDictionary<long, int>で管理しておく。ごちゃごちゃしてきたのでサンプルでデバッグするかと走らせると全部合う。一発で通るとかある？と思いながら投げる。AC。残り3問中2問通せばエキスパート。（2h13m56s）

M 筆塗り

木のパスに色を塗るクエリを処理する問題。上書きするタイプのクエリ問題なので、クエリを後ろから処理したくなる。が、難しい。から落ちない。パスの処理に毎回かかるのでここをなんとかしたいが、良い方法が思い浮かばない。*1パスについて考えるのをやめ、各辺について独立に考えてみる。「辺より右側の頂点と左側の頂点のペアが最後に選ばれるクエリ」が分かればよさそう。だがどう考えても効率的に検索できない。暗礁に乗り上げる。

残り2問も見てみる。Nは見るからにDPっぽい香りの数え上げ。しかし状態の持ち方が分からない。制約（行数と列数）が妙に小さいのも怖い。Oも一見DPっぽく見えたが、は当然間に合わない。区間の後端でソートしてみたくなる。ソートする。何もわからない。Oは捨てることにする。

Mに戻ってくる。何もわからないまま1時間以上が過ぎる。残り1.5時間。木のパスについてなんとかできないかと色々と考えた結果、ふとLCAに思い至る。パスに関するクエリをとに分割してみる。適当に根を決め、葉からスタートして根に向けて上っていき、かに着いたらクエリを拾い、に着いたら捨てればよさそうに見える。拾ったクエリはPriorityQueue<T>に入れ、クエリ番号の一番大きいクエリで辺を塗っていくことにする。各部分木から得られるクエリをマージする際の計算量が気になるが、マージテクを使えばクエリのマージ回数はで抑えられるはず。これで計算量はたぶんとかに収まってそう？よくわからないけどとかにはなってないはず。

実装。投げる。WA。TLEではないので方針が大外れというわけではなさそう。に着いたときにPriorityQueue<T>内のクエリを捨てられるだけ捨てることにしていたがそれでは不十分で、到達済みのをHashSet<T>で管理する必要があることに気付く。こちらもマージの大小関係に気を付ける。実装。投げる。AC。あと1問。（3h51m02s）

N マス目の穴埋め

Oは無理そうなので、比較的筋道を立てやすそうなNに取りかかる。与えられた盤面の?を0か1に書き換えて得られるもののうち、条件を満たすものの数を数え上げる問題。やっぱりDPっぽい。上から下に向けて進めていくと良さそうに見える。そしてなんとなく実装が辛そうな予感がする。この予感は後に的中する。

何に着目すれば状態をまとめられるか考えてみる。row行目という情報は必要。01の並びも情報として欲しい。これは2進数で持てば通りしかないので余裕。あとは何が必要だろう。「各マスについて、下のマスを除く上・左・右・中に関して、書き込まれた数字が1であるマスの数」を6マス分持たせようとする。とかいう†8次元DP†が爆誕する。こんなのが想定解なわけがないと思いつつも、計算量は行数を、列数をとしてでくらいになりそうに見える。時間もないのでこれで突き進む。

実装するうち、遷移式の中でbitをrow行目とrow-1行目の両方（64通り×64通り）について考えなければならないことに気付く。になってかなり怪しい。が、無視。実装が辛いが、150行分を何とか書き上げてサンプルを走らせる。案の定手元環境で10秒くらいかかっている。遅い。

DPの高速化を考える。サンプルも合っていないのだが、ひとまず置いておく。「上・左・右・中のうち、1であるマスの数」は0～4個の5通りもあるので、持ち方を工夫して状態数を小さくしたい。「中と同じマスの数」にすると、3個あればその時点で中央値になれることが確定するので、4個目を考えなくてよくなる。ついでに真ん中は当然真ん中と同じ値なので、これも考えなくてよい。これで0～2個の3通り（上・左・右のうち2個あればその時点で中央値になれることが確定する）。最終的に「上・左・右のうち、中と同じであるマスの数。ただし2個以上の場合は2個と見なす」を6マス分持たせることにした。計算量は。おそらくくらいに収まってくれそう。†8次元DP†は相変わらずだけど*2。

サンプルを走らせる。実行時間は問題なし。出力が合わない。残り時間が30分を切っているので、死ぬ気でデバッグをする。いくつかバグを潰すが、まだ合わない。響ちゃんデバッグ*3を開始する。残り10分を切る。ギリギリのところで、ビットシフトの順番を逆にしており情報が落ちている（0b1111を左に1、右に2の順でビットシフトすると0b0111になるが、右に2、左に1の順番にしてしまったため0b0110になっていた）ことに気付く。修正。サンプルが通る。祈りながら投げる。1...4...7......AC。残り5分でギリギリ滑り込んだ。（4h55m01s）

O 宝箱

解説読んだ。天才。いつか満点を取れる実力を付けたいね。

*1:後になって思い付いたのだが、HL分解+遅延（or双対）セグ木で殴れたかもしれない。HL分解未履修なのでアレだけど。

*2:実は普通にdp[行数, その行の01列, 一つ上の行の01列]のDPで行けるのだが、それはまた別のお話……。

*3:響ちゃんに向かって1行ずつコードの説明をすることでバグを明らかにするデバッグ手法。一般に言うラバーダック・デバッグ。