ICPC2020国内予選 参加記
こんにちは，モジャンボです．
sim(simkaren)，モジャンボ(Mojumbo)，じゅっぴー(juppy)の3人でチームSiMoJappyとしてICPCの国内予選に参加しました．去年結成したチームで，ICPCへの参加は2回目になります．
模擬国内がうまくいって12位だったので，あわよくばアジア地区大会(´イωク｀)ε-(/･ω･)/三┏( ^o^)┛٩(・ω・)วlet's go!という意気込みだったのですが，結果は38位で予選通過ならずでした．残念…
コンテスト前
開始30分前にZoomに集合．コミュニケーションはZoomとSlackで行った．
ここしばらくは
A:じゅっぴー
B:sim
C:モジャンボ
の分担で固定していたが，前日の通話で2人が構文解析に自信なしということが分かったため，もしDかEに構文解析が出たらCはじゅっぴーに押し付けて自分が構文解析をやることにしようと提案した(そしてほんとにDで出た)．
コンテスト
コンテストページにつながらない．そのうちアナウンスがあるでしょと思ってダラダラしゃべってたらヌルっと始まる．
D問題が構文解析なので打ち合わせ通りこの問題に取り掛かることに．Dの構文解析なんて実装するだけだろうと高をくくっていたが，普通に構文解析以外のパートが難しくない…？
苦しんでいる間にじゅっぴーとsimがABを通してC問題を相談しているのを何となく聞きながらDを考える．でも本当に何も分からない．(20分)
じゅっぴーが約数を全列挙して約数のペアを全探索でどうかというのが聞こえてきた．怪しいけどICPC的にはよさそう．
simが3つの約数のうち1番小さいもの(O(N^(1/3)))を全探索でどうかというのが聞こえてきて，それなら実装軽そうだし俺書きます！と言ってDから逃げる．
1番小さい約数は全探索するとして，残り2つは…？うーん，全探索！ｗをしたら実行があまりにも遅い(当然)ので適当に枝刈りを入れたら今度は1分くらいで実行できた．これがICPCなんですね．(40分)
Cを提出して帰宅すると，simがDよりもEの方が希望があると言うので相談しながら解法を生やす．
sim「奇数行と偶数行は独立に考えられて～」
モジャンボ「ｽﾞｻﾞｻﾞｧｧｯ≡______(┐「ε:)_それな」
sim「偶数行だけを抜き出すと，対角に並んだマスを同時に取れないから二部グラフの独立集合の数え上げみたいな」
モジャンボ「☜╮(´ิ∀´ิ☜╮)ﾔﾙﾈ-」
なんやかんやでbitDPができる制約まで落とせることが分かったので，実装する．スルスル考察が進んで気持ちよかった．参加記もこの部分だけ書きたかった．
とりあえず雑に2^15通りの状態から2^15通りへの状態への遷移を書いてDPすると実行が終わらないので，遷移先をDFSで列挙する(これで4^15から3^15に落ちたような気がする)と無事AC．(2:00)
帰宅すると，Dはやっぱり分からなくてFはできるかもみたいな状況らしいので，2人にはFをやってもらって自分はDを考え直すことに．
自分は1時間椅子を温めて，Fもバグが取れない？っぽくて4完で終了．さよなら…
感想
反省すべき点は多分立ち回りにはなくて，単純に個人としての力不足を痛感した．
特に構文解析は自分の担当なのに大量に通されているDが通せなかったのは猛反省．
来年の国内予選までにはAtcoder橙になっておきたい．
sim(simkaren)，モジャンボ(Mojumbo)，じゅっぴー(juppy)の3人でチームSiMoJappyとしてICPCの国内予選に参加しました．去年結成したチームで，ICPCへの参加は2回目になります．
模擬国内がうまくいって12位だったので，あわよくばアジア地区大会(´イωク｀)ε-(/･ω･)/三┏( ^o^)┛٩(・ω・)วlet's go!という意気込みだったのですが，結果は38位で予選通過ならずでした．残念…
コンテスト前
開始30分前にZoomに集合．コミュニケーションはZoomとSlackで行った．
ここしばらくは
A:じゅっぴー
B:sim
C:モジャンボ
の分担で固定していたが，前日の通話で2人が構文解析に自信なしということが分かったため，もしDかEに構文解析が出たらCはじゅっぴーに押し付けて自分が構文解析をやることにしようと提案した(そしてほんとにDで出た)．
コンテスト
コンテストページにつながらない．そのうちアナウンスがあるでしょと思ってダラダラしゃべってたらヌルっと始まる．
D問題が構文解析なので打ち合わせ通りこの問題に取り掛かることに．Dの構文解析なんて実装するだけだろうと高をくくっていたが，普通に構文解析以外のパートが難しくない…？
苦しんでいる間にじゅっぴーとsimがABを通してC問題を相談しているのを何となく聞きながらDを考える．でも本当に何も分からない．(20分)
じゅっぴーが約数を全列挙して約数のペアを全探索でどうかというのが聞こえてきた．怪しいけどICPC的にはよさそう．
simが3つの約数のうち1番小さいもの(O(N^(1/3)))を全探索でどうかというのが聞こえてきて，それなら実装軽そうだし俺書きます！と言ってDから逃げる．
1番小さい約数は全探索するとして，残り2つは…？うーん，全探索！ｗをしたら実行があまりにも遅い(当然)ので適当に枝刈りを入れたら今度は1分くらいで実行できた．これがICPCなんですね．(40分)
Cを提出して帰宅すると，simがDよりもEの方が希望があると言うので相談しながら解法を生やす．
sim「奇数行と偶数行は独立に考えられて～」
モジャンボ「ｽﾞｻﾞｻﾞｧｧｯ≡______(┐「ε:)_それな」
sim「偶数行だけを抜き出すと，対角に並んだマスを同時に取れないから二部グラフの独立集合の数え上げみたいな」
モジャンボ「☜╮(´ิ∀´ิ☜╮)ﾔﾙﾈ-」
なんやかんやでbitDPができる制約まで落とせることが分かったので，実装する．スルスル考察が進んで気持ちよかった．参加記もこの部分だけ書きたかった．
とりあえず雑に2^15通りの状態から2^15通りへの状態への遷移を書いてDPすると実行が終わらないので，遷移先をDFSで列挙する(これで4^15から3^15に落ちたような気がする)と無事AC．(2:00)
帰宅すると，Dはやっぱり分からなくてFはできるかもみたいな状況らしいので，2人にはFをやってもらって自分はDを考え直すことに．
自分は1時間椅子を温めて，Fもバグが取れない？っぽくて4完で終了．さよなら…
感想
反省すべき点は多分立ち回りにはなくて，単純に個人としての力不足を痛感した．
特に構文解析は自分の担当なのに大量に通されているDが通せなかったのは猛反省．
来年の国内予選までにはAtcoder橙になっておきたい．
