ICPC国内予選 2020 参加記

2020/11/06に開催された国内予選にチームAobayama_dropoutで参加しました。メンバーはいつもの碧黴さん・ゆきのんさん・僕です。

例年はサークル顧問の先生の研究室に集まって出場しているのですが、今年はコロナの影響で全員は集まれないとのこと、急遽マルチメディア棟の演習室を借りてもらったので、そこから参加します。

このあたりの事情を含めて、サークル運営としてのICPC参加記も書きたいと思います書きました。社会性をたくさん消費しました。

kotatsugame.hatenablog.com

コンテスト前

ノーパソのキーボードはストロークが浅すぎて慣れないので、今年はキーボードを別に持っていくことにしました。

今回も戦略としては僕が最初にDを読んで、その間に他の2人でABCを通す感じです。模擬国内の後にこれに関して少し話し合ったのですが、結論はうやむやになりました。

コンテスト中

しばらくページが見れない状態が続いていました。緊急事態だと思って同じ部屋から出場しているチームにも確認したところ、全員繋がっていないうえ、ポケットWi-Fiで接続している人も同じく繋がっていないので、向こうの問題だと確信し、待つことにしました。しばらくチームメイトと談笑していると、ヌルッとコンテストが始まりました。

D問題

読みましたが、全然わかりません。しかし僕がDを解かないというのはあり得ないので、あきらめずに考え続けます。とりあえずbit系の解法を考えることにしましたが、bitDPはどうにも情報が足りないので使えません。

もうしばらく考えていると、文字をグループ分けするとよさそうなことがわかります。具体的には、文字集合を2つに分割して片方がもう片方より必ず大きいとし、この状態で構文解析すると、文字列の評価値がどちらのグループに属するかわかります。このとき、評価値にならないほうのグループはどのように並んでいても関係ないこともわかります。

つまり、毎回サイズを半分にしながら同様の問題を解いていけばよさそうです。comb(16,8)*comb(8,4)*...を計算するとかなり小さかったので、この方針で実装します。

mapに正か負の値を入れて、各文字の評価値とします。このとき値の絶対値を2**文字集合のサイズとして再帰の階層ごとにユニークにしておきます。本当は±1でよいのですが、念のため意図しない値が評価値となったときに検出できるようにしておきたかったからです。

残りは最も簡単なレベルの構文解析なので、特に問題はありません。ただ対象となる文字列が2つあります。一瞬、関数を2つ用意しようかとも考えましたが、string::iteratorを渡しておけば1つの関数で対応できます。

テクニックとして、例えば今回の問題では</>とmin/maxのどれがどれか考える必要はないです。結局順序を全通り試しているからです。

D問題が通ったのは40分過ぎで、その間に他の2人はABCを通してE問題を読み始めていました。

E問題

E問題を読むと全然わからないので、F問題をチラ見します。直感的に後ろからUFで連結成分を管理しつつ最大連結成分を持っておけばよさそうだと思ったので、その方針で実装してしまうことにしました。チームメイトに伝えて実装し、サンプルが一発で合ったので提出しましたがWA。よく見ると考察していたことが全然実装できていないことに気づいたので、コードを書き足して、出力が変化したことを確認して再度投げましたがこれもWAでした。

Fを書いている途中にゆきのんさんがE問題の解法を生やしていました。縦横を逆にしたら2^(60/4)になるというものです。どう考えても天才の解法で、明らかに合っています。遷移が2^15になりそうですが、適切に畳み込めばよいです。太鼓判を押すだけ押して実装をしてもらっていましたが、どうにも行き詰っているようで、僕自身FがなぜWAなのかもわかっていないので、改めてE問題を書くことにしました。

bit列と行番号を対応付けるのがかなり難しいですが、この辺りは4通りしかないので2人にそれぞれ求めてもらうことにして、遷移の部分を書きます。かなり時間がかかりましたが、とりあえず書けて、サンプルを試します。何一つ答えが合いませんでした。このあたりでコンテスト開始2時間くらいです。

しばらく格闘していると、遷移に関係する縦のマス目の個数とスタート地点が違うことに気づきました。直すとサンプル1と2が合いますが、3番目は合いません。

入念にコードをにらみつけていましたが、どうにも実装におけるミスが見つからないので、考えたことが間違っているのではないかと疑います。これは当たりで、畳み込みが全然できていませんでした。適当に書き直すとサンプル3も合ったので、提出。WAでした。残り30分です。

サンプルが合って通らない絶望感がヤバいです。相変わらず実装におけるミスはなさそうでした。さっき書き直した畳み込みを疑って、もう少し大きなケースでどういう遷移をしているか想像してみると、明らかに変な挙動をしていそうなことに気づきます。縦の長さが4分の1になるので、そこそこ大きな入力でないと影響が出なかったようです。

間違っていることはわかりましたが、正しい畳み込みが思い出せません。ゆきのんさんがローカルに落としておいた数人の競プロerのライブラリから探してみると言っていましたが、何変換か名前がわからないので見つからないようです。

しばらく唸っていると、何となく「j⊃iなるjに対してdp[j]+=dp[i]」をO(N 2^N)で行うコードっぽいものを思い浮かべることができたので、書いてみます。ちなみにこれまでの実装では⊃ではなく⊂だったので、毎回bit反転します。

サンプルを試すと通り、また先ほどのコードから出力が変化していたので、提出しました。ACでした。コンテスト終了10分前です。このAC自体はかなり遅いのですが、Dまでがそこそこ速かったので、5完内の順位は結構上がりました。

そのあとはF問題の先ほどのコードを少し変えて提出してみましたが、相変わらずWAでした。終了直前に、そもそも途中でセグフォして答えが出力できていないことに気づきましたが、提出はできませんでした。

コンテスト後

セグフォに気づかなかったショックでまともに受け答えができなかったのですが、気づいたら同じ部屋のチームはすでに帰宅していました。この演習室ももう閉めるということで出ます。

チームで打ち上げをしました。

帰宅して、上がっていたFのACコードと出力を突き合せたところ、めちゃくちゃdiffが出たので気が楽になりました。

Dは2分割じゃなくて3分割すると、文字列の評価値を決め打ちして解けるようです。評価値決め打ちはちょっと考えたのですが、文字集合の分割を思いつく前でした。

振り返り

Fは完全にカスでした。一人で勝手に読み始めてふんわりした考察で実装して投げてWAを出すというのはチーム戦においては最悪です。まだ何が違っているのかも分かっていません。

毎年D問題もそんな感じで僕が一人で抱え込んでるんですが、そっちは戦略です。とりあえず僕が最初にDを解いておけばまともなペナルティで四完ができて、東北大学から出場しているなら国内予選を通過します。3並列である今年はまた違った戦略を取る余地もあったかもしれませんが、マシンが1台だと実力を鑑みてこれが最適です。必要なのは何が来てもDを通すという自信・自負・実力と、AからCを任せられるチームメイトです。