第二回アルゴリズム実技検定 (PAST) 受検記

4/18 に AtCoder 社主催のアルゴリズム実技検定 (通称 PAST) に参加しました。

リアルタイム受験だったので検定終了直後から早く解法や感想を語りたくてうずうずしていたのですが，通常受験期間が終わるまでぐっとこらえました。

総得点は94点 (O 問題以外の 14 完) で，エキスパートを取得することができました。明らかに問題との相性が良く，上振れを引いた感があります。暖色やそれに準ずる実力の方々はやすやすと満点を取ってしまうでしょうし，非満点エキスパート勢って少ないんじゃないかなと勝手に思っています。

せっかくなので 1 問ずつ感想を書いていきたいと思います。ただし，すでに記憶がほとんどないので受験直後のメモに書いていなかった部分は内容が無になります。各問題のタイトルの後ろにある括弧はリアルタイム受験で私が AC するまでにかかった時間です。

A (0:04:02)

エレベーターを題材にしているだけあって問題文はすっと頭に入ってくるのですが，ソースコードに起こすとこれが意外と短くならない。

地上階が 1F 2F ……でアルファベットが2文字目なのに対して，地下階は B1 B2 ……でアルファベットが1文字目なのは最初間違えそうになりました。

B (0:06:27)

こちらも問題文はすっと入ってきます。A問題と違ってやるべきことも明らか。

一見 A 問題より簡単なようにも見えますが，こちらが B 問題なのは A 問題で必要とされない for ぶんが必要とされるからでしょう。

C (0:12:34)

これもやるべきことが問題文に直接書いてあるタイプの問題。二重ループでシミュレーションできます。

最初 . のところも X で塗りつぶしてしまったのは内緒。

D (0:18:09)

ここから少しだけ複雑になっていきます。

この問題で考慮すべき部分文字列の長さは最大 3 なので，(ありうるすべての部分文字列の開始箇所) × (部分文字列の長さ 1, 2, 3) × (. への置き換えの全パターン (長さ k に対して 2^k 通り)) をすべて試して set に突っ込めば最終的な set の要素数が答えになります。. の置き換えを全パターン試すときは bit 全探索っぽく bit 演算を使うと便利です。1 文字目を 2⁰ の位，2 文字目を 2¹ の位，3文字目を 2² のくらいに対応させればよいです。

E (0:22:27)

言われていることをシミュレーションすればよいのですが， C までのシミュレーションに比べると読解が少し複雑です。

F (0:29:30)

priority_queue を使ったシミュレーション。i日目になったらi日目以降に実施できるタスクを priority_queue に突っ込んで，得られるポイントが大きい順に毎日取り出していけばいいです。

G (0:39:32)

文字列に関するシミュレーション。ありうる最大の文字数が約 ${10}^{10}$ 文字と非常に大きいので，1 文字 1 文字もつ or 文字列をそのままもつと時間もメモリも間に合いません。

$i$ 文字目を一度クエリの計算に使うと $i$ 文字目はお役御免になるので， (文字，文字数) のペアを管理するとよいです。文字を後ろから追加して前から消していくので，queue で管理できます。

H (0:58:34)

なかなかにひどいソースコードですが，dijkstra でぶん殴りました。事前にグラフを作ったりはせず，$n$ が書いてある頂点からは $n+1$ が書いてある頂点のみに遷移する，S は $0$ として，G は $1$ として扱うということをしています。

I (1:09:35)

queue や deque に「次の試合に進出する人」を突っ込んでいって管理します。決勝戦に出た2人は勝っても負けても「最後の試合」は同じになることに注意です。

J (1:17:09)

これ好き。 stack を使っていい感じにシミュレーションする問題です。基本的には 1 文字ずつ stack に突っ込んでいって，) の番になったら ( が出てくるまで stack の上に積まれているものを取り出していけばよいです。

K (1:43:36)

これは最初に $O(N^3)$ のメモ化再帰を書いて詰まってしまいました。

しかし冷静に考えてみると，valid な括弧列というのは

( を +1，) を -1 と考えて先頭から足していったとき，途中で負にならない
同様に，最後には 0 になる

なので，前から順番に見ていく DP をすればよいです。

許可されている操作が1文字削除と1文字反転であることから，$\mathit{dp}_{i, j}$ ($i$ 文字目まで見ており，上のような考え方で足していったときの和が j) から遷移できるのは $\mathit{dp}_{i, j}, \mathit{dp}_{i, j+1}, \mathit{dp}_{i, j-1}$ の 3 つだけなので，時間計算量 $O(N^2)$ でいけます。

L (2:14:49)

多分セグ木なんてなくても解けるのでしょうけど， ($i$, $A_i$) を乗せたセグ木でぶん殴りました。$K$ 個の値を選びたいので，$i$ (1-indexed) 番目の値の index は ($i-1$ 番目の値の index) + 1 以上 $N - D \times (K-i)$ 以下のはずです。

M (3:09:47)

ゴリゴリと実装をした記憶しかありません。こういう問題はどちらかというと得意な方ですが，解説を書くのは苦手です。

特に好きな料理が提供されない場合に次に何日後に食堂に行くのかはどの社員でも同じ ($L$日後) なので，「ある料理を食べた人は，次に同じ料理を食べるまでに何回食堂に行くことになるのか？」およびそれを 1 週 ( $D$ 日) 分合計したものを事前に計算しておきます。あとはこれを使って (1) 最初に好きな料理を食べる日まで何回食堂に行くか (2) 食堂に行く回数の上限未満の範囲で D 日 1 週の流れを何週繰り替えすか (3) (1) と (2) のあと残った回数で好きな料理が何回食べられるかを計算します。この実装でかなり悩みました。

N (4:28:31)

これもゴリゴリと実装をした記憶しかありません。自分のソースコードを見たところ，どうやら座標圧縮 + セグ木で解いたようですが，何をしているのかいまいちわかりません……。

解いた直後の私のメモ曰く，「登場する座標を軸ごとに全部まとめて座標圧縮！まではよかったのですが，そのあとは迷走してしまいました。」とのこと。

問題の内容とは全く関係ないですが，これを解ければエキスパート！　というところだったのでドキドキしつつ自分を信じてがむしゃらに実装した問題でした。

O (-:--:--)

解けませんでした。ある頂点からある頂点までのパスに含まれる辺の重みのうち最大のものがわかれば，辺の追加と消していい辺のうち重みが最も大きいものの削除でいける気がしたのですが，肝心のある頂点からある頂点のパスに含まれる辺の重みの最大値の求め方がわかりませんでした。オイラーツアーを使って LCA ちっくにできるかもしれないと思いましたが，まだ実装していません。暖色の方からは結構典型だという意見も見られましたし，復習したら記事にします。 -> 記事にしました第二回アルゴリズム実技検定 (PAST) O - 可変全域木 - NoiminのNoise