ICPC2020の模擬国内に参加しました
結果は全体57位で学内1位、選抜35番目のチームでした(ギリギリなので本番はまだまだ怖いですね)
コンテスト前
大学の研究室で集まってコンテストに出ることに、メンバーは mint さん longrun さん、僕の3人チームです
longrunさんとは初顔合わせでした
研究室内のクソデカモニタやマウスを少しずつ借りつつコンテスト準備
しーあるさんに毒を盛られた以外に変な事は起きませんでした
本番
戦略はAをlongrunさん、Bをmintさん、Cが僕を叩いて、その後は適当に進む感じに
Cがなんだか難しそうで許してくれ〜〜〜〜となる チームメイトに予防線を張っておく
Aが少しバグっているようでBが先に通る、入力受け取りがバグっていたようでmintさんとペアコーディングをしてAも通る
Cのdpの方針を思いつく、スタートに対してゴールが右下にある場合、最短移動である必要があるため下方向か右方向にしか動けない事から、
正方形の上辺もしくは右辺を通過した際に+1をするように右か下に移動する遷移を立てて、各点の最小値を求めれば良さそう
しかし点90度回転の方法を思い出せず(理系大学生失格！)
mintさんがDを考えていたので、手が空いていそうなlongrunさんに90度回転のメソッドを作ってもらう
チーム開発素晴らしすぎる…
dpの遷移が作れた辺りでlongrunさんの回転メソッドも作れたのでそれを使ってそのまま提出、AC
この時点で15~20位くらいでかなりいい調子
その後Dの途中考察を聞いてみるも苦手なやつっぽくて不可能を感じる
説明を聞きつつEを見ると不可能を感じた、おわった…
なんかDは一応解法が出来てるっぽくて、順位がまだ良いのでとりあえず提出してもらうもWA
3人同じ問題に張り付きも微妙っぽいので、このあたりでDはmintさん、Eは僕が張り付いてlongrunさんは主にDを見つつ時々Eを聞いて貰う形になる
とりあえず正攻法でなにも思いつかないのでN2 Mの8 * 109 の解法を許容しつつ考察する
なので全ての(i,j)の区間について可能かどうかを確かめる解法を推し進める
まずQ(a),Q(b)の時はa,b共に使用不可能、P(a),Q(b)の時、aが使用不可能ならQ(b)が使用不可能、最期にP(a),P(b)についてどちらかが使えるならOK、どちらも使えないならNGの解法をとりあえず書いてみて提出、WA
P(a),P(b)の時に、どちらかが使えない場合、もう片方を使わざるを得ない場合の考慮を忘れていた
この後2*M+1つの頂点を持つ二部グラフもどきP(x)用の点とQ(x)用の点+繋がっていたら駄目点の連結状態を使えば行けるのでは？みたいな戯言を言う
残り10分ぐらいで自分で書いててもどうしようもないのでlongrunさんにunion-findライブラリを写経してもらいつつその方針を進めるも間に合わず終了
感想
尻があったけぇ… 最初の三十分くらいでコンテストが終了してしまった
Cまではかなり順調だったものの、D,Eの高難易度で壊滅 チームとして高難易度殴り力をもう少し高めないとなという感じでした
