橙になりたいaquarium

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

ICPC Asia Bangkok Regional Contest 2025 参加記

大阪大学のICPCチーム、honmono shinchanのshinchanです。タイのバンコクで開催された「ICPC Asia Bangkok Regional Contest 2025」に参加しました。

※長くなるので、この記事ではICPCの参加資格復活の経緯について記載しません。

チーム紹介

shinchan

情報科学研究科の修士2年。ラストイヤー(2回目らしい)。6度目のICPC。最近AtCoderのレートの伸びがよく、2200に乗りました。Codeforcesも赤に戻したいところですが…。 ICPCチーム The Revenge of shinchan のチーム名担当。

https://atcoder.jp/users/shinchan

Gandalfr

情報科学研究科の修士1年。AtCoder水(Highest青)。ラストイヤー。昨年までは同じ学年のHerring101やhiro71687とチームを組んでいた記憶がありますが、この2人は今年は2軍入りしており(↓下のURL参照)、そこに悔しさもあるんじゃないかなと思ったのが誘ったきっかけです。エンジニアリング方面が強いです。私よりはC++について詳しいです。

2025/Teams/List - ICPC OB/OG の会

https://atcoder.jp/users/Gandalfr?lang=ja

itokoi

医学部3年。AtCoder水。CodeQUEEN2025決勝3位。今年が初めてのICPC参加です。Python使い。

他のCodeQUEEN参加者からは「早解きが得意なイメージ」と聞いていたのですが、高難度問題もしっかり戦えています。

https://atcoder.jp/users/itokoi?lang=ja

littlegirl112

コーチです。

幼女、よじょなどと呼んでいます。私と同じく情報科学研究科の修士2年です。コーチ業に関しては、半年前からいろいろととてもお世話になってます…。

https://atcoder.jp/users/littlegirl112?lang=ja

チーム名について

チーム名に自分の名前を入れること(入れてもらうこと)には元からかなり興味がありました。

