【参戦ログ】第二回全国統一プログラミング王決定戦予選

Nov 10, 2019 12:02 compro

ますぐれです。昨日は第二回プログラミング王決定戦がありましたね。割といい感じに動けた気がするので記録を残しておこうと思います。この記事は戦略についての内容が主なので、考察ログに比べると若干荒いところがあります。

先に結果の方を述べておくと、ABDの3完で570位でした。現在の実力がしっかり発揮できた形です。

コンテスト前

やる前にざっくりと戦略を立てていました。前までは戦略とかよりも実力をつけろっていうスタンスだったんですけど、最近は青パフォor緑パフォみたいな結果を出し続けていて、これは戦略で多少ましにできそうと思ったのが立てた理由です。

今回の戦略はこんな感じです。

AとBをゆっくり目でもいいので0WAで通す
CDEを全部開けて、ランキングのAC数と見比べながら倒せそうなやつを考察する

書くと結構当然って感じですが、意識するのとしないのとだと結構違うんですよねえ。

コンテスト開始後

A問題

$\frac{n-1}{2}$をしました。

B問題

思ったより難しかったです。考察を数式に落とすまで結構時間がかかってしまいました。その代わり考察の時点でコーナーケースを全部拾えたのが良かった点です。

前述の戦略がなかったら、たぶん焦って複数個0があるケースとかで撃墜されるコードを書きそうだなあと思っていました。

ここまでで大体15分です。この時点でCDEを開けたんですが、CよりDの方が考察しやすそうに見え、AC数もその感覚を肯定していたのでDに行くことにしました。

D問題

最初の方は頑張って辺を減らせないかなあという考察をしていました。ufとかでマージとかするとうまくいくかな？　とか、実は$L_i$から$R_i$にだけ辺を生やせばいいのでは？　みたいなことを考えていたのですがまとまらず。

この過程でコストは単調増加だということに気づき、dpで出来ないかなあという方向に考えがシフトしていきました。dpの式を立ててみるとなんかセグ木でコストを管理すると更新はうまくいくことに気づきました。

この時点では、$L_i$から$R_i$全ての点を更新しなきゃいけないなあと思って計算量オーバーするなってなってました。大体ここらへんで40分くらいだったと思います。

うーん分からんって言いながら一番下のサンプルで遊び始めたら、$R_i$だけ更新すればうまくいくことに気づきました。これで上の解法が時間的には通ることが分かったので細かいところを詰めようとします。

ここが今回のやらかしポイントではあるんですが、下のサンプルで遊ぶときはコスト最小の辺から伸ばしていくみたいなことをやってたんですよね。それで構成された解は当然最適だろうと思ったので、優先度付きキューを2種類用意して$L$が現在到達可能な頂点以下のもののうち、コストが最小のものから辺を生やすという解法を実装しました。

これはダメな解法です。なんでだろうなあって思っていろいろ調べていたんですが、下のケースで死ぬことが分かりました。

このケースから、$L$が小さい順に見たら更新時に結局コストのminを取るのでオッケーやんということに気づき、訂正してsubmit。ACを得ます。

優先度付きキュー2つの実装とか大変だったんで、その分の時間とかがもったいないなあという感じでした。

ですが、今回はこれバグらせずに実装できたのが結構嬉しかったりもしました。考察を疑似コードレベルまで紙に落としたのが良かったみたいです。変更するときも疑似コードと照らし合わせながらやったので特にバグもなかったです。その点のリカバリーは今回の良いポイントでした。

この時点で40分くらい残っていたので、AC数を考慮してC問題に行きます。

C問題

これ本番中は全くつかみどころがないなあってなって、サンプルケースをこねくり回していました。なんで掴みどころがなかったのかというと、$N-1$回操作すれば自明なダメな奴以外は全部行ける、という事実を意識してなかったからです。

とりあえず自明なダメなやつを判定するのは簡単なので、そうでない場合を考えていました。

そのときに考えていたアルゴリズムがこれです。

$A_i > B_i$となる組をそれぞれ優先度付きキューに入れる
大きい順に取り出していって組み合わせていく
それでも$A_i > B_j$となってしまうようなものがあれば、$B_k$が$A_i$以上かつその中で$A_k$が最小になる$(A_k, B_k)$を優先度付きキューに放り込む
最後まで構成しきったとき、優先度付きキューに入らないものが少なくとも1つあればOK

これは嘘っぽい(未証明)です。これを構成しきったのが残り5分くらいのタイミングだったので実装もしていません。

終わりに

時間をかければ500や600もAC出来るようになってきたような気がするので、次はこの時間を圧縮するフェーズだなあという感じです。そうすると次の問題に使える時間が増えてAC数も増やしていけそうですね。このような出題で4完できれば黄色パフォくらいは出そう。

参加記書くと結構振り返りになりますね。今後も気が向いたら書いていくかもしれません。

競プロ以外の記事も置きたいなあと思っていますが、今ハマっているのが競プロなので、それ以外の記事はあまり出なさそうです。