ICPC2023 アジア地区予選参加記(itigo)
ICPC2023 アジア地区予選参加記
チームtatitsuとしてpitsuさん、tardigradeくんと共にアジア地区予選に参加しました。僕とpitsuさんは最初で最後のアジアでした。ワクワク
コンテスト以外の話
11/24(金)に横浜入り、空港暑すぎ(札幌が寒すぎる？)
11/24(金)の夜はHCPCのOB達と中華食べ放題した。まわるテーブル楽しい
宿泊先、3泊4日で8500(税込)の最高の宿。どこでも寝れる僕はあまり気にならなかった(なんなら居心地良かった)けど気になる人は気になりそう。普通に近くの宿泊客のいびきは聞こえる。
slackで「ここ会場激近で激安！！」みたいなこと言ったらpitsuさんにパクられた。
ただ最大の問題点として、音出せないので当日朝にアラームがかけれない。幸いpitsuさんも泊まってたので互いに部屋番号を共有した。二人の寝坊率をp,qとするとp+q-pqだった出場失敗率をpqに抑えることに成功。偉い！(当日は普通に二人とも起きた)
コンテストの戦略
うちのチームは次の役割分担
itigo : ひたすら解法を考える、どっちかというとヒラメキ系
pitsu : 実装マシーン。便利
tardigrade : 考察も実装もバグとりも臨機応変にしてくれる。便利
また、チーム戦の戦略として次のようなことをしていた
- バグったら考えるより先にプリントしてパソコンから離れる(超おすすめ。プリントはほぼコスト0。ボランティアにいっぱい労働をさせよう)
- 基本問題概要をチームメイトに伝えることはしないで、各自読む(誤解を生むため。最近のICPCの問題はわかりやすいので口で説明するより読んだ方が正確だし説明側のリソースも裂かない)
コンテスト本番
開始と同時に僕がPCの準備、pitsuさんがA、tardigrade君がBを読む。
僕が準備終わると同時にpitsuさんがAの実装を開始
0:12 A問題 AC
僕は初手Cを読む。実はこの問題、ほぼ同じものを作問で考えたことがあってむず過ぎて諦めたことがある。具体的には下記の問題の「同じ数字を何個でも書いていい時にYESになるものの数え上げ」を考えてた。
チームメイトに「この問題知ってて、不可能です」と伝える。
tardigrade君がBで困ってそうだったのでBに参戦。良さげな解法が思いついたのでtardigrade君に伝えて納得してもらう。納得させたので実装をmarunageした()
僕はF問題考察へ
0:44 B問題 AC
Fが思いついていたので僕が実装をする。
できたコードを実行するとPCがクラッシュする。
復帰してもう一回実行すると実行するとPCがクラッシュする。
もう一回実行すると実行するとPCがクラッシュする。
Judgeを呼んで状況説明をする(英会話力低過ぎてかなりコミュニケーションに困った)
どうやらメモリーが壊れてるみたいなことを言われ、よく確認してみると
./a.out < output.txtとしていた(output.txtを入力にしていた)
これやるとPCクラッシュするのか...
./a.out > output.txtにして実行するとサンプルが合わない。
よく見ると誤読してることが判明。(英語力さん...)もう一回考察して、分かったので実装した。
1:14 F問題 AC
なんかpitsuさんとtardigrade君がKが解けそうみたいなことを言ってる。僕はDを読む。なんか区間DP的な感じで解けそう。Kが詰まってる間にPCを借りて実装したりしてたが、うまくいかなかった。実装力が足りない...
そうこうしてる間になんかチームメイトが勝手にKを通してた
2:20 K問題 AC
pitsuさんにDの概要だけ伝えてmarunageした()
僕はtardigrade君とEをやる。tardigrade君が「これbitDPでO(m2^n)だけど、流石に遅すぎるよね」みたいなことを言っていたので考えてみると、mが大きいケースは巡回順序の制限も重くなるので実際は2^nも無さそうみたいな話になり、「ワンちゃんこれで行けるだろ！！」と強行。
ここでpitsuさんのDがWAになる。tardigrade君がEを実装しつつ、僕とpitsuさんがDのバグ取り。
その間にtardigrade君のEがTLEする。
~ここからDがWA、EがTLEが続く~
Dの誤読が判明。(英語力さん...)直して投げる
3:21 D問題 AC
tardigrade君がEの細かい高速化を頑張る
3:25 E問題 AC(尚非想定解)
僕がGをやる。pitsuさんとtardigrade君がHをやる。
....
....
~何も進捗が生まれない~
コンテスト終了 6完 28位
感想
英語力低過ぎ、実装力も低過ぎ
ただチームで協力して戦うのはかなり楽しかった。このコンテストもっと競プロ強い自分で参加したかったな...
ICPC国内予選参加記(itigo視点)
あらすじ
5完16位、国内予選突破やったーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー★★★★◎◎◎\^^/ddddddd
僕の名前はitigo、北海道大学M1、ギリギリ黄色の競プロer
ICPC予選は今年で5回目、いままで4回は全て予選落ちしていました。(結構行けそうなチームだったんだけど)
最後の年となる今年は5回連続一緒に出てるM2のpitsuさん、とんでもない勢いで成長してるB2のtardigrade君と僕のチームtatitsuで参加しました。
事前戦略
僕(itigo) : 初手B問題を担当、その後は他二人の様子を見てCかDの考察を行う。基本的には考察担当で、実装は可能な限りpitsuさんに任せる形。
pitsuさん : 実装マシーン。初手A問題を担当し、終わり次第tardigrade君とC問題の考察をして実装、D以降も可能な限り実装を担当する。
tardigradeくん : 考察マシーン。初手Cを考察、Cが解け次第D,Eの考察。他の人がバグったときのデバックも彼の仕事、メッチャ便利。
全体戦略：
・まだ問題を見てない人に先に問題概要を説明しない。問題文より分かりやすい問題説明はこの世に無いという結論。口で説明してしまうと結構誤解を生むし、説明側の考察時間も損だし、二人とも誤読するリスクもある。
・バグったらとりあえず印刷。バグってんのにパソコン使うな。デバックは印刷見ても可能だし、他の人もデバックしやすい。ペーパーモア化を促進しよう。
本番
開始4分
pitsuさんがAをAC。3:52で7位らしい。早過ぎ、これ解き始める前に問題印刷してるのでマジでおかしい。
開始15分くらい
僕がBをWA。なーーにやってんだーーー。Cの考察が終わってなかったっぽいのでそのままパソコンを続行、一か所バグを直してもう一回提出してWA。ヤバすぎ、とりあえずコピーしてCのpitsuさんにPCをパス。tardigrade君とBをやる。
開始31分
pitsuさんがCをAC、俺以外のチームメイト優秀過ぎ。ありがとううううううううううううう。僕がBを「線を置く位置を全探索する」方針で実装開始。
開始40分
Bを実装中に気づく。「これ、xとyの出力順逆じゃね？」。以前のWAコードのサンプルを見るとマジで逆だった。このコードの出力順を変えて提出するとAC。これは戦犯。チームメイトにはWAの原因を内緒にしてDに行く。
D問題
先にpitsuさんとtardigradeくんが考察してる。ちゃんと聞いてないけどDPしてるっぽい？けどDPは二人に任せて僕は一人で考察。割とすぐに「これ、答え高々7じゃないか？」になった。（偉い！）6個以下を再帰で全探索すればええやんけ。これを二人に報告。
pitsuさんをPCに座らせて僕が後ろでpitsuさんをラジコンにして実装。言った通りにすぐ実装してくれる。カッコイイ楽しい。なんかメモリが何たらでしばらく沼ってたけど1:31:06でAC。
予選突破がかなり安全になった。
E問題
皆で一緒にEを始めた。割とすぐに僕がDPで解けた気持ちになって実装開始。なんかバグったけど印刷したらtardigrade君が直してくれた、嬉しい。一回WAになったけどこれも些細なミスで(お前何回ミスするん？)直したらAC。5完した。やったーーーーー。
感想
全体として、僕はB,Eの解法と実装、Dの解法とpitsuさんをラジコン操作、3ペナを担当しました。
B問題で沼ったときは吐きそうだった、5年連続予選敗退がちらついた。この後D,Eで活躍で着て本当によかった、本当に。
北大の他のチームのelephant_spaghettiとCactusが普通に強くて、27位と30位なのでDもうちょい沼ってE解けなかったら普通に落ちてた。未来有望だぜ....
普段やらないルールなので練習がめちゃくちゃ大事で、毎回得られるものがあった。特に「バグったら即印刷」は本当に正しくて、これしてなかったら落ちてそう。
なにはともあれ予選突破嬉しい！！！！！！！！！！！！！！！
pitsuさん、tardigrade君ありがとう！！！！！！！！！！！！！
横浜でもよろしくね！！！！！！！！！！！！！！！！！！！！
黄色コーダーになるまでにやったこと(いちごくんver)
黄色コーダーになったぜ！！！！！！！！！！！！！！！！！！！！！！うおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおあああああああああああああ亜亜亜亜亜亜亜亜亜亜亜亜
HCPCの皆！我黄色コーダーぞ？
北大の皆！我黄色コーダーぞ？
pitsuさん！ごちそうさまです！
ポーカーチェイスステージⅥの皆！我黄色コーダーぞ？
おるふぇ！！！！好きだぞ！！！！！！
monkukuiさんの性癖が迷宮入りしてしまったこと、深くお詫び申し上げます。(4月までに黄色になったら書いていいレギュレーションだった)
京子ちゃん！やっと同じ色になれたね！
京子「やったな！」
札幌駅近郊の美味い飲食店BEST3
お待たせしました！札幌の飲食店ランキングのコーナーです！
さて皆さん、北海道と言えば美味いもんですよね？
しかしいざ札幌に旅行に来れた時、札幌には飲食店が多すぎてどこに入るか迷ってしまいがちです
そこで札幌生活4年目のいちごくんがオススメする最強の飲食店BEST3を紹介します！
第三位 根室花まる
やはり北海道と言えば寿司。
数ある寿司屋さんの中でもこの根室花まるは一線を画しています
根室花まるには普通のメニュー表とは別にこのような手書き(風)のメニュー表があります。これは季節によって変わり、旬のネタが詰め込まれています。
根室花まるに来たらこのメニュー表から貪欲に注文しましょう
第二位 Picante
意外と知られていないですが、実は札幌はスープカレーが名物です
その中でも個人的なNo.1はここPicante
カレーとは思えないほどドロドロしてないが飲んでみるとスパイスが効いておりしっかり美味しいスープに豪快に入れられた野菜達
この味はおそらく他の何にも類似しないここだけの味
是非一回ご賞味あれ
第一位 ノースコンチネント
異常。プレートに乗ってる何もかもが美味い。
ハンバーグはもちろん、ソース、野菜、どこを食べても美味しい
「札幌に来てまでハンバーグ？」ってなるかもしれないが、多分札幌で一番この店のハンバーグが美味い。世界最強。
黄色になるまでにやったこと
先に忠告をしますが、ここから先はただの自分語りであり、「黄色になるのに必要なエッセンス」は一ミリもございません。興味ない方はブラウザバックを。
レート推移を見てわかる通り、私は長い長い青コーダーを経験しました
ですが正直この理由は明確です。精進してないからです
私が競技プログラミングを始めたのは大学に入学すると同時の頃で、この頃の私は実は受験に失敗した直後でした
当時大学に入ったら競プロを始めるのが流行っていたようで、Twitterで仲良くしていた僕の第一志望に合格した人たちが一斉に競プロを始めました
僕は彼らに勝ちたくて、劣等感の吐け口が欲しくて、自分の能力を証明したくて...
狂ったように競プロにのめり込みHello Worldから6か月という異常な速さで青色になった時、一緒に競プロを始めた彼らのほとんどはもう競プロを辞めていました
そして僕もなんだかんだ北大に馴染み始めました
競プロをする理由が無くなりました
こうして僕の精進は終わりました
...私が黄色になったのは紛れもなく「上振れ」です
常にあった青上位程度の実力でコンテストに出まくったら、そりゃそのうち黄色になります
だからここに書くことなんてありません
せいぜい大声で喜んで美味い飯屋でも紹介する程度です
黄色になって気づいたことがあります
レートが上がるのって、めちゃくちゃ気持ちいいですね
それに気づいて一週間、レートを更に上げたくなってしまい黄色になってから逆に精進を始めて更に気づいたことがあります
難しい問題を通すのって気持ちいいですね
新しい学びが得られるのってめちゃくちゃ充実感がありますね
競プロ、結構楽しいな
次はこんなクソみたいな記事ではなく、超有益な「橙色コーダーになるまでにやったこと(いちごくんver)」で会いましょう
CodinGame Spring Challenge 2022 参加記
CodinGame Spring Challenge 2022 参加記
CodinGame というサイトの Spring Challenge 2022 というゲームAIコンテストに参加した結果、7695(参加登録のみでは18288)人中199位になることができました。
いえーーーい
というわけでこの記事では今回の僕のコンテストの様子を追体験してもらいながら「コドゲって面白そうだなぁ」と思ってくれれば幸いです
目次
そもそもコドゲって何？
簡単に行ってしまえばCodinGame(以下コドゲ)は自分が作ったゲームAIを他の人が作ったゲームAIと戦わせて誰が最強か決めようぜ！といった大会です。
ゲームAIを書いて提出すると下の画像のように自動的に他の人のゲームAIと対決してくれ、その結果からよくある対戦ゲームのレート戦のように自分のゲームAIにレートが付けられ、順位付けされます。
また、コドゲには「リーグ」と呼ばれるものがあり、最初はWood2リーグから始まり各リーグのBOSSより上のレートになる(要はそのリーグで1位になる)と上のリーグに昇格できます
今回参加したSpring Challenge 2022は10日間開催されており、この期間内に自分のAIを強化して上のリーグを目指すなり上位入賞を目指すなり頑張るといったコンテストとなっております。
ちなみに今回一番上のLegend Leagueまでたどり着いたのは390人だったようです。
ゲームルール
というわけでコドゲのコンセプトを理解したところで、「じゃあ具体的にどんなゲームするんだよ」って気になると思うので今回のゲームルールを確認していきましょう。
と言っても百聞は一見に如かず、対戦動画を見たら何となくわかると思います。
簡単に言葉で説明すると1対1の対戦ゲームで、3人の人間を動かしてモンスター(虫みたいなやつ)を相手陣地に入れた方が勝ちってゲームです
人間は一ターンにつき以下の4つの行動ができます
MOVE : 800マス以下の範囲で動く。
WIND : 1280マスの範囲に居るモンスターと敵を指定した向きに2200マス飛ばす
SHIELD : 指定した相手にシールドを張る。12ターンWINDとCONTROLを受けなくなる。
CONTROL : 指定した相手の次のターンの行動を操作する。モンスターを操作した場合、モンスターはその時指定された向きに以降も歩き続ける。
人間がモンスターの800マス以内に居る時、人間はモンスターにダメージを与え、"マナ"を獲得できます。
WIND,SHIELD,CONTROLを使うには10マナ消費する必要があります
というのが大雑把なルールです
細かいルールが知りたい人はツカモ様がルールの日本語訳記事を書いてくれているのでそちらを見ると良いです。
Bronze Leagueまで
Wood2,Wood1リーグはチュートリアル的なポジションで、メッチャ簡単なプログラムさえ書ければBronze Leagueまで行けます
今回はWIND,SHIELD,CONTROLは使う必要なく、ただ自陣の近くに来たモンスターのとこまで歩いていけば問題ないです
めっちゃ単純でかわいいね
Silver Leagueまで
まだ簡単。
ちょっとだけWINDを使って防衛できるようになればBronze Leagueは突破できた
イメージ的には毎回Silverまではちょっと実装能力があればたどり着けるので、ちょっとでもプログラミングできる人は次回のコドゲに挑戦してみて欲しいかも(?)
ここまで到達した時点ではTOEICがあったため本腰を入れて取り組むことができず、ここまででコンテスト終了まで残り3日となっていた。
「このままじゃ上位いけないな、頑張らないとなぁ」と思い、以下の計画を実行する
よくよく考えたら日曜夜まで何一つ予定ないので今から研究室行って日夜まで意味不明なくらいコドゲしまくるか
— いちご (@itigo_purokonn) 2022年4月29日
そうしよう
家出た
このツイートの通り、金曜(土曜とも言う)夜3AMからコンテスト終了日の昼12時までほぼ研究室に引きこもりコドゲ以外何もしないという暴挙に出た。
いちごちゃんの戦いはここから始まる！！！
Gold Leagueまで
流石にまともにプログラムする必要がある。
具体的にはいままでは守ってるだけで良かったけど攻撃役を用意しWIND,SHIELD,CONTROLを駆使して敵陣にモンスターを押し込む必要が出てくる。
研究室に引きこもってからなんやかんや3時間ほどプログラミングをして、以下の戦略でSilver Leagueは突破できた。
まだまだかなり単純で、序盤はマナをためてある程度溜まったらCONTROLをモンスターに打ちまくって相手にモンスターを押す付けるというもの
まだまだ拙い部分もたくさんあるがとりあえずこれでSilver Leagueは突破できた
Legend Leagueまで
鬼門。
ここまではお遊びに過ぎない。
ぶっちゃけGold Leagueまではまともに動くアルゴリズムを実装さえできればたどり着けるんですが、Goldを突破してLegendにたどり着くにはいよいよ一戦一戦のゲーム内容や環境を研究して強い戦略を練る必要がある。
僕もいろいろな戦略を立ててみた
・CONTROLとWINDを使って適切にシュートを試みるコード
・適切なモンスターにSHIELDを使って敵のWINDを無効化し対応不可にするコード
・WINDを使いモンスターを相手と押し付け合い、敵のマナを枯渇させるコード
・敵にコントロールを打ち対応不可にするコード
その他にも効率の良いマナ稼ぎ、強くマナ効率が良い防衛方法、敵にWINDやCONTROLを使われたときの対処法など細かい修正を加えた結果、日曜夜12時頃、ようやくボスに9割くらい勝てるコードが完成した。
が、このコードではGold League 50位前後が関の山で、Legend Leagueに到達できない
なぜか
それは次の動画を見て欲しい
なにこれ（笑）
これは通称「ロマン砲」と呼ばれる戦略で、複数人でWINDを打つと飛距離が加算されることをいいことに序盤にマナを溜めるや否や、圧倒的パワーでモンスターを押し付けてくる戦略である。
コンテスト終盤、このロマン砲がGold League上位で跋扈しており、性能の良いロマン砲が性能の悪いロマン砲を駆逐するという地獄絵図となっていた。
Legend Leagueに行くにはこのロマン砲を対策するか、自身もロマン砲に魂を売るかのどちらかをしないといけない環境だったのだ。
さて、このロマン砲、最強の戦術かと言われると実はそんなことはない。複数人で攻撃するには当然防衛が手薄となる。すなわちロマン砲を打ってる間にこちらが攻め込んでしまえばこの戦術は崩壊するのである。
ということでロマン砲対策を埋め込み提出してみた
こうして晴れてLegend Leagueに到達できました！よかったね
伝説！！！！！！！！！！ pic.twitter.com/HmDIZhAUHf
— いちご (@itigo_purokonn) 2022年5月2日
感想
今回のゲームは正直かなりジャンケンの要素が強かった
具体的には
・ロマン砲
・マナファーミング(僕はこれに当たる)
・1攻撃2守り型
これらが上からグー、チョキ、パーの関係にあり、明確に戦術同士の相性が存在した。
しかし、順位を上げるのに大切なことは「自分がチョキの時にどれだけパーへの勝率を気づ付けることなくグーにワンちゃん勝てるようになるか」と感じる。実際僕のコードはロマン砲と戦ってもある程度の勝率を確保できるようになったときにLegendへ上がることができた。
どうやったら自分に不利な相手を倒せるか、どうやったらより有効な攻撃ができるかを考察し、実装し、対戦するのは非常に楽しく、研究室に籠っていた三日間熱中して取り組むことができました。
CodinGame様、楽しいコンテンツをありがとう、次回も頑張ります！！
おまけ
最終コードの戦術
【防衛】
モンスターの数と自陣付近の敵の数に合わせて0~2人で防衛し、防衛していないときはマナ集め。尚敵が攻めてきたときは基本的には2人防衛。
モンスターは自陣に着くギリギリまでは攻撃してHPを減らし、WIND以外で対応できなくなったらWINDを打つ。
敵が来ている時は必ず1人が敵をマークし、敵のWIND圏内にモンスターが入った時はWINDを打ちシュートを決められないようにする。
【マナ集め】
防衛役は自陣付近、攻撃役は敵陣付近でマナ集めを行う。
可能な限り複数のモンスターを同時攻撃できた方が良いためモンスターが重なる場所を探索し、そこを目指してマナ集めするように動く。
序盤は敵陣に向かうモンスターを優先的に狩り、中盤以降は自陣に向かうモンスターを優先に狩る
【攻撃】
45ターン目、または相手がロマン砲を作っていると判明すると1人敵陣へ突っ込みWINDを使って攻撃する。敵が1人の時はCONTROLを使ってこの1人を拘束する。敵が2人見えたらロマン砲ではないためマナ集めへ戻る。
十分マナアドバンテージが取れると1人敵陣へ向かう。
敵陣付近でうろうろし、敵陣に入りそうなモンスターにCONTROLを打つ。そして敵陣4700マス地点にモンスターが到達した時、人がその前方1100マスに立ち、二連続WIND(WIND射程が1280マス、WINDで飛ぶ距離が2200マスのため適切な位置に人がいると2回WINDを当てて4400マス飛ばすことができる)を打てるようにする。
十分なHPを持ち敵陣近くに居るモンスターにSHIELDを打つ。
モンスターが3体以上溜まり、敵防衛が2人居る時、敵2人に交互にWINDを打つことによって敵2人を拘束する。
