橙になりたいaquarium

にゃーんにゃーんにゃにゃーん

ICPC2023国内予選参加記

AtCoder黄色のshinchan(@Sophia_maki)です。ICPC国内予選通過しました！！！！！！！！

目次

チームの紹介

チーム名はkotamanegi_mijingiriです。メンバーは以下の3人です。

  • KowerKoint (@KowerKoint2010)

一番レート高い。実装とか早解きの鬼。ABCで取った100位以内の順位のビンゴとかやっててめっちゃ埋まっててすごい。

  • Daylight (@Daylight_pro)

DPとかデータ構造が得意らしいです。DPが出たら投げようと思いました。

パズルが得意です。数学とかFPSとかもちょっとだけできます。DPと早解きと実装が苦手です。

黄色下位3人チームで、阪大では2軍でした。ただ始めてからずっと勢いがすごいkureha氏に負ける可能性はじゅうぶんあると考えてました。実際私たちは学内3位になりました。

前日まで

チーム名の決定

チーム練

6月11日、AHCがあった日に吹田キャンパスに集まりました。daylightさんとは初対面でした。

twitterを見ると、ちょうど同じ時間帯にAHCをサボってチーム練をしているチームがあるではありませんか。

れたすさん、りきぽんさん、はちじさんのチーム(tenkei998244353)でした。彼らが2018国内予選をやるということで、私たちも対抗して同じのを解くことにしました。

結果として、5完早解きという形になりました。このとき、KowerKointくんに常にpcに張り付いてもらうのが最適だと考え、私は実装しないことに決めました。

あとlettuce_mijingiriも行うことにしました(？)

個人練(儀式)

模擬国内

KowerKointくんが参加できないということで、Daylightくんと2人ででることに。家がわりと近かったので私の家にしました。

A, BをDaylightくんがやって、僕はCを見る方針となりました。

Cでわりと苦戦してしまいました。KowerKointくんいないしーと思って自分で実装したのが間違いでした。DはDaylightのD、DPのDです。良い高速化を見つけて解いてくれました、つよい。

Eはなんかいい感じになりました。僕も実装しましたが、拡張ユークリッド書く以外は実装量かなり少ない問題で助かりました。

2人でこの結果、いい感じ。

本番

方針

早解きが得意なKowerKointくんにA, Bを解いてもらい、CをDaylightくん、Dを私がやることになりました。 また、私は一切実装をしません。他2人の好みで、キーボードがUS配列で、Neovim拡張を入れた環境でした。私は元々実装苦手なのもあって、すべて他2人にmarunageする方針を取りました。

また、パズルっぽいのがでたら私に回してもらい、逆にDPっぽいのはmarunageする方針でした。

本番中

A問題ACまで

始まった途端コンテストページにアクセスできなくなりました。httpsにしてたらダメだったみたい(リハーサルでは大丈夫だったのに)。きたむーが審議申し立てを提案してくれたのでやってみた、通らなかった。

さて、問題見れない、印刷できないことには、KowerKointはフォルダやファイル作ってマクロやライブラリを書くとして、他2人はやることがないです。

7, 8分ほどして問題が見れて印刷できたので各々取り掛かりました。KowerKointくんがAを通してくれました。

B問題ACまで

Cがパズル、DがDPっぽいと思ってDaylightくんと問題を交換しました。

とはいっても、まずはCを2人で考えようとなりました。行の偶奇と列の偶奇に着目してみてはという助言に従い、市松模様を考えました。これで白い部分を左に、黒い部分を右に寄せたらなんかいけそうと思いました。

KowerKointくんがBをACしました。

C問題ACまで

合ってるかどうかの確認ができるタイプの問題なので、解法をKowerKointくんに伝えて実装してもらいました。他2人はD以降見てました。 どうやらCはNが偶数のときにうまくいってないみたいです。Daylightくんが、右に寄せた部分の上半分と下半分を逆にしてみてはと言ってくれて、KowerKointくんが実装してACしました。

D問題ACまで

このタイプの問題は2冪を考えるとよく、1, 2, 4, 8, 16, 32, 64で、高々7つですべて構築できることがわかります。 なので6個以下でできないことを確かめるといいです。単調増加で、総和がNで、bitsetが使えるのでーって感じで全探索で間に合う気がしてきました。って考えてる間にKowerKointくんがEの考察を終わらせたみたいで、先に実装してました。違ったようです。Dの実装をDaylightくんが始めました。6重forで書くのはかなり厳しく、KowerKointくんのEと交互に実装してました。途中でdfsでの実装に切り替え、完全にペアプログラミング状態でした。その際、bitsetまわりを1, 2行だけ私が実装してしまいました。まぁ、ACしたのでよしです。

その後

順位表を見るとEを解けば確実だと感じました。F, GのACもちょっとだけいるけど望み薄いなぁとなりました。Fは見た瞬間にチームメイトと爆笑してました。Gはどうやって重複除くんだろうとなってました。

というわけで、3人で確実にEを通し切ろうという方針に。なにもできません、おわり。

結果

21位！！！！！通過しました！！！！！

さいごに

コーチのolpheさん、めっちゃmarunageしてました、すみませんでしたありがとうございます。

阪大初の3チーム通過！！














院試今月末！やばい！