The Revenge of shinchanに対抗した名前にしてみようと思ったのと、ロボてりー(https://x.com/terry_x86) に対しててりーさん(https://x.com/terry_u16) が「ほんものてりー」と呼ばれていることから真似して、ほんものしんちゃんにしました。

他にチームメイトから案がでなかったので決定。

きっかけ

OKが出るまで(詳細は別記事で)

国内予選の前後で私の気持ちは大きく変化しました。6月上旬までは出たいという気持ちでいっぱいだったのですが、8月に突如メールが来たときには、「全員平等に引退しようよ…」という気持ちに変化していました。

しかし、もし出られることになった場合、横浜でJAGとしてThe Revenge of shinchanのWF進出決定を見守るより、Asia Pacific Championship (以下、APAC) でそれを見たいと思いました。そして、チームメイトになってくれる人が、ラストイヤーであれば、最後にいい思い出になってくれたら。そうでなければ今後成長してくれることに期待して、参加したいと思うようになりました。

チーム結成

ICPC日本側運営からGoサイン(と私は認識しています)が出て、私がチーム募集をかけたのが9月11日のことです。

運営からは、「横浜Regionalに参加させることはできないが、海外Regionalに参加が可能」とのことでした。また、7月にあった日本の国内予選に落ちている阪大メンバーを誘ってチームを組むことも可能でした。

なので、ICPC参加資格が残っていて、横浜Regionalに参加しない人をレートややる気、レスの早さ、成長性などを考慮して上記2名を誘ったところOKしてくれたので、この3人で組むことになりました。9月12日のことです。

正直なところ、レート2200から見ても青と水ではだいぶ差があると思っていて、阪大には青以上が残っていなかったのでレートはそれほど気にしていなかったです。ライブラリ準備の手伝い・ライブラリ写経・英語問題文読解・C++仕様・数学・データ構造知識などについてなにか秀でていれば良いと思ってました。

gandalはライブラリ準備・写経などの雑用・エンジニアリング面を従順にやってくれそうと思って、Daylight (昨年のチームメイト) みたいな感じで扱っています。

itokoiはPythonでの虚無問題の早解きだけでなく、医学部であることから、受験から得た英語力や数学力に期待できそうと思って、僕にできないことをやらせる枠です。

Regional選択

決定的な理由は3人の予定が合うのがBangkok Regionalだけだったからではあるのですが、他にもいくつかあります。

まず、以下のような要因でAPACに進めない可能性を考え、どうせならチームメイトの2人にRegionalだけでも楽しんでくれたらと思ったことです。 実力面、横浜でRevengeが優勝、「自分やっぱり参加資格復活してないんじゃないか？？」「もしかしたら突然失格になるかも」なんていう可能性もありました。

そして、タイ国内のチームは1つを除いて強くないこと(海外チームのことだけ考えればよい)。

相談も何人かにしました。Kuroni からは東南アジアのRegionalの難易度感について教えてもらいました。ttamxからは、3月のシンガポールでのAPACの時点でBangkok Regionalの存在を教えてもらってて、改めて、バンコクに誘われました。

また、少し野望もあって、APACでまともにRevengeとやりあって勝てるわけがないので、Bangkok Regionalでワンチャンの優勝を狙っていました。

練習

チーム練内容

チーム練は毎週、計6回行いました。毎回部屋を貸してくださった研究室の方々に本当に感謝しています。

元々チームメイト2人の特徴は一切知らなかったし、itokoiはチーム戦の経験もほとんどないです。なので6回というのは、水色の2人にとってみても、6週間ほどしかない猶予を考えてもかなり多いように思いますが、実際にはまだまだ練習が足らなかったです。

練習に使ったセットは、過去のタイのRegionalや最近のタイの国内大会、Chulalongkorn大学の内部コンテストがCodeforcesのgymにいくつかあるので、それを使いました。このときにも、僕が過去問を見つけられなかったり、新しいセットが生えたときはttamxが毎回教えてくれました。また、物理好きが並走してくれて、感想戦を行ったりもしました。

https://codeforces.com/gym/101161

https://codeforces.com/gym/102091

https://codeforces.com/gym/106118

https://codeforces.com/gym/105335

個人練内容

チームメイト2人が日本語配列キーボードを使ってたことに対して僕がちょっと残念がってたら2人とも英字配列を買ってくれました…、ありがとう…。

ソロでもタイの問題のupsolveをしました。

https://codeforces.com/gym/106069

2人共通して指示したのは、英語問題文の読解の練習です。僕が一番苦手としているのがそこですし、競プロ以外でも役立つほうが積極的にやってくれるかなと思ったのが理由です。

追加でgandalに指示したのは、ライブラリの整備と写経の練習です。セグ木をgandalが書きやすいように改造してもらい、写経の練習をしているうちに、ソラで書けるようになっていました。

一方でitokoiに指示したのは、これまで通りレートを上げることです。おそらくすぐに青になりますし、来年以降のICPCでは確実に主戦力に入ります。あと、阪大からCodeQUEEN優勝が出たら嬉しいです。

私はいつもどおりAtCoderやCodeforces、それからUniversal Cupにも新しくチームを組んで参加しています。また、gandalと協力して昨年の私のチームのライブラリを改造しました。

わかったこと・戦略

昨年の私のチーム(kotamanegi_hint_kureya)では、3人とも同学年で、チーム結成当初はレートも近かったので、お互いに積極的にコミュニケーションを取ることができました。一方で、今年のチームメイトはかなりおとなしいように見えました。2人とも私よりレートが数段階低く、後輩なので、どうしても怖がられてる可能性があります。

ICPCでは、限られた時間で、読解できた問題の伝達をいつも以上に早口で、正確に、簡潔に伝える必要があります。聞く側も、問題に感じた違和感に突っ込む必要があります。以下の、2024年のWorld FinalsのSpeed StarのReactionsは、かなり自分の理想に近いコミュニケーションをしていると思いました。

https://news.icpc.global/reactions/2024/?team=132

私はチーム練で意図的に、最初は気持ちゆっくりめに話し、練習を重ねるごとに、本来の早口に戻していきました。チームメイトに自信を持ってほしくて、「腹から声出して」なんて言ったかもしれません。 チームメイトも、最初より格段に積極的になってくれたと思います。

練習を重ねるうちに、gandalの知識の多さ、itokoiの解法の糸口を掴む力に気づきました。

そこから、競プロっぽくない問題はgandalに任せ、知識があまり必要ない(知識が意味をなさない)問題にitokoiを張らせることが多くなりました。実際、僕がわからなかった問題がitokoiに解けることも少なくなかったです。私は可能枠・自明枠を確実に通し切ることに徹しました。

その他の準備

参加登録

※コーチである、よじょの参加記に詳細が書かれると思います。

チームを組んだ直後は参加登録が始まっていなかったのですが、参加登録が始まった旨をttamxから連絡してくれました(始まってから数分のことでした)。どうやら、インスタを見ていればそういった情報が入ってくるようです。参加資格が復活したという旨も含めて、コーチからBangkok Regional運営に連絡してもらい、OKがでました。

参加費の支払いではコーチが想像よりもかなり大金を払っていて、8000バーツ(だいたい4.8をかけると日本円になる)を1人あたりだと認識しているようでした。さすがにそんなことはないと思ってホスト大にいるttamxに聞くと、運営に聞いてくれて、per teamだと返ってきた。結果として、Regional Day1のRegistration時に、10万円を超える現金がバーツで返金された。

参加チーム

登録が終わってからコンテスト環境・ルールが発表されたり、参加チームが公開された。

元々kuroniから、WFで32位だったHCMUSのチームや、NUSから3チームが参加するということを教えてもらってはいたが、NUSからは4チームで、台湾大も来るし、WFで10位だったソウル大のチームが来るというのを知ってさすがに優勝は諦めた(このチームは韓国予選でも優勝していた)。

そのくせに参加チームは少なく、site scoreも期待できない。なぜなら、Bangkok Regionalはタイ国内チームにも数万円ほどのお金が参加料としてかかるため、国内チームが少ない。その上、国内大会はRegionalの予選としての立ち位置ではなく、単に広告目的であるということ。そして、国内大会はオンサイトであるため、参加チーム数が限られること。

正直、どのみちタイしか選択肢がなかったし、自分もタイに行きたかったので、まぁそこに関しては運が悪かったねという感じ。魔境だなぁ。

コンテスト環境

ほとんどはDay1の開会式時に伝えられたものです。

Yokohama Regionalと違うところがいくつかあった。ライブラリはAPACと同じで、片面25ページ。上着などを持ちこんで良いが、持ち込むものはすべてday1のリハーサルのときに置いて帰ること。キャンディーとya dom(タイの鼻薬)が持ち込み化だった。ya domに関しては研究室の同期からお土産として要求されてた(眠気覚ましになるらしい)ので、そんなにいいものならと、僕も自分用に購入して持ち込むことにした。キャンディーは現地のセブンイレブンにメントスがあったので購入して持ち込んだ。また、筆記用具は自分で用意する必要があった。

また、印刷ページ数制限があり、50ページ以下である。それも、1ページは50行ほどで、ちょっとシビアかもしれないと考えていた。countpagesというコマンドで印刷するファイルのページ数や残りの印刷可能ページ数がわかる。

キーボードはペチペチキーボードで、それだけならまだいいとして、ほんっとうに、ほんとうに、打ちにくい。タイのチームもみんな言ってた。全部キーボードのせいにしていいレベル。

あと強いていえば、机の上に布が敷かれていてちゃんと固定されてないので、マウスを動かすとついてきてしまってマウス操作もままならなかった。これについては下にライブラリの紙をしくことで対処したが、そこに面積を使うほど机も大きくなく、...。

あと、リハーサルでも本番でもたまに画面がブラックアウトしていた。他のチームもそうだったらしいが、まぁ合計して1分程度しか変化しないと思うので、clarは投げなかった。

その他

discordがあり、参加チームに誰がいるのかがわかったり、質問が適宜可能でした。私も3回くらい質問しました。

ICPC自体とは関係ないが、海外に行くときにやることとしては、ホテルや航空券以外には、Wi-Fiと保険である。保険はこれを毎回使ってます(広告か？) https://off.sompo-japan.co.jp/top 。Wi-Fiは、これまでは空港で借りるタイプのを使ってたのですが、esimを使ってみることにしました。価格ドットコムから3日間で無制限のものを選んで、450円くらいでした。

また、ttamxから事前に知らされていたこととして、最近タイ国王の母が亡くなったらしく、服は黒とかのほうがいいかも、など教えてもらいました。実際にはそこまで気にする必要はなかったようですが、空港や寺など、街の至るところに説明つきの写真が飾られていました。

Day0(移動日)

到着まで

あまり寝れなかったです。家を7時15分くらいに出発し、関西国際空港に9:30くらいに着きました。

集合して、荷物を預けたり、昼ご飯を食べたりして、12:00発(の予定だったがもちろん遅延)のVietjetに乗りました。APAC開催国である台湾でのtransitで死亡フラグを立てます。

機内では、あらかじめ印刷していたベトナムのセットを、itokoiと一緒に考察しました。解かれてる範囲の問題は全部解けたと思います。実装は大変そうですが。

https://oj.vnoi.info/contest/icpc25_mt

到着後

無事にタイに着きました。時差は2時間で、現地は7:00くらいでした。

grabでタクシーを捕まえようと思ったのですがなかなか捕まらず、電車に乗りました。切符はコインのような形状で、入るときはこれを改札にタッチ、出るときは改札に入れます。

ホテル最寄り駅に着いてホテルまで歩いてると、大麻の店がかなり多く、タイに来たことを実感しました。匂いも20m歩けば極端に変わり、正直どれが大麻の匂いなのか一切わかりませんでした。車はごくたまにHyundaiやTeslaのものがありましたが、ほとんどは日本車でした。

ホテルではハロウィンということ、くじ引きでお土産をもらいました。石鹸をもらいました。コーチはなにやらいいものを引いてそうでした。街中でもハロウィンスタイルの仏教っぽいものがあったりしました。ホテル内での電話・テレビ・エレベーター・エアコンなどもほとんど日本製でした。ホテルでは、またも海外に来たことを実感するイベントが発生しました。

ホテルからの景色は少し怖かったです。

晩御飯はタイっぽい感じのところに入り、牡蠣と卵を焼いたなにかと、おすすめされていた海老を食べました。海老がとても大きくてびっくりでした。

セブンイレブンは日本とわりと似ていました。ya domあるかな？と思って聞いたらあったので、3本購入しました。

Day1

Registration

Registrationは9時から10時半なので、8時40分にロビーに集合し、Grabでタクシーを呼びました。朝ごはんは各々でした。日本から持ち込んでいたUFOを食べました。

タクシーがなかなか捕まらず、待ち時間も長かったので着いたのは9時45分くらいだったと思います。スポンサーブースでスポンサーと話していろいろもらいました。日本から来たと言うと、だいぶ嬉しそうにしてくれました。少し日本語が話せる人もいました。

ttamxとも再会し、日本から持ち込んでいたどらやきを、そのチームメイトにも配りました。Day2含め、話した人のほとんど(30人くらい？)にどらやきを配ったのですが、元々どらやきを知っている人が多かったです。聞くには、ドラえもんがかなり有名そうでした。

開会式

開会式があり、学長の挨拶(！？)、スポンサーセッションや、上記のコンテストの詳細ルールが発表されました。

開会式の最中、 Kriz Wu が1つ後ろの列にいることに気づき、エンカしました。HCMUSのキーホルダーをもらいました、かわいい。

式の終盤、前述の国王母の件で、黙祷を行いました。これ以外で、なにか制限はなかったです。

食堂っぽいところに移動し、昼ご飯を食べました。味はバターっぽい感じの味で、脂っこくて少し残しました。チキンの方はおいしかったです。食堂では机の上に平然と鳩がいました。

リハーサル

問題

問題は以下の通りです。(記憶が間違ってたらすみません)

A

1000桁以下の正整数が100000個与えられる。総和をmod1250で出力。

B

万有引力に関して3つくらい値が与えられるので、なにかを計算する問題(僕は読んでないのであまり覚えてないです)。 チームメイトが式変形したものが \sqrt{MG/d}/d みたいな形になってた気がする。

C

N個の商品がある。i番目の商品の値段はAi円。10Ai円以上持ってるときにAi円の商品を変える(買うとAi円手持ちが減る)。今M円持ってるので、最大何個買えるか。

D

インタラクティブ。N×Nのマスのどこかに駒がある。(x,y)を投げると、xまたはyの少なくとも一方があってればyesが返ってくる。N+1回の質問で当てる。

流れ

隣のチームのチーム名が"OniChannnn"だったので気になってたのですが本番も来てませんでした。

リハーサルはfirefoxを開くところから始まりました。IDとパスワードはいつもの"Do not touch anything" の紙の裏に書かれてました。問題は封筒の中に入ってました。リハーサルはガチる必要なくてあくまでも確認だけするつもりでした。

最初、pcは真ん中にあったのですが、途中で左に動かしました。

リハーサル開始と同時に、Gandalにブラウザ, vscodiumを開いてログインするところまでを説明しました。問題の封筒を開けて配りました。Aをitokoiが読み、私はCを読みました。settingを終えたgandalがBを読みました。

Cがソートしてにぶたんやるだけだったので書きました、AC。

Aは、itokoiが「これなんですか？」と聞いてきました。見ると、C++のcin高速化の方法などが書かれていたので、それのPython版だろう。TLも0.3sだった。いろいろ試してもらったがREとかが出てた気がします。結局、その呪文を付けなかったらACしました。ほんとになんだったんだろう。itokoiがやることなくなったあとにスマホで調べてました。

おそらく、普通にint(input())して総和とあまりを取るとそれを付けないとだめなのだろう、と思ってやってみたけど、まぁ最後まで使い方がよくわからない呪文でした。解法は文字列として受け取って下4桁やるだけで、itokoiが考察・実装。

Bも式変形をすると求めたいものはすぐわかり、誤差だけ怖いねーという問題だった。Gandalが考察・実装するもWA。

itokoiがDを読んでたのでそれを聞き、itokoiにGandalを手伝ってもらった。Dは(i,i)を全部聞いたら高々2通りになるのであと1回で一方の可能性を消すだけになる。先にDを実装してAC。

2人がBを考えている間に、pb_dsやrope、QCFium法、ライブラリのhashが動くことを確認しました。

gandalがいろいろ試すもたぶん誤差落ち。

結局僕が入って、いろいろ試して連投すると通りました。13ペナとかだったと思います。結局、全部sqrtしたあとに計算したほうが精度が上がったはず。正解したときには順位表が凍結していたので、Kriz Wuとかに心配されました。リハーサル後はかなり自由に写真を撮りました。翌日使うものを置いて帰りました。 Kriz Wuたちのチーム HCMUS-AleaJactaEst や ttamx とマスコットで戯れ、Demen100nsともエンカしました。

Day1解散後

リハーサル後は、コーチが調べて出てきた、ワット・ポー(涅槃寺)に電車を使って向かいました。

電車の切符購入は反応が悪くて苦戦しました。

寺はめっちゃよかったです。東大寺以上にスケールの大きい仏や、多くの金色の仏像。建築は仏像と違ってかなり細かくカラフルで、イスラムやロシアっぽさも感じました。

中では屋台もあり、コーチはなにやらよくわからないものを買っていました。食べた感想は「ハイボールに合う」だそうです。

https://x.com/Sophia_maki/status/1984558607334342893

私はマンゴーとココナッツのミックスのソフトクリームを買いました、とてもおいしかったです。

涅槃仏の建物に入ると、近くに日本人がいるようで、日本語が聞こえてきました。「足の裏が本質」と聞こえてきた気がして、見ると、ここにも細かな絵が描かれていてすごかったです。

寺の中にも、国王や国王の母の写真が多く飾られていました。

その後はバスに乗ってホテルに帰りました。バスは乗りこむと同時に出発するので日本に比べるとちょっと危ないです。運転手のほかにもう1人いて、どこまで行くかを聞かれ、お金を払いました。

そしてホテルから歩いていけるスーパー(？)に向かってお土産を買いました。食品やおむつ、扇風機まで、毎列に日本製品がありました。タイ限定の味のコアラのマーチと、ドイカムという有名なメーカーのドライマンゴー、それからya domを爆買いしました。

タイっぽい店に入り、晩御飯を食べました。最初は匂いが苦手だったのですが徐々に慣れました。飲み物はタイコーヒーを頼みました。とても甘く、最初はおいしかったのですが、徐々に飽きてしまいました。チキンはおいしかったです。

その後、男3人でマッサージに出かけました。gandalと私はfixstarsの服を着ていて、2人で同じ店に入ったので「社員旅行みたい」「いやっすよ笑」なんてことを話していました。タイ古式マッサージを選択し、暗い奥の部屋に入って若い男の人にしっかりほぐされました。かなり良かったです。

夜食に日本から持ってきたカレーヌードルを食べて就寝しました。

Day2

7時にRegistration開始、8時にコンテスト開始というかなりやばいスケジュールです。6時半にチェックアウト、そしてタクシーで会場に向かいました。Registration後、Kriz Wuらとだべって過ごしました。

コンテスト本番

gandalにsettingをしてもらう予定が、ログインなどはリハーサルと違ってすでにされていました。

また、事前にdiscordで連絡があったのですが、計算用紙はライブラリに数えるため、預かられていました。

序盤

gandalには当初と予定を変えてテンプレートを書いてもらいました。itokoiはAを読むつもりだったのですが、僕がざっと見た感じI, J, Nが問題が短かったので、itokoiにIを読ませ、私はJを読みました。Jは明らかに後回し問題です。マクローリン展開で誤差が無視できる範囲になるまで近似するんだろうなーと察していったん捨てました。

itokoiにIの問題を教えてもらい、考察を始めました。テンプレートを書き終えたgandalにNを読ませたところすぐ解けたというので実装、AC。

N: gandal 0:11

itokoiはすでに別の問題を読み、gandalも他の問題を読み進めました。

その後、Iの考察ができた私が実装を始めたのですが、WA。ここでかなり時間を使ってしまったのは少し反省。itokoiがBを解けたというので実装するがWA。

Iが地雷だと思ったので、gandalが読んでいたなかで、順位表で解かれていたMをいったん聞きました。well-definedからかけ離れていたので誤読を疑って読み直させました。itokoiがBがわからないというので聞くと、N個の本から右端以外の1冊を右端に移動させるのをM回行うことで昇順に、とような問題だったので、N=2が例外で偶奇になることを伝え、実装してもらいました。AC。

B: itokoi 0:48

Mを再度聞くと、すぐにライブラリとして持ち込んだ永続AVLで解けることはわかりました。そして、fenwick treeで解けることがすぐわかりました。

itokoiが先にCが解けたようで、実装してもらったのですが、少しバグっているようで、先にMを実装してAC。Cのバグも見つかったようでAC。fenwick treeは昨年から私がソラで書くことにしています。

ちなみに、Cは他のチームはかなり苦戦していたようで、終了後、「Cどうやってそんなに早く解いたの？」と聞かれました。itokoiは「簡単だったので…」と言ってたので、My teammate said, "Because it was easy." と答えました。

M: shinchan 1:09

C: itokoi 1:10

その後Iのバグを見つけたので修正すると、AC。

I: shinchan 1:24

ちなみにこの時点で順位表では5位でした。

開始90分時点で6位だったようです。(ICPC APACのインスタより)

中盤

Gが解かれていたのでgandalから聞いて考えていたのですが、まぁ求めたいものは直径なのでいつも通りdfsを2回やってみました。2つの頂点を選ぶとき、それが相異なる必要があるかどうかが問題からはわからなかったため、clarを投げてみると、yesが返ってきました。提出結果はWAで、その後いろいろ試みてもWAでした。順位表を見て、Hをitokoiから聞き、Eをgandalから聞き、Gについてitokoiに反例を探ってもらいました。

Hは O(X \sqrt{X} \log{X}) とかになってほんまか？となったのと、実装もしんどいのでいったん後回し。Eは本当にわからなかったので結局Gを考えました。そうこうしているとGの反例をitokoiを見つけてくれて、やっぱり座標を考慮して1つ目の頂点を決める必要があるなとなり、過去の薄い記憶からx, y, zの±の寄与を8通り試してみたところ、ACしました。もちろん未証明です。まぁ、他のチームがみんなノーペナで通してるのに我々だけ2ペナしてるのも変な話なので、どうせこれやろ、えいっの気持ちでした。

G: shinchan 3:05

終盤

itokoiがEの解法を生やして、納得しました。TLが少しきつそうなので私が実装することに。かなり実装がきつかったのですがなんとかサンプルが通り提出するもWA。HはTL的には大丈夫そうな解法が生えたのですが、MLEすることに気づきました。それに実装もやばいです。その後は時間もなかったのでとにかく3人でEを通しきることに徹したのですが、通りませんでした。

終了後

終わったあと、チームメイトが「5時間って短いですね」と言いました。これはかなりいい成長だと思いました。もう十分5時間コンテストに慣れていて、5時間集中しきったこと。そして、各々が自分のやることを自分で見つけ、最低1問通したこと。それだけで、今回挑戦して良かったと感じました。

コンテスト後はかなり自由だったのでttamxに私のチームのpcでEのコードを読んでもらったのですが、なぜWAなのかわかりませんでした。Hはshort型を乗せたfenwick treeでMLに耐えるといわれ、さすがに想定じゃないろ笑という気持ちになったが、そうでもして通さないとなという気持ちにもなった。ttamxのチームのコーチが実は阪大で博士を取ったようで、うちのコーチと日本語で話していました。

ttamxと話したのはそれが最後で、2027年のAPACが東京で開催される旨を伝えました。日本にまた行けることをとても喜んでいて、私もボランティアで参加しているだろうからまた会えるのを楽しみにしていると伝えました。

タイの高専の学生がいて、日本語で話しかけられました。Mの解法を教えてほしいというのでfenwick treeを使ったと教えました。また、驚くことに、APACの存在を知らないというのです。タイ国内のチームでもお金がかかるけど、単にRegionalに参加するのが目的なんだなーと思いました。その分タイ国内の参加チームも少ないですが。

その後はランチタイムです。明らかにアジアっぽくない顔をした3人のチームがいたので聞くと、エルサルバドル、ジョージア、アイスランドからタイへの留学生チームでした。タイのスタッフの方も交えて話しました。アイスランド人めっちゃイケメンだった。

アイスが配られ、ゆず、レモン、ヨーグルトの3種類があったのでヨーグルトにしました。Yuzuと書かれていてここにも日本語か、と。

総評・表彰式

合間に、席が近かったベトナムチームのNEU.Anarchaosの3人と話しました。Codeforces上のタイの過去問に必ず現れる名前として認知してくれてました。

運営の想定難易度と順位がおおむね一致していて、内容もなかなかいいセットだったと思います。yes/noも終盤に入り、優勝争いはソウル大2チームの争いとなりました。一番の優勝候補のfloorsumをJust use CRTが不可能枠のAを通して抜いたときは会場の拍手がすごかったです。

https://icpc-chula.github.io/scoreboard-archive/2025/

解散後

次の場所も決まってなかったのでその場にいたタイのチームとしゃべってました。「大きい荷物があってあまり歩けないんだけど3時間くらいつぶせる場所ないか」と聞くと大学に北にある大型ショッピングモール、サイアム・パラゴンを勧められて、そこに向かうことに。日本のものが多くて面白かったです。涼しかったし座れるところが多かったので休むのにちょうどよかったです。

空港に向かいました。ここでも日本語の店が多々ありました。

空いてたので中華に入り、水餃子を食べました。空港のごはんはやはり高いのですが、その分日本に近い味付けで食べやすかったです。

空港での待ち時間で、チームメイトから残りの問題を聞いて解いてみました。問題を一通り読み終えていてえらい。

Lを聞くと、一瞬で解法が生えてしまい、顔ない。

続いてFを聞くと、これも一瞬で解法が生えてしまい、顔ない。

ttamxから連絡がきて、Eのコーナーケース(実装によっては)を教えてもらいました。完全に理解しました。

自分で読んでいたJも考えてみました。式変形をすると解けました。顔ない。高専・工学部出身者がマクローリン展開に手を付けなくてどうするんだという気持ちになってしまった。

Dを聞きました。やりたいことはすぐわかるのですが…。と30分くらい考えてると解けました、顔ない。まぁDは実装に時間かかりそうなのでさすがに今のチームでコンテスト中に解けることはなさそうです。

Kはコンテスト中に聞いて解けないと確信していたので、インタラクティブであるAを聞きました。飛行機でも寝ながら考えたのですがダメでした。さすがにA, Kは運営の想定通り不可能枠です。

そんな感じで10時くらいに帰国、14時くらいに帰宅しました。

問題

ぜひ解いてみてください。(来週こどふぉのgymにuploadされるらしいです。) 不明瞭なところがあれば教えてください。解説は後日追記するかも。Nは読んでないです(一番簡単問題なので飛ばします)。A, K以外はたぶん解けた。ちなみに14問中5問は想定がセグ木です。

運営の想定難易度は、

簡単 : BN

普通 : CEGHILM

難しい : DFJ

不可能 : AK

だったのですが、私の体感はN<B<M<C=I<F<L<G=J<D<E<H<A<Kです。Kriz Wuは"N-B-M-G-L-I-E-C-H-D- A-K (F idk, but should be easier than D)"だそうです。

A

問題文

インタラクティブ。N(<=100)が与えられる。ジャッジが順列pをもっている。

こっちから順列qを与えると、長さNの数列s(最初すべて0)に対してi=1から順に以下を実行。

s_q_iが0なら、s_p_q_iを1にする。

結果のsが帰ってくる。400回でpを特定。

B

問題文

N<=105, M<=109が与えられる。

以下を満たすような長さNの辞書順最大の順列を出力。

順列の右端以外の要素を1つ選んで右端に移動。をちょうどM回繰り返すことで、昇順に並び変えることが可能。

C

問題文

abs(X) <= 200000が与えられる。1-2+3-4みたいな感じでプラスかマイナスを挟んでXを構築。長さが最小のものを出力。

D

問題文

また、長さN(<=500000)の数列Pも与えられる。

R(<=109)匹のモンスターを使ってゲームを行う。現在の体力がAi。体力が正のモンスターを選ぶ。i番目のモンスターを選ぶと、体力がP[A[i]]だけ減る。操作できないほうの負け。

後手は勝つために、最初にどれか1つのモンスターの体力をK減らす。

そのままだと先手が勝ち、操作によって後手が勝つようになるような数列A (0<=Ai <= N)の個数。

E

問題文

N<=100, M<=10000, Q<=100000が与えられ、N頂点M辺の有効グラフが与えられる。辺の形式はu, v, p, hである。hは重みで、pについては後述。

Q個のクエリが与えられる。

type1のクエリは、u, hが与えられるので、ある閾値であって、頂点uから、pが閾値以下であるような辺だけをたどっていくときの最遠点までの距離がh以下であるような最小のpを求める。

type2のクエリは、hだけが与えられるので、ある閾値であって、ある始点uが存在して、pが閾値以下であるような辺だけをたどっていくときの最遠点までの距離がh以下であるような最小の閾値を求めたとき、閾値の最小値とそれをなす最小のuを求める。

F

問題文

N<= 200000, W<=1018と、N個のアイテムvi(<=109), wi(<=1018)が与えられる。ただし、sum(wi)<=1018, w[i]>=w[i+1]

閾値を決めて、viが閾値より上かつ重みに余裕があれば入れるような貪欲ナップザックを行う。

価値を最大化するような閾値のうち、最小値。

G

問題文

辺重み付きの木と頂点それぞれの(3次元)座標が与えられる。2頂点選んだときの、(マンハッタン距離+パスの辺重み総和)の最大値。N<=200000。

H

問題文

TL4s。

長さN(<=50000)の数列A (Ai<=100000) が与えられる。狭義単調増加、さらに隣接する要素の差も狭義単調増加になるような長さが最大の部分列を1つ出力。

I

問題文 I, C, Pからなる文字列S(len(S)<=200000)から、できるだけ多くの独立な部分列ICPCを作る。

J

問題文

N<=200000と数列Aが与えられる。

\sum_{i < j} \sqrt{A_i + A_j}

K

問題文

R×C (<=109)の座標があり、(N, M)から右上に向かって撃つ。隅に行くまでに通った格子点の数。

テストケース数100000。

L

問題文

N, Q<=200000。A, B<=109

N個の座標(x, y)にciという値がある。(xi, yi <= 109、ci <= 1018)

Q個の座標(s, t) (s, t <= 109)が与えられるので、各クエリについて、

min_i (A abs(xi - s) + B abs(yi - t) + ci) を出力。

M

問題文

空の配列があって、i=1..Nに対して以下を行ったあとの配列が入力で与えられる(N<=200000)。

iを左端に追加。左からj番目までを右に持ってくる。

入力の配列になるような操作列(jの列)を求めよ。

感想

自分はこの半年間で本当にいろんな人にお世話になって、迷惑をかけたと思います。しかし、それでも譲れないものを通しきった自分を褒めたい想いです。競技プログラミングを続けてよかったと今なら思えます。

コンテストは結果だけ見れば、残念な結果でした。私が解ける問題はA, K, E, Hを除いた10問で、順位表に惑わされなければ9完は全然あったなと思いました。しかしそれは順位表マジックではなく、順位表と運営の想定難易度は一致していました。東南アジアの得意と僕の得意が違うのかなと思います。1人が強いチームというのはその人次第でチームの調子ががらっと変わってしまうため、今回のようなことはおそらく頻繁に起こると思います。キーボードもタイピングがかなり困難で、自分の強みである実装の精度をうまく活かすことができなかったのも1つの要因です。site scoreが低いことも、それらも含めて運命です。

海外Regionalに参加する人は、必ずマイノリティになるので、順位表を見て動くのではなく、いつも以上に順位表をかき乱す側にならなければならないと思いました。

内容を見れば、今回は十分成功だったと思います。約50日間の、チームメイトの成長をとても感じられる日々でした。itokoiは来年のCodeQUEENで優勝してくれることでしょう。優勝してください。

ICPCを引退してしまいました

shinchanです。2025年3月でICPC現役を引退していたようです(？)。せっかくなので軽く振り返りをします。

1年目(2020/21, 高専4年)

明石高専にいました。クラスメートをレート順に3人集めたら全員早生まれでした。なので参加チームの中で最年少チームと言えるでしょう。ちなみに高専生の早生まれ率は異常で、クラスメートでレート順上位6人中5人くらい早生まれだと思います。

国内予選とRegional参加記は以下の通りです。

https://shinchankosen.hatenadiary.jp/entry/2020/11/07/010225

https://shinchankosen.hatenadiary.jp/entry/2021/03/17/234856

チーム名はappearedです。たぶんおーじがapiadっぽい名前にしたはず。

メンバーは エカスド , おーじ, shinchanの3人です。エカスドだけ黄色、他2人が青下位でした。エカスドはなんでもできる、おーじは実装が得意、僕が考察が得意という位置づけで、その他の得意な分野もいい感じに分かれてて、チームワークがかなり発揮できた1年だったと思います。

国内予選では、A, Bを早解きが得意なおーじが担当し、Cがshinchan, Dがエカスドでした。ABが順調に通り、Cも国内予選特有の激重プログラムで通し、Dは3人で分担して通しました。31位でした。

Regionalはオンラインだったのでちょっと残念がりながら出たのを覚えています。なにより、KINGの無双は今でもよく覚えています。25位でした。

2年目(2021/22, 高専5年)

1年目と同じチームのappearedで出ました。レートがおーじと入れ替わってました。国内予選では、A,Bは余裕で、Cから急に重い感じでした。C, D, Eを3人で分担していて、Cは全方位木DPなのはわかるけどまじで書きたくなかった(というか書ける自信がなかった)です。D, Eを担当していたおーじとエカスドが解けたというので2人を応援していたら終了しました(えっ？)。77位でした。まじでもったいない年。

3年目(2022/23, 学部3年)

大阪大学工学部電子情報工学科というところに編入しました。高専時代のクラスメート(同じ研究室でもある)で一緒に同じところに編入した3人で一緒に出ました。

tako, おーじ, shinchanの3人で、黄色間近だったshinchanが一番レートが高くなってしまいました。この年も3人とも早生まれです。

3人の研究テーマだったものをチーム名にしました。Chordal_Ringです。

この年は阪大内レート順で4番目くらいのチームだったし、他2人が引退気味だったため、完全に思い出って感じで参加しました。

このとき、自分が6回参加可能であるということを多方面に確認したのはよく覚えています。まぁこの時点ではコロナ禍特例の廃止は正本にも書かれてなかったので誰も悪くないのですが(確認した相手も今回一緒に引退になってしまった側)。

内容はなにも覚えてないです。89位でした。

この年、初めてオンサイトに行くことができました。DDCCさん感謝しています。他にも、トヨタのオンサイトにも翌年と合わせて2回行くことができました。

4年目(2023/24, 学部4年)

この年から本番って感じです。阪大レート順2軍チームです。メンバーはDaylight, KowerKoint, shinchanの黄色3人です。チーム名はkotamanegi_mijingiriです。この年はなぜか自炊スキルが上がりました、特に玉ねぎを使ったチャーハンをよく作りました。

このとき、野良で競プロをしていてメキメキ実力を伸ばしていたhint908をICPCに誘ったのですが、ギリギリDaylightのレートが上で、ちょっと申し訳ないことをしたと思っています。国内予選ではhint908が強くて3軍に負けました。まぁ3チームともRegional行けたのでヨシ。

DaylightとKowerKointは僕と違って考察とかよりパソコンが好きって感じで、実装型でした。2人とも普段からUSキーボードを使用し、Neovimという当時聞いたことなかったエディタを使ってました。なので、shinchanは実装をしないことにしていました。

いろいろあって運良く繰り上がってAsia Pacific Chanpionship(以下、APAC)に進むことができました。これによって、World Finalsが実はすぐ近くに来ていると錯覚できました。

国内予選21位、Regional 20位、APAC 40位。

国内予選, Regional, APACの参加記はこちら。

https://shinchankosen.hatenadiary.jp/entry/2023/07/08/091950

https://shinchankosen.hatenadiary.jp/entry/2023/11/27/151320

https://shinchankosen.hatenadiary.jp/entry/2024/03/10/120237

5年目(2024/25, 修士1年)

kotamanegi_hint_kureya=hint908+Daylight+shinchan、同級生3人チームです。余り物2軍チームでもあります(いつもの)。

チームメイトから実装をするように言われたので鍛えていたら、かなり実力の向上を感じられました。本当に3人ともよくがんばった1年だったと思います。シンガポールも楽しかったです。結果は国内予選がピークでしたが。

海外チームとの交流いっぱいしました。楽しかったです。

国内予選5位、Regional 12位、APAC 47位。

もろもろの参加記は以下。

模擬国内

国内予選

JAG夏合宿

Regional

APAC

チーム振り返り

さぁ、来年もがんばるぞ！

6年目(2025/26, 修士2年)

The World of kotamanegi=Nachia+KowerKoint+shinchan

の予定でした。チームでの練習も3ヶ月くらいしてました。毎週Nachia様の格言を聞けるのはとても良い体験でした。

さて、参加登録の時期ですね。おや…？特例廃止…？

というわけで引退になってしまいました。だれも正本をちゃんと読めていなかったらしい。まわりの勧めもあって一応ゴネてはみたがもちろんダメでした。

脳内に千の風になってが流れた。

残ったチームメイトについては、新しいチームが組まれ、私の名前をWFに連れていってくれるようです、感謝…。

https://jag-icpc.org/?2025%2FTeams%2FList

自分のこれまで

ここまでかなりほがらかに書いたのですが、引退が決まった直後は本当に辛かったです。

昔話をするのですが、私は中2くらいの頃が自分にとって一番しんどい時期で、それがあったから今回も「あのときに比べれば…」となりました。中学時代はサッカー部だったので、まぁ運動部だと厳しいのは当然ではあるのですが、、という感じです。運動部を経験しているということは今となっては様々なところで活きています、高専時代も、競プロでも、就活でも。ただ、もっと楽しくしたかった、またはもっと結果を残したかった、という気持ちが大きく残りました。

小学生のときピアノを習っていた関係で、高専ではもう一度音楽がしたいと思い、雰囲気が一番自分に合ってると思った吹奏楽部に入りました。辛いこともありましたが、楽しかったです。しかし、最後の演奏会はコロナでなくなってしまい、またきれいに引退することができなかった…。

コロナ禍になってからは、ひたすら競プロでした。時は流れて現在、コロナ禍特例の廃止による引退…。またきれいに引退することができなかった。

WFに行けなかったという結果面もそうですが、負けてもいいからきれいさっぱりという気持ちになりたかったなって思います。

それからというもの、週30時間以上の時間が突然虚無に変わり、とりあえず鬱アニメとプリキュアを交互に見たことで元気になりました。

これから

これからどうするべきか…。いろんな人に相談した。実はわりとすぐに見つかった。吹奏楽でちょうどいいイベントが存在したので、それに向けて頑張るつもりだ。このイベントはまだ公開情報じゃないと思うので詳しくは伏せておくが、コロナによってできなかったことを取り戻そうとする動きだ。学生最後の学年をそれで締めくくることができるのはどういう偶然かな。

また、コロナ禍という制約がなくなったこと、自分は既に大学院生でお金にゆとりができたことで、そういったお金のかかる趣味ももっと取り組んでいこうと思えた。ラブライブ！サンシャイン!!のfinaleライブが来週末にある。離れきってたため知ったのが最近だったからライビュだけ行くつもりです。後方腕組みオタクになってそう。

元々、高専1,2年のときは主に吹奏楽とラブライブって感じの人間で、古参フォロワーのみなさんはわりと覚えてくれてると思う。それが数年かけて競プロに変わっていった。今回の件で、昔の自分に戻っていくのかなって思いました。

競プロはとりあえずAtCoder橙になるまでは続けるつもりです。

世界と戦うなにかに取り組めたことはかけがいのない経験で、あと少しのところまで届いた。学生が終わることで難しくはなるけど、競プロか、もしくは別のなにかで、世界を目指せたらいいなって思う。

追記

今回引退となった理由について、補足しておきます。

https://icpc.jp/2025/eligibility/ (今年度の日本のICPC参加資格)

https://icpc.global/regionals/rules (ICPCルール正本)

https://icpc.jp/2024/domestic/registration/eligibility/ (昨年度の日本のICPC参加資格)

  • ICPCのルールは2019年度までは、現役入学してる早生まれならM2の学年でも出れる(回数は5回まで)というものだった

  • コロナ禍特例により、2020年度以降、「2020年度を1回に数えない」「2021, 2022年度は合わせて1回と数える」が追加された

  • 実際、過去この特例によって6回参加した人は少なくない

  • 今年度、なぜか上記の2つの特例が一気に廃止されることになった。これにより、6回目の参加をしようとしていた者が、意図せず参加資格を失うことになった

  • たしかに、2023年度から正本に、特例が2025年度以降廃止されると書いてあった(This exception will be removed from the regional year 2025/26.)

  • 昨年度の日本のICPCの参加資格ページでは、「ICPCへの参加資格は、世界統一ルールで決まっています。参加資格ルールの正本はICPC世界サイトで確認してください。このページは、横浜大会実行委員会の責任で、国内予選の参加資格をわかりやすく説明したものです。」と記述があるものの、2025年度以降特例が廃止という旨は書かれていない。(これについて、この差異に気付けた人が自分の観測範囲でいなかったというのはそれは日本のICPC側の書き方が悪くない？より多くの参加者を募りたいためにルールを簡単にしている意図はわかるけど、これまでたくさん精進してきた僕らやチームメイトの気持ちが阻害されてない？という気持ちです。)

ICPC参加資格の正本はだいたい日本の参加登録が終わる頃(終わったあと？)にその年度のものに更新されるため、2023年度の正本のその記述には気付けないのはそれはそう。2024年度、正本を正しく読み、出るか出ないかの選択を正しく行うべきだったということです。

CodeChef STARTARS 187 P5, P6: Minimize Tree GCD 別解

問題

問題URL

(EASY) https://www.codechef.com/problems/MINGCTREE0

(HARD) https://www.codechef.com/problems/MINGCTREE

入力で数列 A と木が与えられる。 A を並び替えることで、木の上の辺 (i, j) について A_i + A_j の総GCDを最小化する。

hardでは、数列の末尾が与えられず、代わりに整数 M が与えられるので、 i=1..M について A_N=i としたときの上記の問題について答える。

解法

ネタバレ注意













EASY

乱択で並び替えるだけです。

正当性を考えます。

gcdになるかもしれない値を固定して g とします。 A_i を g で割ったあまりで分類すると、ある値 x を使用して、 x または g-x で書けることが答えがgになりうる必要条件です。

x=0 のときや、 x=\frac{g}{2} のとき、答えは自明に g になるのでそれ以外の場合を考えます。

g になるのは、各辺の端点が x と g-x である必要があります。つまり交互になる必要があるのですが、 N が大きいとき、確率的にはかなり低そうに見えます。

各 g において交互になる確率を独立に求めて足すことを考えても、乱択が通用しそうという気持ちになります。書いてみます、ACおめでとう。

HARD

上記のEASYの解説を前提として進みます。

HARDについては、 A_N にに対応する頂点と隣接しない頂点については、先にgcdをEASYのときと同様に求めておきます。 A_N に対応する頂点と隣接する頂点の A_i の値を別の配列で管理(vecとする)しておくと、辺の値は A_N+vec_j ~(j=0, 1, 2...) となります。これの総gcdは、 i=A_N を決めてから求めると遅いため、今の段階でできることをします。

vecの要素同士の差分のgcdを求めて置けば、あとはその値と A_N+vec_0 と、最初に求めて置いた、隣接していない頂点の分のgcdのgcdを求めれば答えになります。

実装例

EASY https://www.codechef.com/viewsolution/1161208631

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)

