ICPC模擬国内予選 2020 参加記

2020/10/25に開催された模擬国内予選にチームAobayama_dropoutで参加しました。メンバーは変わらず碧黴さん・ゆきのんさん・僕です。

今年はコロナの影響で特別ルールが設定されました。模擬国内予選も基本的に同様のルールに準拠することになります。最も大きな変更点としては、1人1台マシンを使用できることでしょうか。あとはモニタに関する制限がなくなりましたが、まあ正直なくてもいいかなという感じです。

Wi-Fiの設定に手間取り、コンテスト開始からちょっと遅れて問題文を読みます。碧黴さんとゆきのんさんがABCを担当している間に、僕はDを読みます。これはどうなんでしょう、3人がそれぞれABCを担当したほうが初動的にはいいのかもしれません。

D問題(途中C問題)

Dはかっこ列の問題です。これが全然わからない。とりあえず普通のかっこ列を目指して、それをもとに考えることにします。

その間にC問題を読んでいたゆきのんさんからヘルプが来たので、僕もC問題を読みます。スタートとゴールの位置関係が固定されていないなど嫌な気分になりますが、まあ実装するのは僕ではないので、とりあえず考察を投げます。

斜めの最短経路を移動していく際、移動できない区画というのは正方形なので、入ってから一度出たらもう二度と戻ってこないということが言えます。なので、どの正方形を通ったかという情報はいらず、各移動に際して新しく正方形に入った個数だけカウントすれば、それがその移動のコストになり、あとは最短経路問題を解けばよいです。移動のコストに関しては、各正方形について辺をまたいで入る移動に1加えればよいです。区間になるので、imos法でできます。

スタートとゴールの位置関係を固定するためには、盤面全体を適切にrotateすればよいです。

これだけ考えて、実装をぶん投げました。後から冷静になると境界の扱いとか盤面全体のrotate(これはflipにしたようです)とかいろいろ大変そうです。実際大変なことになっていましたが、僕は以降ノータッチでした。

Dは何とか光明が見えてきました。普通のかっこ列を目指したとき、余ったパーツは))))(((((のような形をしています。元の文字列をうまく分けて、))))(((((に分かれるようにし、片方はかっこごと逆にします。分けたあと2つにまたがるようなペアは作らなくてもいいので、)が余る文字列をうまくマッチさせる最小個数の問題をそれぞれ解いて足せばよくなります。

)が余る文字列に対して解を計算します。連続する)を一気に処理することにします。まず(をあるだけマッチさせ、残った分は()にくっつけていきます。それでも処理しきれなかった分は(を新しく追加することでしかペアにできないので、答えに加算します。大体こんな感じのアルゴリズムでよさそうです。

ただし注意が必要です。____をマッチし切ったかっこ列とします。(____))は可能ですが()____)は不可能なので、())をくっつけようとしてもうまくいかないものがあります。具体的には、((()))____というものがあったときに、新しく)をくっつけられるのは2個までとなってしまいます。( [ {} ]] ____ ))です。( ( [ {}} ]] ___ )) ))になると4個くっつけられます。

このことを考えると、n重のかっこ(((...)))____ではfloor(n/2)*2個しか受け入れられないことがわかります。

こんな感じでstackをコネコネしてサンプルを試すと合います。テストケースを実行して提出するとAC。2回目も同様にACできました。50分くらい。

E問題

C問題がまだヤバそうですが、かまわずE問題に行きます。碧黴さんが問題を読んでいたので、概要を聞きます。条件が2つあってどちらかを満たせばよい、これは2-SATです。とりあえずその方向で考えます。

ここで頭がバグって、2-SATは2部マッチングを解けばよいと勘違いしてしまいます。辺を張ったときに増加道があるか見ればよい、と意気揚々と宣言して書きますが、正気に戻りました。

