PAST3を受験したんだよっ - ちゃっくのメモ帳

この記事は解説ではなくただの感想です。

結果

A~Mを解いて88点で上級。
どのくらいのレートだとどのくらいの点数になるか分かっていないので良いのか悪いのかわからず...

全体の感想

普段コンテストにあんまりでないのにPASTが無料と聞いて飛びついてみた。乞食精神旺盛ですねとか言われたら泣いちゃうかもしれない。

社会人にとって5時間を用意するのはかなりハードルが高い。
今回は金曜日の就業後にやった。8時間労働のあと5時間プログラミングするのはかなり疲れる。そのため、2時間くらい過ぎたあたりからは自分との戦いになる(自分との戦いって言いたいだけです)。
土日にやったほうが良さそうだけど1日潰す覚悟が必要でなかなか気分が乗らなかった。(TOEICとかIPAの試験とか1日潰すつもりで受けるのでそのくらいの気持ちで受けるべきものなのかもしれない)。

解いた範囲の感想。
全体的に実装重視の気がした(異常にバグらせまくったのでそんな気がしただけかもしれない)。AtcoderよりICPC国内予選のA~Cあたりのほうが問題のイメージが近い気がしたけど、そんなこと言ってる人みかけないので気のせいかもしれない。
WAに対してペナルティが無いのでそのあたりはすごくやりやすい(サブミットデバッグをするな)。

この試験は40点ラインで初級と書いてある。しかし、40点に達するためには前からだとFまで解く必要がある。Fまで解き切るのに「オーバーフロー」「2次元配列(文字列型の1次元配列)」「グラフを持つ」「回文」(レイヤーが違うものを並べてSorry)などのハードルがある。このハードルは地味に最初の称号を手に入れるハードルとしては高い気がした。
コンテスト中にC問題とE問題でバグらせたときには「おいおい、まじかよ。自分は初級にもなれないのか。。。」って気持ちになったし、D問題の実装で地味に詰まったりした。

問題は全体的に好きだった。(Mまでは)天才的発想を要求してこないし、基礎はしっかり出来てますかみたいな感じが好きだなぁと思った。

各問題について

A問題

とくになし。

B問題

「現時点で」を読み落として詰まる。

C問題

$AR^{N-1}$ を求めるだけ。
ただし、オーバーフローに注意する必要がある。long longを使ったらWAしたので、Pythonに逃げた。後からunsigned long longにしたら通った。

C問題で高速累乗が必要になるのはびっくり。

追記
高速累乗いらないっぽいです。たしかに2^nでもnが30程度でlargeになるか。
https://twitter.com/rian_tkb/status/1269331562304159745?s=19

D問題

問題の意味を理解するのに時間がかかりすぎる。
個人的には「入力例1を見てください」がなんか....

E問題

とくになし。

F問題

とくになし。

G問題

6方向の意味を考えて警戒した。普通4か8方向でしょ....
BFSをすれば良いが、負の座標もあるので実装で添字に下駄を履かせる必要がある。

個人的には、アルゴリズム検定なんだからC問題とこの問題は逆じゃないかという気もしなくもない。(アルゴリズムの解釈にもよるけど....)

H問題

Tが偶数で距離に0.5が出てくるので思考停止で距離2倍、Tを1/2倍した。
結果的にはしなくても良かった気がする。

DPはすぐ思いつくし、DPの遷移もすぐに思いついたけど「地点Lで行動が終了する」ではなく「地点Lを通過すればよい」ので、地味に実装がめんどくさくなった。
とりあえずdp[i]をiで行動が終了する最短時刻を求めたあと、各iに対してdp[i]から1回の行動で通過できる場所とその場所までの時間を計算した。

I問題

とくになし。

J問題

僕は今日夕食に寿司を食べました。(自慢)

セグメント木と二分探索で解いた。
頭が壊れてaを-aにしてRange Maximum Queryにした。よく考えたらRange Minimum Queryでいい。何をしたかったんだ...

実はLISになるというのを後から知った。そう言われたらそうですね。頭がよろしいことで...

K問題

問題としてはとくになし。
最初UnionFindを使おうとしたのでUnion Findっぽく親の番号を保存した。
ただし、地面に振れてる箱は親を「地面の番号」を符号反転したものにした。
これもUnion Findの実装としてどこかでされてましたね。

L問題

これも問題としてはアルゴリズムという感じではないと思ったけど実装が大変になった。
ただ、制約のa<=2を見落とさないように注意する。
最初かなり複雑な実装をしてWAを出した。
実装が複雑化しすぎたのでlinked listで書き直した。

M問題

K<=min(N-1,16)に気がつくと解ける。
TSPなので制約に特徴があるか、問題に特徴があるかのどちらか。

愚直にbitDPしたらWA。
これは、「到着した集合」だけじゃなくて、その集合に到着するときの最短コストのときに「最後にどこの街にいる可能性があるか」を持つ必要がある。
なのでdp[i][j]を「すでに到達した街の集合」と「最後に到達した街」を状態としてその状態への最短コストを持てば良い。

N問題 O問題

読んでいない....