class random_devicer {
    int seed;
    std::mt19937 engine;
public:
    random_devicer(const int seed = 0): seed(seed), engine(seed) {}
    int next(int lower, int upper) {
        std::uniform_int_distribution<> dist(lower, upper);
        return dist(engine);
    }
};

void solve() {
    random_devicer rnd(42);
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<pair<int, int>> edges;
    rep(i, n - 1) {
        int x, y; cin >> x >> y;
        x --; y --;
        edges.push_back({x, y});
    }
    vector<int> ord(n, 0);
    iota(ord.begin(), ord.end(), 0);
    int ans = 1 << 20;
    rep(_, 20) {
        rep(__, n * 2 + 10) {
            swap(ord[rnd.next(0, n - 1)], ord[rnd.next(0, n - 1)]);
        }
        int num = 0;
        for(auto [x, y] : edges) {
            num = __gcd(num, a[ord[x]] + a[ord[y]]);
        }
        ans = min(ans, num);
    }
    cout << ans << endl;
}
int main() {
    int t; cin >> t;
    rep(i, t) solve();
    return 0;
}

HARD https://www.codechef.com/viewsolution/1161229093

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)

class random_devicer {
    int seed;
    std::mt19937 engine;
public:
    random_devicer(const int seed = 0): seed(seed), engine(seed) {}
    int next(int lower, int upper) {
        std::uniform_int_distribution<> dist(lower, upper);
        return dist(engine);
    }
};


