PAST 第1回を解いてみた

AtCoder社のアルゴリズム実技検定　第一回の問題を全部解いてみた。 感想をはさみながら解説をする。

A問題

PASTだけに普段よりは実務的な問題って感じがする。やるだけ。 入力例もどことなく実務を意識している感じがある。（アルファベットの入った文字列を整数値リテラルと解釈してしまうことによる脆弱性はいかにもありそうなため）

B問題

同じく、実務を意識させている。やるだけ。

C問題

実務？やるだけ。

D問題

実務っぽいかも。やるだけ。

E問題

無駄に複雑でめちゃくちゃ詰まった。 制約がゆるいので雑にやれるのが救い。

F問題

実務かは怪しい。面倒だけどやるだけ。

G問題

全探索。PASTの問題傾向がこのあたりでなんとなくわかってくる。

H問題

セグ木で殴ってしまったが、O(N)で解ける。簡単。

I問題

典型的なbit全探索。入力形式は実務っぽい。

J問題

これが地味に難しい（？）。 ある2点を結ぶ経路があって、そこの途中からもう1点へ分岐している、と考えれば、そこの交点から3点への距離を調べれば良い。

この辺りからアルゴリズム知識が必要になってくる。

K問題

典型的なLCA問題。ダブリングで終了。

L問題

が小さいので、使う小さい塔を全探索して最小全域木問題を解く。

M問題

こういうのは二分探索が常套テクニック。

類題もある。

N問題

セグ木で殴れそうに見えるが、実は余事象を考える必要がある。

それぞれの区間について取らなくていい石のコストの和は、区間をスライドさせていけば合計 で求まる。 区間の候補は適当にしておけばいい。

O問題

最終問題だけあって難しいかと思いきやそこまででもない。

確率論の基礎的な教養があれば、次のサイコロを選ぶためには今出ている目以外の情報は必要ないとわかる。

次にどのサイコロを選ぶと、これからサイコロが振れる回数の期待値を最大化できるか考えればよく、これは次の目が今の目より大きい場合には計算が必要で、そうでなければ全部0である。 よって、目が大きい順に計算していけばすべての目についてこれが求まるので、答えは、最もこの期待値が大きいサイコロのものを選べば良い。

感想

5時間で解けるかは多少不安。 最後の4問くらいだけ集めた教材があったら青コーダーくらいに対してとても教育的だと思った。