ICPC 2023 国内予選参加記

ICPC 2023 Asia Yokohama Regional 国内予選に Aobayama_doctors として出ました．

チームについて

チームメンバー

チーム名の doctors の由来は「医者になる人」×2 + 「博士になる人」×1 から．

当日まで

私と Ryota が学業で多忙だったため，チーム練習はほとんどできず模擬予選のみ．圧倒的に練習がたりず，模擬予選の結果も不安が残るものだったため焦っていた．事前に決めていたことは，幾何と構文解析が出たら私が担当することくらい．実装力に自信があったので，重そうなやつは引き受けるとも言ってあった．

主な使用言語が私が Python で私以外が C++ だったので，ライブラリはそれぞれが持っていくことにした．

当日（コンテスト開始前）

14 時頃に会場となる研究室に到着．各チームが集まって場所決めをした後にプリンターのチェックをして，リハーサルをした．

その後序盤の立ち回りについて話し合った．元々 A,B 問題を私以外の二人に任せて私が C 問題以降を考察することにしていた．だが，模擬予選の序盤がうまくいかなかったこと，FA を取ると企業賞が貰えること，去年の ICPC の B 問題を数日前に私が Python で解き直したら結構素早く書けたことが合わさって，A,B 問題を私が担当することに急遽決めた．

リハーサルの後結構時間があって落ち着かなかったので，他のチームの人やこたつがめさんとしゃべっていた．

暇だったので，パソコンの目の前にこたつがめさんをお守り用に置いておくことにした．（コンテスト中はすっかりこたつがめさんの存在を忘れており，こたつがめさんの存在を再び思い出したのはコンテスト後だったんだけどね......）

コンテストについて

A 問題

Python を使える環境を整えた後，FA を狙って爆速でコードを書いた．やるだけなので 30 秒くらいで書き上げて AC（2:54）．一秒差で FA を取れていた．やったね！

B 問題

あみだくじをみて，TUPC の J - AMidA を思い出した．問題文の読解に苦労して題意をつかむのに時間がかかった．やることは追加する場所が O(NM) 箇所あるのでそれらを全探索する．各追加場所に対して O(N+M) で結果が分かるので全体で O(NM(N+M)) ．Python のスライスを使うと実装がちょっと楽になっていいね．AC （17:39）．

def solve_amida(n,xs):
  P=list(range(n))
  for x in xs:
    P[x],P[x+1]=P[x+1],P[x]
  return P

while True:
  n,m,p,q=map(int,input().split())
  if n==m==p==q==0:
    exit()
  X=list(map(int,input().split()))
  X=[i-1 for i in X]
  p-=1
  q-=1
  first=solve_amida(n,X)
  if first.index(p)==q:
    print('OK')
    continue
  ans=[]
  for j in range(m+1):
    for i in range(n-1):
      X2=X[:j]+[i]+X[j:]
      res=solve_amida(n,X2)
      if res.index(p)==q:
        ans.append((i+1,j))
  if ans:
    print(*ans[0])
  else:
    print('NG')

C 問題

私が A, B を解いている間に二人が C の考察を進めてくれていたが，やや詰まっていたらしい．Dispersion さんがコード書いて実験したいとのことなので席を譲り，私と Ryota は紙で考察をしていた．Ryota がマス目を市松模様に塗って黒のマスを適当にシフトする方針を思いついていて，これが筋が良さそうだと思ったのでもう少し考察を詰めた．半分くらいずらすといけそうな気がしたので Dispersion さんから席を譲ってもらい実装．

( N=5 の場合． x+y が奇数のものだけを順番にシフトした．)

00 01 02 03 04       00 13 02 15 04
05 06 07 08 09       17 06 19 08 21
10 11 12 13 14  -->  10 23 12 01 14
15 16 17 18 19       03 16 05 18 07
20 21 22 23 24       20 09 22 11 24

これが正しいかどうかを判定するコードを書くと N が 4 の倍数のときだけ合わないらしい．Ryota が N=4 で合わない理由をすぐに教えてくれたので，試しに N が 4 の倍数のときだけ奇数行目を反転してみるとなんか合った．

( N=4 の場合．シフトしたのちに奇数行目を反転させた．)

00 01 02 03       00 09 02 11       11 02 09 00
04 05 06 07  -->  12 05 14 07  -->  12 05 14 07
08 09 10 11       08 01 10 03       03 10 01 08
12 13 14 15       04 13 06 15       04 13 06 15

無事 AC（48:44）．

D 問題

C 問題の実装で手こずっている間に Dispersion さんがほとんど考察を終わらせてくれていた．答えが 7 以下になるのを見抜いていて，答えが 6 以下かどうかを全探索すればよさそうとのことだった．大雑把な計算量が 100^5/120\times 100\times 6 くらいで Python だとやばそうだということになり，C++ で bitset を使って実装することにした．Dispersion さんが実装することになったが，実装方法に苦労していそうだったので途中からずっと横で見て適宜口を出すなどをしていた．実装ミスもほとんどなく，デバッグもほとんどせずに AC（73:21）．Dispersion さんとハイタッチして喜んだ．この時点で大体 10 位．

E 問題

初手で引いた方針が悪く， O(N^3) からずっと落ちなかった． dp\lbrack i\rbrack \lbrack x\rbrack \lbrack y\rbrack で i 番目の人が解いた数が (x,y) のときの最小の変更コストとするとして，高速化とかもいろいろ考えたけどダメだった．

F 問題

E の考察がなかなか進まないので途中から F も並行して考えていた．多角形の凸法に含まれない部分について，その両端の 2 つの辺が平行じゃなかったら不可能，そうじゃないときは可能になりそうだと Dispersion さんが予想して，これが正しそうに感じたので実装．幾何ライブラリの凸包とかを写経して，サンプルがあったので提出したが WA．なにがいけないのかわからずそのままコンテスト終了．

結果全体 19 位（大学内 1 位）．予選突破できた．

コンテスト後

チームメイトと反省会をした．E,F は解けなかったものの，D までのムーブがほぼ完ぺきでよかったねとお互いを褒め合った．三人がそれぞれ活躍していて，チーム戦のよさが出ていてよかった．

そのあと他のチームと軽く感想戦をした．E 問題の想定 O(N^2) 解法を 1 年生が思いついてすげ～～と感動していた．言われてみれば典型だけど気づけなくて悔しい．F については条件が不十分だと指摘されて確かにとなった．

（追記）F は方針自体は合っていそうで，私の実装が間違っているだけな気がしてきました．

サークルで解散した後は打ち上げをした．

感想

去年惜しい結果で予選敗退していたので，今年初めて横浜に行けて凄いうれしい！学業がやばくて横浜の対策は全くできそうにないので，横浜は楽しむことを第一にしていければいいかな～