void solve() {
    random_devicer rnd(42);
    int n, m; cin >> n >> m;
    vector<int> a(n);
    rep(i, n - 1) cin >> a[i];
    vector<pair<int, int>> edges;
    rep(i, n - 1) {
        int x, y; cin >> x >> y;
        x --; y --;
        edges.push_back({x, y});
    }
    vector<int> ord(n, 0);
    iota(ord.begin(), ord.end(), 0);
    vector<int> ans(m + 1, 1 << 20);
    rep(_, 30) {
        rep(__, n * 2 + 10) {
            swap(ord[rnd.next(0, n - 1)], ord[rnd.next(0, n - 1)]);
        }
        int num = 0;
        vector<int> vec;
        for(auto [x, y] : edges) {
            if(ord[x] == n - 1 or ord[y] == n - 1) {
                if(ord[x] == n - 1) vec.push_back(a[ord[y]]);
                else vec.push_back(a[ord[x]]);
                continue;
            }
            num = __gcd(num, a[ord[x]] + a[ord[y]]);
        }
        int sz = vec.size();
        rep(i, sz - 1) num = __gcd(num, abs(vec[i] - vec[i + 1]));
        int v = vec[0];
        for(int i = 1; i <= m; i ++) {
            ans[i] = min(ans[i], __gcd(num, v + i));
        }
    }
    for(int i = 1; i <= m; i ++) cout << ans[i] << " ";
    cout << endl;
}
int main() {
    int t; cin >> t;
    rep(i, t) solve();
    return 0;
}

