PAST 第2回を解いてみた

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

今回はバチャ形式で一気に解いたので、時間も記しておく。

A問題 2:42

やるだけ、条件分岐して和か差。

B問題 4:54

std::countを使うと楽。やるだけ。

C問題 10:13 1WA

シミュレーション。やるだけ。

配列サイズを間違えて一敗。

D問題 15:38

全探索。やるだけ。

E問題 17:55

シミュレーション。やるだけ。

F問題 28:00

priority_queueで殴る。この辺から難しくなってきた感じがする。

G問題 35:20

dequeを使うだけ。

H問題 45:37

BFS。JOIのチーズが類題。

I問題 51:54

シミュレーション。やるだけ。

J問題 63:12

構文解析ふうにやる。雑にやってもたぶん に収まる。

ここまでで1時間強。

K問題 68:18

急に難易度が落ちる。DPをするだけ。

L問題 93:14

次の場所の候補は明らかに区間なので、考察は簡単。 最小値の場所がわかるセグ木が欲しくなるので、作る。

ただ、セグ木ライブラリがバグっていたため修正作業も入って面倒だった。

M問題 165:19

噂には聞いていたが、実装がかなり面倒。

とりあえず次の好きな料理まで進めて、そのあとD日目のうち最初の好きな料理まで進めて、そこからは周期を使うのが楽そう。

これをバグらせないで書けたのは我ながらすごいと思う。 lldbのセグフォ検知力が高く、助かった。

N問題 268:50 2WA

セグ木と平面走査という実家のような問題。

Starry Skyの悪夢が蘇るが、幸いにも定数倍は優しい。

座圧を一部ミスっていたため2WA。

O問題 256:48 8WA

解法はすぐなんとなくわかるし、証明も厳密に記述できなくても自明なのでまあよい。

結局パス上の辺の重みの最大値が知りたいので、HLD+セグ木とかで殴るとよいが、上で言ったようにセグ木ライブラリが崩壊していたため、とりあえず代わりにSparse Tableを貼る。

HLDからSparseTableに辺を乗っけて参照するのをミスっており、REやWAを大量に出した。 20分ぐらいで直し、AC。

感想

第1回より難しく、というかバグりやすくなった気はする。 セグ木はともかくHLDが実務に求められるかは疑問だが、ダブリングでも解けるらしいので、まあ（？）