ぷ～べあさん(Twitter)とAtCoder Problemsのlockout形式のバーチャルコンテストをやりました。
最近話題になっているので僕もやりたいな～～と思っていたらぷ～べあさんも対戦相手を募集してそうだったので、やりませんか？と声を掛けたら快諾してもらえました。
問題はぷ～べあさんに選んでもらいました。青diff 6問150分のセットでした（ここ）。
以下、バチャレポートです。解法ネタバレ回避のために本質っぽいところは白文字にしてあります。
バチャ開始~ 1問目
最初はとりあえず6問開いて、解けそうなものを探す。Colorful SlimesがAGC004の400点だったからどうせ簡単だろうというメタ読みをして取り組む。
読んでみると簡単で、N が小さいのでそれぞれ色のスライムについてどこから取ってくるかを全探索すればいいと考える、実装する、サンプル2が合わない。サンプル2を見ると、出力例が僕の想像より小さいことに気づく。
僕は一度の魔法で一匹しかスライムが動かないと勘違いしていたけど、問題文をよく読むと一回魔法を唱えるたびに全部のスライムが移動するらしいことがわかった。
昔のAGCの400点がそんなに難しいわけないだろと思いながらとりあえず全探索がなのを確認していると、魔法を唱える回数を
回と決めたらそれぞれのスライムは自分以下
個から自由にとってこれることに気づく。
セグ木を貼ると誤読したコードを少し変えるだけで良かったのでgot a kotonaki。
1問目~ 2問目
次はErasing VerticesとContignuous RepaintingとMoving Piecesのどれかだな～～、とりあえず一番左上にあるErasing Verticesやろう。
と思って見てみるといつかのAGC-Aだった。なんかうっすらと解法覚えてる感あるし、これ解いたらちょっとフェアじゃないだろうな～～と思いながら眺めてると全然わからなくて余計な心労をためずに済んだ。
残った二つではMoving Piecesが取り組みやすそうだと思い、解こうとしてみる。ACLコンテストで問題概要知ってたけど、そんなこといってたらやってられんわと思い気にしないことにした。
ACLのmin_cost_flowは負辺に対応していないから絶対違うだろうなとは思いつつ、最初は負辺あり最小費用流を考えた。行き詰った駒どうすんねんと思っているとコスト0キャパ1の辺で逃がせばいいと気づく。もしかしてこれ二部マッチングでいける？となると方針がたった。
このあたりでContignuous Repeatingが通される。Moving Piecesを通したらErasing Verticesやることないだろうし、ペナで威嚇しとこ と思い適当なコードをErasing Verticesに投げる。
なんかめちゃくちゃWA吐いたけど、lockoutのペナルティよくわからないから気にせず投げまくるとAC。
ここまでの状況
僕: 1000 点、ぷ～べあさん: 400 点
残った問題:
Erasing Vertices: 400 点
Nearest Card Game: 500 点
Ears: 600 点
僕があと一問通すとして、
Erasing Verticesを通す-> 残り全部を通されたら負け
どっちかを通す-> 勝ち
2問目~ 3問目
得点状況からErasing verticesよりもEarsかNearest Card Gameをやるべきだろと思い、二つを見てNearest Card gameをすることに決める。
ちょっとみて全然わからないので少し手を動かすと高橋君が取るゾーンと青木君が取るゾーンと二人が交互に取るゾーンに分かれることに気づく。
このゾーンの境目はにぶたんで求められる、勝ったなガハハと思いつつ実装をしていると、バグる。
あわあわしてると先に通されて涙。
次何やろう
ここで次に解く問題に悩まされる。
Erasing Verticesをやる場合、解けてもEarsを通されれば負け。
Earsとやる場合、僕が解けないかつぷ～べあさんにどちらかを通されれば負け。
の二択になってしまった。
人が解けないことを願う時間が発生するの嫌だからEarsをやることに決める。
Earsをやる
問題文を読むとすぬけくんの耳に石が入れられることがわかった。たまに話題になってる奴じゃん。
う～～～ん、どうしたらいいんだろう。と思っていると通される。対戦ありがとうございました。
余った時間
プロの将棋では自分に勝ち目が無くなった時、熱戦だったと演出するために「形作り」という行為がしばしば行われる。
僕は将棋も結構好きだし、これにならってせめて100 点差で熱戦だったと演出してやろう とErasing Verticesに取り組んだ。
解けませんでした^p^
感想
普段とは全く違う形式のバチャで新鮮だったし、コンテストとは違ったゲーム性があってとても楽しかったです。
中盤以降怒涛の追い上げをくらってしまい、非常に焦ったのもコンテストでは中々ない体験でした。
150分もあったので、途中休憩をはさみましたが普段よりも集中して取り組めたのも良かったです、つかれた～～。
ぷ～べあさん、対戦ありがとうございました！！
またやりましょう🔥
lockout形式の対戦相手随時募集中です
いつでも声かけてきてください！！