AGC072-D Magician 解説

目次

概要

考察手順を、補足していきます。

公式解説　atcoder.jp

問題

atcoder.jp

解説(ネタバレ注意)

↓

↓

↓

↓

↓

↓

↓

↓

本題(解説)

部分問題

以下の問題が解ければ良いです。

問題文

長さ 2N の順列を N 個構築したい。 それぞれの順列 P は、以下の条件を満たす。

  • 長さ 2N でそれぞれの要素が 0 で初期化された配列 s を用意する。

  • オンラインに飛んでくる a, b (制約は元の問題の通り) に対して、 P における a の位置が b より後ならば、 s_a , そうでないなら s_b を 1 にする。

  • 出来上がる s は a, b の順番によって、カタラン数通り存在。その集合を f(P) とする。

  • 各順列同士で、 f(P) が独立 (共通の s が存在しない) ようにする。

部分問題の導出

a, b がジャッジから飛んできたときにどっちを選ぶかの規則を決めたくなります。例えば、a, bの大きい方を選んで、その場所を1にします。

こうして出来上がる文字列は、0を'(' 、1を')' とすると、括弧列になります。a, bのペアの組み方によって任意の括弧列を導けます。

よって、規則(順列)を文字ごとに定め、出来上がる文字列が、それぞれで重ならないようにすればよいです。

可能であるかどうかを確認してみましょう。(hatenablogのmarkdownでtexを扱う都合上、 binom 関数を以下で定めます)

 binom(x, y) = \begin{pmatrix}
