ICPC国内予選 2022 参加記

2022/07/08に開催された国内予選にチームAobayama_dropoutで参加しました。模擬国内予選の参加記でも書きましたが、今年のメンバーはha15さん・ホスフィンさん・僕です。

これも模擬国内と同様、ホスフィンさんが確保してくれた大学の演習室から参加しました。

序盤の戦略はホスフィンさんがA、ha15さんがB、僕がCを読むというものでした。以降の問題については、とりあえず皆で考え、解けたら誰か一人に実装を任せて残りは先に進むというような形にできればなと思っていました。以下に見るように、今日はそれどころではなかったのですが……。

問題文：https://icpc.iisf.or.jp/past-icpc/domestic2022/contest/all_ja.html

今年は特にネットワークに問題もなく、時間通り始まって問題文もすぐ読むことができました。

C問題

能力の増分は、日連続すればとなるように定められています。特に、練習計画においては練習日と休憩日がそれぞれどれだけ連続しているかにだけ興味があって、その順番は特に関係ありません。

練習日の連結成分が個ある場合、休憩日の連結成分は個のどれかなので、この組を全探索できます。中途半端に偏らせる必要はなさそうなので、練習日と休憩日のどちらかは連結成分を一つだけできる限り大きくし、もう一方は全体にまんべんなく割り振るのがよいでしょう。

連結成分が二つだとして、両方の戦略で能力の増分（の絶対値）がどれくらいになるか比較したところ、前者のほうが大きくなるようでした。よって、練習日はほぼ連続のところ一つだけ連続することになり、休憩日は基本連続、うち個はとなります。

これを実装します。またはの場合を先に処理しておき、がを満たすように全探索して、上の戦略を用いた時の能力の増分を計算しました。サンプルが合ってそのままAC。7分40秒でFAでした。

D問題

A問題も少し前に通っていました。一方B問題では詰まっているようでしたが、聞いてみると「解けるはずだが実装がよくわからない」ということだったので、僕が読む必要はないと判断し、ホスフィンさんにヘルプに入ってもらうことにして一人だけ先に進みました。

D問題を読みます。結局マージソートをしているため、列の一部を切り出す度にそこまででちゃんと望む順番に入場できているか判定してよいことがわかります。つまり、まだ分割していない部分の影響で順序が入れ替わることはないということです。ここで分割位置と分割回数を持つdpが思い浮かんだので、実際に書けるかどうか考えてみました。

今、インデックスの前までを本の列に分割できているとしましょう。まず、新しく列を追加したとき、ちゃんと望む順番の入場順になるかどうかですが、すでに「をにおける順番に並び替えたもの」があったところにをマージしたとき、「をにおける順番に並び替えたもの」が得られるか判定すればよいことになります。との値たちをいくらか大小比較すればできそうです。

またそのような、言わば「の遷移先となれる」は、を左端とした区間をなすこともわかります。つまり遷移が区間加算で書けるため、dpと同時にimos法を行うことで十分高速に計算できます。

大体解けた気持ちになりました。B問題は念のため二人で実装しているらしく、また上の考察は細かいところまで詰められていなかったので、人に投げるのをやめ、自分で書きながら考えてみることにしました。

の逆順列をとします。つまりです。インデックスを見ている瞬間、セグメント木には各について位置に値をセットしておきます。今、新たに列を追加したとすれば、マージ後にがの位置に来るためにはセグメント木の区間により大きな値がセットされていてはいけません。これは区間MAXを計算することで判定できます。

同様に、を考えているとき、先ほどの条件に加えてセグメント木の区間により大きな値がセットされていないことをチェックする必要があります。また当然ながらも必要です。このようなチェックを繰り返して追加できる限界を求め、それを用いて区間更新しました。

サンプルが合いません。しばらく考えて、より後ろにより小さな要素がある場合もまずいことに気づきました。ただし追加時点で列の先頭にいなければ大丈夫です。しかしこれは、判定が列の分割方法に左右されてしまうことを意味します。つまりこのままではdpができません。

一瞬目の前が真っ暗になりましたが、チェックのタイミングを変えることで一命を取りとめました。つまり、を追加できない原因を探すのではなく、がほかの何かの「追加できない原因」にならないか判定すればよいのです。が列の先頭にいるのはの間ですから、その区間で、にまだ出現していない値であって、より大きなものがないかチェックすることになります。

同様のチェックはについてを見るという風に全体で行うことになります。区間MAXを計算するセグメント木をもう一本生やして、こちらはまだ出現していない値をセットしておきました。条件を追加してもう一度サンプルを試すと今度こそ合い、提出してAC。28分57秒で、今度もFAでした。

E問題

2問もFAだったということでひとしきり踊り狂っていました。B問題は実装が佳境に入り、もう問題なさそうなのでE問題を考え始めました。

この問題は非常に難しかったです。まず初手でこれっぽいと思える方針がありませんでした。一応、フローらしさが感じられないこともなかったので、かなり長い間その考察と像の条件を絞っていく考察を交互に進めていました。結局フローではなかったのですが。

1時間くらい経過して、その時点で得られていた考察は、端の交差点に関するものだけでした。まず、調査員が帰還した道路は、最初が+で最後が-であることが確定します。逆にこのどちらかを満たさないように置けば、調査員が絶対に帰還できないようにできます。

