season's quarterly

数学/物理/プログラミング

PCK2020予選参加記[EngelBæts!]

9/12に開催されたPCK2020予選に参加しました。
本選はこちらです。
season1618.hatenablog.jp
PCK2019の参加記はこちらです。
season1618.hatenablog.jp
season1618.hatenablog.jp

チーム

チーム名は「EngelBæts!」です。世の中には「Angel Beats!」「Angel係数」「Engel係数」という言葉があるのですが、「Engel Beats!」だけなかったのではい。10文字制限なのでスペースを排除してeaを発音記号でごまかしました。相方は競プロ未経験の一年生です。

練習

当日の一週間前から軽く練習を始めました。3年なので部活は休止してましたが、電車が来るまでの40分ほどでAOJ PCKの虚無埋めをしてました。前日は家で2018年の予選の難しい問題を解きました。9完できたので去年より成長したなあという感じです。

予選当日


去年は問題をよく読まなかったりサンプルを確認せずに提出してペナルティを重ねたので、今年はサンプルを全部確認してから提出するようにした。

問題1 緯度経度

La/3600,Lo/3600をそれぞれ出力。LatitudeとLongitudeというらしい。

問題2 商店街へのお出かけ

ヤエちゃんが辿り着けるとき(s \leqq m)1足して、タケコちゃんが辿り着けるとき(w - s \leqq m)2を足せば良い。

問題3 あいさつまわり

左端の座標をx、右端の座標をy、モチヒト君の現在地をmとすれば、min(m - x, y - m) + y - xが答え。

問題4 カラフル円盤通し

配列をreverse。初期値を0としてそれまでの最大値より真に大きければインクリメント。

問題5 写真の回転

写真を回転させる関数を作った。あとは回転数を数えて(1なら+1、-1なら+3)4で割った余りの数だけ適用させる。

この辺はよく覚えてないけど30分で5完したらしい。

問題6 テトラへドロン

color[i][j] = color[i-4][j-2]なので8通りだけ考えれば良いんだけど頭壊れるやつ。結局12パターン全部書き出した。これが一発で通ったのはかなり精神的に良かった。

問題7 加工機

最初素直に配列使ってやったらREになったので制約を見るとW, D \leqq 10^5だった。C \leqq 10^5なので削る区画を管理して、四方を見てどれだけ表面積が増えるか判断。区画が端にあるかどうかで場合分け。思ったより時間かからなかった。

問題8 高速道路網

最初dfsでやってTLEしたのでbfsでやった。トポロジカルソートのライブラリを印刷していなかったので、bfsでやるかーって実装したけど結局トポソになってた(は?)。ある頂点に辿り着いた時点での経路数C_iと経路長L_iをもっておけば、辺の終点でそれぞれ\Sigma C_i, \Sigma C_i + L_iと更新できる。WAになったので最大ケース(と思われる)を確認するとlongにすれば良いことが分かったのでそうする。


最初デバッグ出力を消し忘れていて、もう一度提出したんだけどジャッジが詰まってたので結果が分かったのは競技終了後だった。ここでWAだったらかなり悔しい思いをしていたので良かった。
問題9以降は見てない。

結果

f:id:season1618:20200916150211p:plainf:id:season1618:20200916150236p:plain


全体の解答状況
f:id:season1618:20200916150138p:plain
3と7の正答率が低いなあという印象。
実力枠じゃなかったのでちょっと不安だったけど、無事通っていたので嬉しい。ただで会津旅行行けないのは残念だけど。

感想

去年の教訓を活かすことができたので良かった。実際去年が7完6ペナだったので成績は良くなった。あと結局自分が全部ACしたけど、後輩も自分の後に通してて凄いなあと思った。