x\\
y
\end{pmatrix} = x C y

括弧列の個数はカタラン数であり、 \frac{binom(2n, n)}{(n+1)} です。

つまり、 binom(2n, n) 個の可能な文字列を、 N 個の規則(順列) が \frac{binom(2n, n)}{(n+1)} 個ずつ占有するため、理論上は可能です。

順列の構築

構築方針は公式解説と異なります。

枝刈り全探索を試みます。枝刈りパートは以下です。

  • 順列を追加するたびに、以下の矛盾判定を行う

  • binom(2n, n) 個の文字列をbit全探索し、複数の順列から生成されうる文字列が存在するとダメ。

  • それぞれの順列から生成される文字列がカタラン数個になることを確認する。

作る N 個の順列を、 N \times 2N の二次元配列 P で表すことにします。

まず、自明に　 P_0 = [ 1, 2, 3, ..., 2N ] としてよいです。

これによって、 ((2N)!)^{2} 通りで、 N=3 が実験できます。

P_{1,0}=3 や P_{2,0}=5 に固定して良さそうだとわかります。反映してもう一度 N=3 を実験します。

P_{1,1}=4 や P_{2,1}=6 に固定して良さそうだとわかります。反映して、 N=4 をやってみます。

P_{1}=[ 3, 4, 5, ..., 2N, 2, 1 ] として良さそうです。反映して、もう一度 N=4 をやってみます。

P_{2}=[ 5, 6, 7, 8=2N, .... ] が可能と予想できます。なんなら、 P_i の先頭 2N-2i 個は、 [ 2i+1, 2i+2, ..., 2N ] が可能と予想できます。反映して、 N=5 を回してみます。以下が最初に出てきます。勝ち確です。

1 2 3 4 5 6 7 8 9 10 
3 4 5 6 7 8 9 10 2 1 
5 6 7 8 9 10 4 1 2 3 
7 8 9 10 6 1 2 3 4 5 
9 10 8 1 2 3 4 5 6 7

つまり、 i > 0 のとき、 P_i = [ 2i + 1, 2i + 2, ..., 2N, 2i, 1, 2, 3, ..., 2i - 1 ] です。

ACおめでとう。

私は合計3時間くらいかかりました。コンテスト中に解けたらアツイ。

実装例

競プロメモ

高速化

  • 配列が2べきだとavxが自動でついたりする

  • monotone minimaはSMAWKより速い

  • オフラインでできることはオフラインでやったほうがいい

  • 区間DP→monge(mongeじゃなくともmonotoneであることを祈る)

  • bitset, _Find_first, _Find_next

  • endlはlog

  • 動的bitset(特にxor基底？)はC++だとvector ullまたはpythonを使うとよい。

    • n<=1, n<=2, n<=4, ..., のような場合分けでstaticも一応可能

  • ropeは文字列のためのデータ構造である(？)。文字列に対しては爆速らしい？

  • BITのlogは定数

  • 同様に、セグ木も速い。setは遅い。

  • フローは想定よりも速くまわる

  • フローだと思ったら貪欲説

  • 再帰は非再帰に

    • DFSをstackで書くとか

  • シーケンシャルアクセス

  • 多次元配列を1次元に

  • マルチテストケースでは配列をグローバルに置いて使い回す

ICPC2024 kotamanegi_hint_kureya 振り返り

大阪大学のICPCチーム、kotamanegi_hint_kureya のshinchanです。

先日参加した ICPC Asia Pacific Championship 2025 で、チームメイトの引退・チーム解散することになったので、1年間の振り返りや戦略について語ろうと思います。

参加記はこちら↓

shinchankosen.hatenadiary.jp

目次

メンバー紹介

3人ともM1で、早生まれの私(shinchan)以外の2人はラストイヤーです。

Daylight

https://atcoder.jp/users/Daylight

AtCoder青黄反復。競プロ歴7年くらい。1人だけJOI本選経験あり。競技プログラミング以外のプログラミングも経験豊富。社畜適性あり。データ構造やグラフの知識が豊富。元々実装や早解きが得意。英語が一番できる。単純なタイピングはたぶん一番速くてライブラリ仕様も一番理解してるので写経は任せていました。

去年もkotamanegi_mijingiriで僕と同じチームでした。

shinchan

https://atcoder.jp/users/shinchan

https://codeforces.com/profile/shinchankosen

https://www.codechef.com/users/shinchankosen

AtCoder黄、Codeforces赤、CodeChef赤。競プロ歴7年くらい。純粋培養。

この記事を書いている。チームの中だと一番精進量が多いと思う。海外コンもわりと埋めている。

むしろARCは数え上げが多すぎるので、メインをCodeforcesに移してもいいなって思ったり。

最近の苦手分野は数え上げと桁DPと難読。数え上げは元々得意のつもりだったけど、暖色になるとまわりに数オリ勢が多すぎて、相対的に苦手になりがち。

これといった得意不得意分野は正直特にないつもりで、安定が自分のいいところだと思ってる。でもARCより海外コンやAGCの方が明らかに得意なのは、数え上げが苦手なんだなって。

以前まで実装がとても苦手だったが、ここ1年で大きく向上した。

強いていえば得意分野は構築だと昔から思ってる。Codeforcesにありがちなエスパーとかギャグとかは大好き。ICPCでは、自分やチームメイトのコードのバグを見つけたり、コーナーケースを見つけたりするのが得意だと感じた。

練習日や練習内容を決めたりなにかを提案、指示するのは基本僕だった。

hint908

https://atcoder.jp/users/hint908

AtCoder黄橙反復。競プロ歴3年くらい。純粋培養。

元々細々と競プロをしていたらしいが、おそらく僕の影響でratedに出始めた？

去年度のICPCの話をすると、阪大から3チームregionalに出られたのは阪大が強くなったというより、成長途中で3軍にいたhint908が強かったから。ICPCに僕から誘ってそのときのレート順で3軍になってしまったのは少し申し訳ないが、その分今年組めて良かったと思う。

単純に賢いなーって思う。hint908が調子いいだけでこの世のすべてに勝てる予感がする。可能枠を埋めるのがshinchanの役目だとしたら+1,2問の高難度を通すのがhint908の役目。

同じ問題を3人それぞれ解くとしよう。shinchanはバグらせにくく安定した考察と安定した実装。shinchanに比べて、実装量は長くなってしまうが実装そのもののスピードが速いのがDaylight。2人に比べてなんかよくわからないめっちゃシンプルな解法で実装するのがhint908。

それぞれ別々の強みが早解きにつながり、ICPC国内予選5位、Yokohama Regional開始1時間時点3位などにつながったと感じる。

対策

チーム結成直後

チームで

チーム結成時、とりあえずdiscordの鯖を作りました。discordはコンテストごとにチャンネルを作ったり、なにかしら目を通してほしいことは一般、見なくて良いがメモを残したいときはmemo、ライブラリ整備や練習することリストは「やることリスト」というチャンネルでそれぞれ発言していました。

そして、チームメイトに「shinchanはどうあってほしいか？どうあるべきか？」を聞きました。去年度kotamanegi_mijingiriのときはといえば、KowerKointとDaylightに実装を丸投げし、考察一本でやっていました。

Daylightからの返答は、「shinchanとhint908にも実装ができるようになってほしい」というものでした。自分はこれに賛成でした。OUPC2023のときに「Daylightが問題を読んでshinchanが考察してKowerKointが実装した」という話をしたら双子に怒られたこともあり、3並列が理想なのでは？と考えるようになりました。

個人で

昨年のICPC APAC参加チームを中心に、部内でもっと精進しようという動きがあったので、Codeforcesのバチャを週2でやることになりました。半年ほどで終わってしまいましたが、実装力、考察力ともに大きく向上したように思います。

さらに、部内というか某研究室を中心に、CodeChefの文化が広がり、毎週水曜にでて、部員同士の対面での交流が活発になりました。チームワークに少なからず影響していると思います。 インドにでることでスキル面で得たものは正直特にないかな…。すぐに赤になり、今は2600を超えました。

また、「これやってねぇな」って思うことを埋めていきました。具体的には以下の記事に書いてるとおり、よく聞くけど履修してないアルゴリズムだったり、AtCoder黄diff以下埋めをやったりしました。

shinchankosen.hatenadiary.jp

ICPCとは関係ないチームを組んでucupにも出ました。

その一方で

忙しい。

3月から某企業でアルバイトを始め、TAや授業も増え、学会発表もあった。週20時間近くの労働の上に授業、研究、毎週の研究室内ミーティング、毎週の共同研究先とのミーティング。土日と夜は空いており、「なんで社会は夜と土日は動いてないんだ」という謎の発言を繰り返していた。もちろんその時間は全部競プロに使ったけど。

チームメイト2人も同様に忙しそうだった。それでもがんばって、バイトを休んだりしながら時間を作って国内予選までにチーム練を3回ほどやった。 国内予選参加記はこちら。

shinchankosen.hatenadiary.jp

Regionalまで

TAは前期で終え、学会は後期にもあったが土日含めて20連登校することでなんとか処理し、バイトも7月で辞めて競プロを無理やりした。

チームメイト2人にも時間ができたようで、JAG夏合宿の結果への危機感から、ucupに3人で出ることに。

やったことはだいたいここに書いてる。

shinchankosen.hatenadiary.jp

個人では、海外コンにほぼ毎回でるようになり、solved.acのclass7, 8を埋めていった。

そして、日本のICPC過去問も埋めていった。

APACまで

チーム練では、ucupは回によって質が大きく下がったりしていて、海外regional過去問をvnojやqojやcodeforcesのgymで走った方がいいな？となって、土日を使って毎週2つずつ走りました。

個人でも、Asia Pacific地域のRegional過去問を埋めていき、チームメイトにもそのように指示しました。

特に、自分はベトナムを埋めていき、hint908には韓国を埋めさせました。regional過去問をいくつか走ったときに、毎年共通して苦手意識が出たのがベトナムであり、昨年のAPACで知識不足を感じたのが韓国典型でした。わからなかった問題は適宜共有してお互いに解いたりしてました。

ライブラリ