強連結成分分解ですね。辺u->vを張ったときに、xnot xが同時に属するような強連結成分を検出できれば良いです。これは各頂点から到達可能な頂点集合G_ubitsetで持っておき、G_u |= G_vで更新して、G_x cont (not x)G_(not x) cont xを判定すればよいですね!

WAです。それはそうで、a->u->v->bみたいなパスを全然考えられていません。最高にアホ。

もうちょっと冷静になります。SCCというのは辺Gと逆辺RGを持って計算します。u->vを張ったとき、uを含むような強連結成分は、uからGを使ってたどり着ける頂点とuからRGを使ってたどり着けるような頂点の共通部分となります。ここにxnot xが同時に含まれたら2-SATは充足不可能となります。

この判定はO(N)で、辺の追加はO(M^2)回あるので、全体でO(M^2 N)となります。MNは最大2000ですが、手元実行なのでぶん回してAC。100分くらいのことでした。

冷静になると、そもそもすべての強連結成分を検出するSCCO(N+M)でした。またしゃくとり法が適用できるので試す回数はO(M)になりますね。辺の追加と削除さえうまくすればO(M(N+M))になります。

そういえば、こうやってぶん回すとき、実行がどれくらい進んでいるのか気になりませんか?出力をファイルにリダイレクトしていると、そのファイルを覗き見するのにはちょっと気を使います。こんなときにteeコマンドを使うと、入力を標準出力とファイル書き込みに同時に出せるので便利でした。

F問題

C問題はWAを食らって大変なことになっていましたが、F問題を読みます。さいころを転がしています。勝ったな!

こういう実装やるだけ問題は、頑張って実装すれば頑張っただけ確実に成果が得られるので、大好きです。頑張っていきます。

まずサイコロ構造体を実装します。面があって、向きがあるので、6つの面にそれぞれ番号とどこを下にするかを割り振り、矢印の方向4つにも番号を割り振り、それぞれの面の矢印がどこを向いているかを持てば必要十分です。

次に読み取りを実装しようとしましたが、冷静になると先に回転を実装したほうが良いことに気づきます。

回転を実装します。まず縦と横で1方向ずつ作って、逆に回す代わりに順方向に3回回すことにします。回転するたびに6面それぞれの矢印が互いに移り変わったり向きを変えたりして大変です。こういうところでバグを埋め込むと後から再チェックが大変なので、絶対にバグらせないぞという決意を持つ必要があります。対称性がありそうですが、楽をしようとすると得てして勘違いでバグらせるので、全てのマジックナンバーについて必ずじっくり考え、1つ1つ丁寧にコーディングを進めます。

これで展開図上をサイコロが動けるようになったので、入力の読み取りの際は実際にサイコロを転がしつつ写し取っていく感じにします。物理的に考えると、現在真下にいる面に反転して写ることになりますが、この読み取りは全サイコロで共通なので、どの面にどのように写し取ろうと変わりありません。僕は真上にある面にそのままの方向で写し取りました。

各サイコロのペアについて、全ての状態を試し、それぞれに違いがどれだけあるかカウントして最小値をとればよいです。(縦回転x4+横回転)x4で試してみたところ、答えより小さな値が出てしまったので、デバッグをします。マジックナンバーに1つ違いがありました。

もう一度試してみると、今度は必ず答え以上の値が出るようになりました。この原因は簡単で、状態をすべて列挙できていないんですね。縦回転と横回転だけで再現する方法もなくはなさそうですが、一番手っ取り早いのは3つ目の軸周りの回転を実装することでしょうか。さっきの4x4ループの内側でさらに新しい回転を4回するとサンプルが合いました。

特に実行時間にも問題なく、AC!170分くらいのことでした。

僕がE問題を実装している最中にC問題もついにACしていたので、これで6完です。ペナルティが結構あります。あとはH問題が解かれていますが、あんまり考える気はないので、残り時間は適当に過ごしました。

総合11位、現役内10位、学内1位でした。