ICPC国内予選にmintさん、longrunさん、僕の三人でnoborito290yenとして参加しました
結果は全体37位、学内1位で不正がなければ追加です、shop_oneが沢山居るので不正が怖いです
〜前日
ICPCのチーム紹介の所にshop_oneが沢山出てきた、治安最高大学か？
(チーム)shop_oneのしーあるさんと勝負して勝ったほうが焼き肉を奢ることに、どうして？？？？？？
shop_oneへ
— しーある (@cs_c_r_5) 2020年11月5日
勝った方が焼肉奢りでどうですか
shop_oneより
当日コンテスト前
適当に待ち合わせをして昼食と買い物をする、百円均一にサイコロを探したが無かった
結局longrunさんが紙でサイコロを作成していた
同大学のGenius Takano -Forever-チームと同じ部屋でコンテストへ
コンテスト開始
鯖落ちした後ログイン出来なくなって焦る、なんかリハの開催予告が始まったりリハが始まったりして笑う、その後唐突に始まって滅茶苦茶ビビる
取り決め通りAはlongrunさん、Bはmintさん、Cは僕で読み始める
例年であればCは少しの考察とそこそこの実装問題なのでこの取り決めだったのだが、どう見てもAtCoderで絶叫した
マジで何もわからないので数学方面に強いlongrunさんの方を待つ、Aが終わりそうだったので一緒に見て確認してOKを出して投げてもらった AC
Cの概要をサッと説明してみると仮の方針が出てくる、いつもなら実装してたけど数学が分からないので方針ミスが不安で、数学系なら実装は重くならないかなと思って実装を任せる
mintさんがBが簡単過ぎて不安と言っていたので空いてる僕が見に行って確認、色々つっついて問題が無いことを確認して投げてもらってAC
Cを任せてる間にD,Eを見る、Dは構文解析と聞いてウキウキ、俺の愛したICPCはこれだ！
Eは数え上げで絶望、俺の愛したICPCよ…
そんな間にCが書き終わったものの滅茶苦茶実行が遅い(後で聞くと本番中コンパイルオプションで最適化を全部殺していたらしい)で困る
一応こちらでコードを実行しつつ、一緒にCを考える
10分くらい？でこちらのコードが実行終了するもののその頃に新しい解法がlongrunさんから上がる、もう一度+10分だと流石に怪しいのでそっちを進めてもらう
この時点で50分位立っていて、3完突破は怪しくないか？となりCは任せてDを本格的に殴りかかる
構文解析は本質で無いとなり涙、n <= 16で階乗は無理、まず決め打ちをするんだろうな〜となる
もう一度制約を見直すと2nの計算量を使う解法が良い解法になりそう bitdpが頭をよぎるが不可能と却下
mintさんが考察途中でちらっと言っていた、決め打ちした文字Aに対しての他の文字の大小をsetで管理するみたいなことを思い出す
今回は大小比較を常にしているので、Aより大きい、もしくは小さいで分けれそう、これ2nじゃ〜〜〜ん♥となる(この辺りでCが通った気がする)(こちらに集中していてタイミングを覚えていない)
結局構文Eの返り値はAより大きい、小さい、Aそのものであることが分かるので、あとはやるだけっぽい
あとは好きな構文解析だけなので、ペアコーディングでバグを見つけてもらいながら書き始める
意外と焦っていてわりとバグを埋め込む sとsの文字を比較していたりした なんで焦ってたのかよく分かりませんね
バグらせつつもプログラムが完成、2セット合わせて5分くらい？実行してAC ガッツポーズをキメる
流石に予選突破か？となる
2人はFを見ていたので逆張りでEを見る、かぞえあげなのでわかりません
なんか睨んでいると、全てのマスは4つのパターンに分けられそうということが分かる(これもしかして市松模様ってやつですか？)
すると、3次元dp(i、jに桂馬を置く、置かない)を上の方から計算できそう
とりあえず書いてみるも最終的な答えをどうすれば良いのか全くわからない
数え上げが得意らしいlongrunさんに聞いてみると包除原理が使えそうらしい、包除原理できん…
結局分からず、二部グラフとかもう一つdpを左から右へやるみたいな事を考えるも脳が爆発して分からずコンテストが終了してしまった
感想
(自称)ICPC特攻持ちイベントキャラだったので何とかDを通せてホッとしました
ただかなりDをバグらせてしまったのは反省点です、mintさんありがとう
また、Cが全く分からずほぼlongrunさんに投げてしまったのも反省点です、longrunさんありがとう
始まる前から一人欠けると壊滅みたいな事を皆で言っていましたが、終わってみると本当にそんな感じでした
それでもDが(一応)方針立てて通せたのはよかったです こういうのが得意であるので
チーム戦はやっぱり楽しいですね、今回は同じくらいの実力でlongrunさん考察、mintさん実装、僕インチキで得意が分かれてるのでお互いに支え合ってる感じがしました
精神的にも、現在のレートでは僕が一番高いわけではなく、年齢も一番下なので素晴らしい先輩たちに助けてもらえると思ってかなり気楽に望めました
本番で壊滅するタイプではないつもりでしたが、AtCoderのレートが暫く壊滅した過去を思い出したので、レートを理由にmintさんにエースを押し付けていました
アジア予選も頑張ります！
余談
これは勝利の飯と僕が奢らされる予定のしーあるさんの飯 pic.twitter.com/u1wwIsnzzh
— 店長 (@_shop_one) 2020年11月6日
♥最高の先輩♥かけがえのない存在♥本当にshop_oneに飯を奢らせました
— しーある (@cs_c_r_5) 2020年11月6日