Daylightには、ライブラリ整備を頼みました。とはいっても、なにが必要だとか、分野によっては私が口出し、準備していました。

Daylightも11月頃、昨年度のmijingiriのライブラリを僕たち仕様に改変してくれていて、さらにkuhaku先生のスパルタ指導を受けていたそう。

ライブラリはAPAC直前にvwxyz先生とNachia先生に見ていただきました。ありがとうございます。

github.com

notebook.pdfが印刷して持ち込んだものです。wavelet matrixと遅延セグ木が一部build時に欠損しています。

追記 tatyam先生が対策してくださりました。ありがとうございます。

github.com

戦略

序盤

DaylightはAを見る。shinchanはBから読む。hint908は後ろから。

適宜順位表を確認して、解かれたものがあったらその都度コミュニケーションを取り、読むor読ませます。このへんはお気持ちです。

ライブラリが必要なとき

BIT, 2dBIT, UnionFindはshinchanがソラ書きします。

それ以外はDaylightが写経します。

実装

本当にめんどくさい実装はDaylightに投げます。

が、ほぼ各々やります。一緒に考察していた問題については、以下のようになってました。

  • Daylight+shinchan → 基本はDaylightがやる。Daylightが嫌って言ったらshinchanがやる。

  • shinchan+hint908 → 基本はshinchanがやる。

  • Daylight+hint908 → たぶんDaylightがやってたと思う。

これについては、考察に回す優先度が hint908 > shinchan > Daylight のようになっていたからです。

提出するときは、印刷も同時に行います。結果を待ってソワソワしてる時間が無駄なので。

めんどくさいとき

Daylightに投げます。問題読解、実装、めんどくさい考察、写経など様々です。

考察で困ったとき

hint908に投げます。

全体として

適宜コミュニケーションをとって問題の交換はわりと活発に行います。shinchanが知識として知ってること、hint908が考察力ですぐ解けること、Daylightだけが意外にも解けること、様々あります。

指示は基本shinchanが出します。チームメイトは「わかった」「やだ」みたいな返答をくれます。やだって言われたら自分でやりますが、チームメイトはわりと素直なのでちゃんとやってくれます。

とは言っても、hint908にはできるだけ指示を出さずに自由に考察させるのが良いと考えていました。一方、Daylightには指示を出せば出すほど良いです。特に彼が考察や実装で時間がかかっているときはshinchanが見るとすぐ解決できることが多いので、コミュニケーションを積極的にとり、少なくない確率で奪います。その後は「この問題読んで」がいつもの。この1,2年間でDaylightはしっかり社畜適性をしっかり高めていきました。申し訳ないとは思ってます、、。

hint908も考察で時間がかかっていたらいったん他の問題に移らせることが多々ありました。

振り返り

昨年ベトナムから帰ってきてから、「次は絶対WFに行くんだ！」という気持ちをみんな持っていました。それで、今年は早いうちに組んでチーム練をいっぱいしようという方針になりました。

レートを上から見ると、vwxyz, KowerKointは確定として、3人目をどうするかが問題です。候補としてはhint908, shinchan, そして既にアクティブではないPro_ktmrがいました。結果としてvwxyzセレクトで、kotamanegi_worldはvwxyz, KowerKoint, Pro_ktmrとなりました。

残り者をレート順に見るとhint908, shinchan, Daylightです。阪大で参加権限が残ってる暖色はこのちょうど6人です。hint908は既に私よりレートが上で、考察型、天才型なので、すぐに誘いました。Daylightは昨年度もチームを組み、英語力、問題読解力の点でとても活躍してくれました。KowerKointほどではなくとも実装力もあったりで、hint908と私にないものを全部補填してくれそうという印象があって誘いました。

kotamanegi_hint_kureyaの練習は上記の通りなのですが、kotamanegi_worldも毎週平日にチーム練をしていました。結果として、模擬国内、国内予選、Regionalと、私達2軍は1軍に負けることがありませんでした。これは、私たちの強みがなんなのか、を考えなおす機会となりました。同級生3人であることは割と大きそうです。特に私はDaylightを日々こき使い、hint908にも知識を吸収させました。

2人がラストイヤーなのもあって、3人がそれぞれの役目を果たそうとしたこと、同級生だからこそ、就活、TA、学会で忙しいとかの、それぞれの事情を理解してあげられたこと、それぞれが言い合えたことがチームとして良かったと感じています。

どうでもいいのですが、阪大上位3チームの構造は似ています。1人天才担当がいて、1人パワハラ担当がいて、1人実装担当がパワハラ被害を受けます笑

ICPC APAC自体は、完璧な戦略だったとしてもWF進出が可能かは怪しいのですが、明らかに私の戦略ミスだったと思っています。4完はもっと速くできたと思うし(特にAはもっと早く奪うべきだった)、Dももっと速く奪うべきだったし、Kも定数倍を信じて書いておくべきだった。これだけでWFボーダーの完数に届きます。

1年間ついてきてくれた2人には本当に感謝してて、それと同時に、ラストイヤーなのにWFに連れていってあげられなかったことが悔しい。

とても頼もしいチームでした。楽しかったです。来年度のチームでは必ずWF進出を果たします。

ICPC Asia Pacific Championship 2025 参加記

大阪大学のICPCチーム、kotamanegi_hint_kureya のshinchanです。シンガポールで開催されたICPC Asia Pacific Championship 2025に参加しました。

ICPC Asia Yokohama Regional 2024 参加記はこちら↓

shinchankosen.hatenadiary.jp

ICPC Asia Pacific Championship 2024 参加記はこちら↓

shinchankosen.hatenadiary.jp

チーム紹介

チームの振り返りと戦略はこちら↓

shinchankosen.hatenadiary.jp

3人ともM1で、早生まれの私(shinchan)以外の2人はラストイヤーです。

大きく分けて、普通に競プロをしたり指示を出すのがshinchan、天才担当がhint908、問題読解や写経やめんどくさい考察, 実装(まとめると、めんどくさいこと全般)やグラフ担当がDaylightです。実装はだいたい各々やります。これはそういうふうに決めていたものの、そういう傾向になっている程度のものです。UnionFind, BIT, 2dBITはshinchanがソラ書き、それ以外はDaylightが写経ってところは毎回その通りだったと思います。

Daylight

AtCoder青黄反復、だけど黄色に戻れる気配があまりしない、がんばってくれ。

競技プログラミングの競技プログラミング以外の部分を担当(？)

shinchan

AtCoder黄色。Codeforces赤。いろいろ担当。この記事を書いている。

hint908

AtCoder黄橙反復。天才担当。

Day 0 (移動日)

出発は昼からなので当日になってから荷造りを始めました。昨年の教訓を踏まえて、キャリーケースにどん兵衛を4つ入れました。また、海外チームに配る、おにぎりせんべいとカントリーマアムも入れました。スポンサーからもらえる物がとても多くなることが予想されていたため、キャリーケースは半分空いている状態で出発しました。

バス停でDaylightと合流し、途中の駅で他の阪大生とも合流しました。また、空港で徳山高専のチームとも合流しました。wi-fiを受け取り、午後7時頃？関空から出発しました。

飛行機は向かい風の影響で7時間半ほどのフライトとなってかなりしんどかったです。シンガポールに着いたのは午前2時半頃でした。入国はとても楽でした。Grabを使用してタクシーに乗ってホテルに向かいました。英語はDaylightに任せていたのですが、わりと聞き取りやすかったです。景色は正直ベトナムと変わらんなーって思ったり。気温は25～30℃で、大阪の真夏の37℃と比べると全然過ごしやすいです。

kotamanegiさんと同じ部屋に泊まりました。部屋に入れたのは午前4時頃で、晩御飯を食べてなかった私はどん兵衛を食べることに。湯沸かし器を壊してしまい、早速kotamanegiさんやホテルの方に迷惑をかけました(スプーンで直されました)。

Day 1 (開会式, リハーサル)

朝食

およそ2時間半の睡眠を経て、朝7時頃に起きて朝食に行きました。日本の知り合いや、わかりやすいリユナさんを発見しました。朝食はベトナムと変わらなかった。

↑ fish ballと書いてあったものが本当に合わなくて、「どん兵衛足りるかなぁ」となった。しかし、翌日以降朝食はパン, ゆで卵, ナゲット, コーヒーだけにしておけばわりと耐えました。ランチ, ディナーもイタリアンの肉とデザートだけを食べて1人だけスイパラをしていました。

開会式, ランチ

シンガポールの方の英語はベトナムよりも聞き取りやすくて、開会式も去年に比べると楽しむことが出来ました。スポンサーセッションがメインでしたが、普通にすげーって聞いてました。獅子舞？みたいなやつも普通に見ごたえあった。

休憩時間中には、discordの鯖で仲良くしていたi_am_noobやwayneyam達が話しかけにきてくれました。

ランチ時には、某有名なリユナさんや一緒にいたNUSのインドネシア人の方、台湾の方、横浜にも来ていたタイのttamxと交流しました。おにぎりせんべい、出番だ。

スポンサーブースにオセロがあったので、なにわづと一局(？)やりました。その後観戦時に隣にいたベトナムの方とも会話しました。

リハーサル

コンテスト環境はかなり過酷で、ノートpcのディスプレイ, キーボードを使用するというもので、机も短かったです。さらに左のチームが壁をどんどん押してきてうちの土地が狭くなっていきました。なんとか押し返して均衡状態を保てました。これも競技プログラミングです。

向かいのチームとの壁も物足りなくて普通に見えて気まずいです。向かいのチームが来たときにNice to meet youと挨拶すると無視されました。悲しい。

A, CはやるだけなのでDaylightに通してもらい。Dは昨年のK問題でWMで解けることを覚えていたのでとりあえずWMをDaylightに書いてもらいました。以下は実際に持ち込んだライブラリです(notebook.pdfです)。

github.com

DaylightがWM写経時、ライブラリがなぜか一部消えていることに気づきました。後から確認すると、リポジトリのコード自体は完全な状態で、pdf化するときになぜか関数1つ分が消えることがあるというバグでした。消えていた部分はDaylightが自力でなんとかできるレベルだったのですが、reserveをresizeと書き間違えていることに気づけず、それ以外の部分は合ってるはずですがD問題のACを得られませんでした。