これを念頭に置いて、例えばの場合を考えます。このとき一番北の道路はほとんど自由に決めてよいですから、各についてなら+を、なら-を置くのが最適です。の場合もなら+と決定しますから、である道路だけから個選んで-にすることになります。この選び方は東から貪欲に取るのがよいでしょう。の値を見れば、ほとんど同様のことが一番南の道路に対しても行えます。

ここからが一つ目のポイントでした。である道路のみを考えます。またはなら、最初に-を置かれたり最後に+を置かれたりして、すでに調査員が帰還できないと決まっています。ではならどうでしょう。一番北の道路では東から本に-が、一番南の道路では西から本に+が置かれています。すると、である道路は当然本以下ですから、これまたとのどちらかで調査員が帰還できないと決まっていることがわかりました。

結局、端に関する考察だけでは達成できています。同様のことをでも行いますから、残りは個の交差点でとを無事帰還させることさえ考えればよいことになりました。

ここで二つ目のポイントです。を市松模様に埋めれば、最初が+で最後が-なら必ず帰還できるようになります。これに気付いたときはかなり大きな衝撃を受け、思わず手を打ち鳴らしてしまいました。

実装に取り掛かります。とを見て端を埋めるコードを書き、それをコピペして向けに修正しました。この部分は明らかに、とを交換して同じコードを再利用したほうが良かったです。端を埋め、中を市松模様で埋めた後、四隅が矛盾している場合に備えて実際に各道路をチェックし、出力しました。それなりに苦労してサンプルを合わせ、いざ提出。しかしWAでした。

最後にチェックしているのですから、答えがYesのケースは間違っていません。つまり、YesなのにNoと出力しているケースがあるはずです。絶望しながら考察をもう一度辿っていると、やの場合の決め方があまりに自由すぎることに気づきました。の値に応じて決めた結果、うっかり帰還できてしまうケースが考えられます。

これを解決するためには、であるような道路を選んで切り替えればよいです。ですが、これを切り替えたせいで今度、その道路が帰還可能になったりはしないでしょうか？結論から言えば、そのようながあるならそもそも出力がNoとなります。場合分けで確かめられますが、実はこの事実は今気づいたことで、本番では適当な場合分けにより、であって一番東または西の道路を選んで切り替えていました。こうするとそこも帰還可能にならないことが言えます。

しかし、今度はそのような道路を切り替えたことで四隅が矛盾する可能性があります。そこで、まず四隅を2⁴通り全探索し、それ以外の部分を上のように決めたり切り替えたりする対象にすることにしました。コピペの結果実装が肥大化していて、苦しい書き換え作業になりましたが、何とか実装し切ってサンプルを合わせました。

先ほどWAを出したテストケースに対する出力がどのように変わったかチェックします。YesとNoの行だけを抜き出してdiffを取ると、見事に3ケースNoだったものがYesになっていました。これを提出してAC。2時間39分34秒でした。

コンテスト終了

残り時間、と言っても20分しかなかったのですが、その間はF問題のコーディングをしていました。

さすがにE問題だけに2時間以上没頭できていたわけではなく、途中で少しF問題を読んでいました。その時点でとりあえずメモ化再帰で答えが出せることはわかっていましたが、それほど高速には思えず、またE問題のほうに注力すべきだと考えて詳しく考えずに戻ったのでした。その考察を引っ張り出しとにかく実装してみることにしましたが、さすがに20分では何もできず、そのままコンテスト終了時刻を迎えました。

結果は5完13位です。学内1位を取って昨年の予選のリベンジこそできたものの、E問題で苦しみすぎて喜ぶ元気はありませんでした。5完したチームではちょうど真ん中の順位を取ってしまっていますから、D問題までのスピードが見る影もありません。上では触れませんでしたが、2問FAの後、B問題も無事通った時点では2位だったのです。

https://icpc.iisf.or.jp/past-icpc/domestic2022/common/guest_standings_ja.php.html

結局僕がCDEを実装してしまっています。しかしそもそも、そのような問題分担について考えられるような出来ではありません。いかなる戦略を取ったとしてもE問題が解けるのは前提になっていて、それが崩れた今回はもう……本当に大変でした。なぜ解けたのかがよくわかりませんが、九死に一生を得たような心持ちです。

まあ、戦略に関して思うところがないわけではありません。E問題に取り掛かった時点では順位表に一切の情報がありませんでしたが、それからしばらくしてE問題とF問題に同程度、むしろF問題のほうが多い瞬間もあったくらいACが出てきたのは把握していました。つまり今回、この二問の難易度にそれほど差がないことは分かっていたのでした。

僕自身はE問題を捨てるような気分になれなかったものの、例えば一人、F問題の考察に回ってもらうのは十分あり得た戦略かと思います。いや、実際にF問題も考えてくれていたのかもしれません。チームメイトが何をしているかは全く把握していませんでした。しかも解法は僕が考えた方針の先にあるものだったため、余計にもったいなさを感じます。これは結果論ではありますが。

E問題を通してからF問題の自分の考察を開陳したのですが、コンテスト後にチームメイトに考えていたことは共有してくれと言われてしまいました。これは全くその通りです。チームメイトが何に取り組んでいるかを把握しようとしなかったのも合わせ、自らワンマンチームにしようとしているようなものなので、意識を変えなければなりません。