かっつのメモ帳

主に競プロ　時々日記

ICPC 模擬国内予選2021 参加記

コンテスト参加記

今年も Give us sociability (Kattu, Hyado, hotman) で組んで参加しました。

チームの様子

  • Hyado→前日にワクチンを打って頭痛と目眩に苦しむ。
  • hotman→連絡が来なかったので当日話を聞きに行ったら出場のモチベは低そう。
  • かっつ→課題に追われて大変だが、俺が頑張らないとヤバそ〜。

コンテスト

ぬるっと開始。

例年僕がA問題をやっていたが、今日のHyado君に無理はさせられないのでB問題を担当することに。

2分探索をやるだけだったので早々に書き終わったので提出する。するが、反応が無かったのでクリックし損ねたのかな？と思い、再びクリックするとそこには Wrong Answer の文字が。かなり焦る。が、提出画面に戻るとデータセット2に変わってたので、これ絶対データセット1で2回送信されただろ〜〜〜〜〜とキレながら再実行してAC。

A問題をHyado君がバグらせている。副作用辛そう。。なんとか通る。

C問題は見るからにメモ化しながらDFSやるだけなので僕がやると言って、D問題以降の読解をHyado君に任せる。やるだけだったのに、L字型ブロックを置く遷移の見落としがあり、大幅にロスってしまった。大反省。

この時点で順位表を見ると50位だったので絶望、ライバルチームの UHISHIRO や MSB は10位台で既に4完していて更に絶望した。


DをHyado君が読んでいて、Eを読むことにする。

が、先にDをやった方が良い気がして問題概要を伝えて貰った。

整理すると2つの文字列を一致させる最小コストを求める問題になり、行える操作は区間反転で、コストは長さの2乗がかかる。話を聞いて割と早い段階で、左から見ていって、反転により文字列が一致するような最も短い区間に貪欲に操作を行って良いのではないか？という考えに至る。

この後、正当性検証で20分ぐらい議論したが、この時間でサクッと実装しても良かったかもしれない。初めはローリングハッシュで文字列一致判定をするつもりだったが、愚直にループを回そうと思い実装。実行爆速で草、とか言ってると無事通って一安心。


Eの初感は流石に左や右の端から揃えたい。

1回の操作で減らせる転倒数の理論値は、(選んだ区間の長さ-1)で、順列に対して操作を行うので左や右に揃えていく方法はこの理論値を達成する。ライバルチームが5完してる焦りもあり、深く考えず左から順番に揃えてくコードをHyado君に実装してもらうも、WA。

ある境界 x が存在して、xより小さい値は左に揃えるのが、それ以外は右に揃えるのが最適になるのではないか？→それを全て試すコードを出すも、WA。

操作回数の最小化をすれば良い事に気が付く。それを踏まえてもう一回嘘貪欲を投げる→WA。

冷静になる。最小化を考えるにはLISを取ってくれば良いですね〜〜→AC。


ライバルチームは既にFまで通してる。何とかFを通したいがパッと見筋の悪いDPしか思いつかない。

まあ取り敢えず手を動かすか、と筋の悪そうなDPをHyado君の考察を聞きながら実装していく。実装していくにつれ、あれ？もしかしてこれで上手くいってるのか？という気分になってきて、ダメでもしゃあないと出したデータセット1が通った時、確信に変わった。AC。

コンテスト終了。

結果

6完31位。

ライバル2チームが15位と18位なので悔しい結果に。

反省

  • 普通に各問題に時間かかりすぎだった。
  • 解法の議論が出来るのがチーム戦の利点だが、もう少し比率を考えても良かったかも(今回は相談相手のHyado君が弱ってたので特殊ではある)。
  • Hyado君がWAした時の出力をちゃんと手元に残してるのとても偉かった。
  • 本番には万全な状態の3人を揃える。

お疲れ様でした会

競プロやった後にご飯食べに行く奴を久々にやれて、嬉しい！

後輩分は頑張って奢るので今後ともよろしくお願いします。

感謝

JAGの皆様コンテスト開催ありがとうございました。

コーチ

今度は一緒にラーメン食べに行きましょう。