ttamxにどうだった？と聞かれ、「our library is broken...」と答えました。

追記 tatyam先生が対策してくださりました。ありがとうございます。

github.com

ディナー, その後

ディナーでは「東大, 京大, 東工大はWF進出として、日本4位がどこになるだろうね～」という会話をしました。

ディナー後は近くにマーライオンがあったのでみんなで散歩することに。

マーライオンは思ってたよりも大きかったです。

さて、ホテル帰還後、ライブラリの一部欠損バグが他の箇所で起こっていないか気になったので、確かめました。リハーサル中に見つかったWM関数欠損と、さらに遅延セグ木が1行欠損してることがわかりました。逆に2箇所だけで助かりました。

Day 2 (コンテスト当日, 表彰)

本番前

朝食は軽めに食べたあと、いつもと同じ調子で向かうため、どん兵衛を食べました。ホテルのロビー集合FAでした。形から入ります。

本番

DaylightはA, shinchanがBから, hint908が後ろから読む作戦です。

Daylightが「Aはちょっと重いけどできる」と言ったので実装を始めます。私はBが読みたくない見た目をしていたのでCを読んで、15分ほど考察していましたが、わかりません。

Daylightが苦しんでいたので20分おきくらいに声をかけますが、大丈夫と言われていました。後ろから読んでいたhint908がLをすぐ書けると言ったので実装をして、ACしました。

L: hint908 0:27

その後、私は順位表を見て解かれていたGを読んで、誤読解法を生やしてWAを返されるなどしました。

hint908がJで苦しんでいた(？)ので交換すると、「N<=500？区間DPやるだけじゃん」と私が言い、hint908も「あっ」となりました。実装は私がやりました。ACです。

J: shinchan 1:04

hint908がG問題の私の誤読に気づきました。一応、英語が一番できるDaylightにその部分を読んでもらいます。「1と1で1。0と0で1になります。」「いや、1と1で1になってそれ以外0だ。」となって私の誤読が確定したものの、誤読が発生しやすい文章であることもわかりました。その後はhint908が実装してくれました。ACです。

G: hint908 1:33

さて、苦しんで80分たっているDaylightのAを奪って問題と考察方針を聞きます。Daylightは固定するものが違った気がする。2の場所を固定して1の方向と4の方向について4通りに場合分けしてそれぞれ詰めれば実装は楽そう。20分ですべてをしてAC。

A: shinchan 1:41

その後は、D, H, I, Kを3人で考えていました。Kはどうせmonotoneだと思って O(N {(\log N)}^2) を生やしますが、さすがに N <= 500000は無理だーとなります。

その後のメインは、私がHを考え、hint908がDを考え、DaylightがIを考えていましたが、これもミスだったように思います。Dはhint908に「セグ木だと思う」と伝えられ、実際に乗せ方もすぐに考察できましたが、すでに残り1時間でそこからさらに3問ACする必要がありました。薄々諦めたような動きですが、Dの実装は可能だけど放置し、3人でHを考えました。通したい見た目をしていたからです。

私の考察として、multiとtypeを同時に聞く二分探索方針や、黄金分割探索方針、multiだけで攻める黄金分割探索方針などを思いつきましたが、どれも外れです。約数列挙をして矛盾を省いて大小関係だけがわかればいいなーっとなって一意に定まってくれたらいいなーっと考えて実験しますが、外れでした。

最初に2回multiをしてあとは二分探索で攻めるような方針を思いつきましたが、これもRRRRRLRLLLLLLLのようなケースでまずいことがわかりました(早稲田や東北、チュラロンコン大も同じ考察方針に沼ってしまって解けなかったそうです)。

終了直前にhint908が「そうなると最初からtypeを聞く必要があるんだな…」と言いました。外れ方針でずっと考察をしてしまって残り時間が数分という状況になってしまい、4完で完全な敗北を味わうことになりました。

結果

47位でした。

Yes/No時、日本や韓国チームが予想よりも低い順位だなーって思っていたのですが、上位勢はちゃんと勝っていてすごかったです。Screenwalkersが1位に上がったときの会場の沸き具合。

感想戦

Dは自力で通せるとして、Hは「RLってなってる場所を探せばあとは2手でできる。全体のRの数が答えになる。」と教えてもらってため息がでました。

まぁ、あのタイミングからだと6完してもWFはたぶん行けないから、ええか…となっていました。悔しさすら出ない。

が、twitterを見るとKがlog 2乗で通ったというツイートがちらほらあります。なんだ、mirrorの話か、本番で通るわけ…。

Yutoさん「通りました」

一気に悔しさが出てきました。

後日3問ともACしました。D, Kは自力。

Day 3 (Excursion)

USS(Universal Studio Singapore)に行きました。最初は20人ほどで行動して、徐々に分裂しました。ちょうどいいアトラクションが多くて助かりました。明らかにやばそうな見た目をしているアトラクションを避ければとても楽しかったです。transformerやミニオンが特に楽しかったです。途中、Daylightとkotamanegiさんがカジノに行くということで分裂するとき、目の前にあったアトラクションについてDaylightが「あれ(Cylonに比べて)緩いらしいよ」と発言し、「緩いのか、じゃあ乗ろうかな」と、まんまと乗ってしまい、ちゃんと落ちるやつでした。Daylight許さん。でも、(去年kotamanegi_mijingiriも含めて)この2年間Daylightに実装や写経、問題読解を投げた回数は100回を超えてそうだから受け入れるか…(戦略ではあったが)。と、自分の行いを反省しながら叫びました。

USSを出たあと、中国料理屋台が並ぶNewton Food Centreに行って夕食後、ホテル、空港に向かいました。

Day 4 (帰国)

午前2時くらいの出発で、わりとちゃんと寝られました。わりと揺れて着陸前後が大会一番のワクワクでした。30℃の服装で飛行機を降りると外は4℃で雨が降っていました。

入国、解散。

交流

今回は国際交流をがんばりました。おにぎりせんべいとカントリーマアムを持っていって会話したチームに配りました。

台湾、韓国、ベトナム、インドネシア、シンガポール、タイのチームと会話しておにぎりせんべいを配ることが出来ました。

チュラロンコン大のttamxと英語でしゃべる時間が長く、逆にリユナさんとしゃべるとき日本語がでてこなくなったりして、リユナさんに「英語使わなくて大丈夫ですよ」と言われてしまった。

そういえば、APAC直前にシンガポールで別のオンサイトがあって、日本から参加してるチームはいないと思いますが、チュラロンコン大チームは参加していたらしいです。宿泊費がやべぇって言ってました。

シンガポールは全体的に、英語で会話するものの、街中の案内には中国語もセットで書かれています。日本人にとってとてもわかりやすいと感じました。

リスニング面は、去年に比べるととても聞き取りやすい英語の方が多いです。シンガポールにはいろんな国から人が集まってきているため、訛りはきつくならないのだと思いました。ベトナム出身らしき人達は去年と同じくほとんど単語レベルで聞き取れませんでしたが…。

感想

大会全体としてめっちゃ楽しかったです。去年のようにスケジュール通りにならないとかがなく、交流も盛んに行うことができて良かったです。

食事は去年と違って合うものが多くて助かりました。USSも楽しかったです。

コンテスト環境はうーんって感じでしたが本番中は集中していて結果的にあまり気にしてませんでした。

コンテスト自体は後悔も残らないほど大敗し、「今回のセットで勝てるシチュがまったく思い浮かばないなぁ」と思っていたのですが、自分がTLEだと考えていたKの解法が通るなど、戦略がよっぽどうまくいけばわんちゃんあったのか…となってしまいました。

前述の通り、日本4位に入る大学として、徳山高専・慶應・阪大・東北大・筑波という5つの候補がありましたが、徳山高専はおそらくWF進出、それ以外は予想よりも悪い順位になったと思います。この結果を見ると、自分の順位も納得の結果だなぁと思いました。

全国的に、私の学年は大学に入ってから競プロを始めて強くなる人がどんどん増えた学年だったと思います。みんなは今年度でICPC引退。チームメイト2人もjagにメール送ったらしいです。 自分もチームメイトも、他のチームもみんながんばった1年で、とても有意義でした。できれば、チームメイト2人をWFに連れていってあげたかったな…という心残りも。

自分個人としても、阪大初の2回WF進出を狙っていたので達成不可能になって少し残念なのですが、2年連続ICPC APAC進出、ICPC国内予選阪大史上最高順位(たぶん)といった結果を残すことができたのは、チーム3人で頑張った成果として、誇れることだと思っています。

さいごに

来年度、4月からの話をします。

阪大の英語名称が、Osaka UniversityからThe University of Osakaに変更になりました。来年はUOsakaとしてWFの歴史に大学名を刻みます。

早速、来年度のチーム鯖を作りました。メンバーは以下の通りです。

Nachia

執筆時点で日本1位のCodeforces Ratingを保有しています。知識、考察、実装、英語問題文読解など、すべてにおいて他2人を上回っています。

高専生特有の事情やNachia君自体が大阪公大高専であること(またその他の事情)から、阪大に五分五分で来てくれるだろうとは個人的に企んでいました(残り半分は東工大)。

KowerKoint

今年度はkotamanegi_world, 昨年度はkotamanegi_mijingiriで私と同じチームでした。レートは2200前後で、ABC, ARCの早解きが非常に得意です。実装速度やICPCにおけるライブラリ写経が非常に上手です。ただ、実装精度(バグらせ)に問題があり、そこをゆっくり改善していってほしいところです。

shinchan

わたしです。

Nachia君がいるので、まずは確実にWFに進出すること、その中でRegional優勝やAPAC優勝を狙うこと、そしてWFで1つでも高い順位を取ることを目標にします。まだチーム練をしてないのでこれから試してみようと思っているのですが、戦略の候補は大きく分けて2つです。1つ目は一般的な並列考察。2つ目はいわゆる、りんごさんチーム戦略です。

japlj.hatenablog.com

この1年間で私は考察力実装力ともに大きく向上させることができました。来年度はとりあえず、各国のICPC過去問やcodeforces、ucupをメインにして頑張ります。




kotamanegi_hint_kureya 解散、2人とも1年間ありがとう。