kotamanegiの取り扱い説明書

のんびり趣味の事を書いてます。

The 2024 ICPC Asia Pacific Championship 参加記

2024年2月29-3月4日に開催されたThe 2024 ICPC Asia Pacific Championshipにチームkotamanegi_marunageで参加し、6完大学別順位14位・全体19位でした。 メンバーはvwxyzさん・kuhakuさん・kotamanegiで、コーチがolpheさんでした。

前準備

航空券の予約メール

olpheさんが体調不良で大会に参加できなくなり、僕がkotamanegi_marunageとkotamanegi_mijingiriの6人分の航空券や宿泊の手配などを行いました。 とりまとめは大変でしたが、非常に良い経験をさせていただきました。

Day 1

初日は、日本からベトナムまで飛行機で移動しました。

行きの飛行機

関空でkotamanegi_marunageとkotamanegi_mijingiriで6人集まり、さらに京大勢の6人とも合流して12人で飛行機に乗りました。

サントリーブランドのTEA+という飲み物。日本のウーロン茶とは違って、とても甘いです。

到着先のベトナムのノイバイ空港では、さっそく海外の甘いウーロン茶の洗礼を浴びました。 サントリーブランドなので安心して飲もうとしたら、とても甘くてびっくりしましたが予想外に美味しかったです。

(左)ホテル (右)ホテルに備え付けのパナソニック製ドライヤー

空港からはICPC運営が用意してくださったバスに乗り込み、今回の宿泊先であるCầu Giấy Hotelに向かいました。 ホテルはとても綺麗で、内装も日本のビジネスホテル並みだったので快適に過ごすことができました。

Day 2

2日目は、開会式やPracticeがありました。

(左)ICPCのチーム写真 (右)開会式会場

バスに乗り込んで着いた開会式会場では、ICPCのチーム写真撮影をしたりベトナムの著名人の話を聞いたりしていました。

(左)コンテスト会場 (右)昼食

開会式の後、コンテスト会場に移動して昼食を摂り、Practiceに参加しました。 昼食はごはん+チキン+汁物という日本でもおなじみの構成で、大変美味しかったです。 Practiceでは会場を飛ぶ謎のドローンや外のクラクションに悩まされながらも無事に全完相当の成績を取ることが出来ました。

Day 3

バスに乗り会場に着き、コンテスト本番を迎えました。

コンテスト本番

滑り出しの戦略は、

  • kotamanegi: PCのセットアップ
  • vwxyzとkuhaku: 問題文を読む

でした。

以下は記憶から掘り起こしてきた時系列情報です。

  • -0:30: コンテスト前にライブラリの一部没収を告げられる。悲しい。
  • 0:00 ジャッジシステムへのログインに失敗する。苦戦していたところ、アナウンスで不具合の連絡があった。
  • 0:10 ジャッジシステムが復旧し、ログインに成功する。
  • 0:30 HをAC。いつの間にか通っていた。Jのコーディングを始める。
  • 0:49 JをAC。ペナルティを1個出したが、順当にうまく通すことができた。
  • 1:21 CをAC。WAが出て苦戦しているのを眺めていたら通っていた。僕がE、他の2人でGの実装を始める。
  • 1:59 GをAC。プレッシャーを感じながらEを書く。
  • 2:06 EをAC。とりあえず一安心し、K問題の実装方法を考えていく。
  • 3:07 FをAC。Kを書き始める。
  • 4:20 Kが書き終わり、提出を始める。TLEではなかったが、WAとなり困り果てる。
  • 5:00 Kが間に合わず、コンテスト終了。

コンテスト後

6完はできたものの、Kが通らなくて悲しい気持ちになっていました。 後日解きなおしをしたところ、答えの保持にint型を使うとオーバーフローしてしまうというのが真相らしいです。 バグの原因がわかって納得の一方、悲しい気持ちが残ります😢


(左)閉会式会場 (右)閉会式のステージ

コンテスト後は市内観光を少し楽しんだ後、閉会式に向かいました。

Day 4

(左)乗船 (右)タコの着ぐるみ

朝5:30に出発するバスでハロン湾に向かい、クルーズ船に乗り込みました。

(左)景観 (右)昼食

景観も食事も良く、満足度が高いクルーズでした。

(左)ティートップ島 (右)頂上の展望台

1つ目のアクティビティでは、ティートップ島の頂上まで400段程度の階段を上るというアクティビティを楽しみました。

スンソット鍾乳洞
2つ目のアクティビティでは、スンソット鍾乳洞の景観を楽しみました。

帰路のベトジェット

往復ともにベトジェットエアというLCCを使ったのですが、遅延することなく定刻通りに運航してくれて良かったです。


振り返り

僕は世間から競技プログラミングの大会では弱くはないけど強くもないという認識をされていると思います。(実際そうだと思います)中学生の頃に競技プログラミングを始めてからというもの、あと少しで国際大会に手が届くという寸前まではいけましたが肝心なところで取りこぼすというもどかしい経験が続いていました。なので今回ベトナムのChampionshipに参加できるという連絡をいただき、初の国際大会に参加できたのは僕自身としても大変嬉しかったです。

これはもう何度も書いたと思いますが、大手前高校時代に競プロのコンテストでチームを組む際も人集めにとても苦労したので、大学へ入学したときにも僕とICPCに出場してくれるような人が出てくるのか心配するほどでした。 高校を卒業する頃は大手前高校はそこそこ競プロをしている人材が増えていたので、その努力がリセットされてしまったような少し切ない気分になっていたと思います。 しかし、気心知れた仲間内でチームを組めたにも関わらず、折角阪大にこたまねぎさんが入学してくれたんだからと先輩に引っ張り上げてもらい、B1の時から予選突破を目指すチームに編成される事になりました。 自主的に勉強会を開いたりと活動も盛んになり、阪大はもしかしたら強くなれるんじゃないかという希望や期待に心が温かくなりました。 同時にもっと強くなって必ず予選を突破しなければいけないというプレッシャーとの闘いも始まりました。 後は前回も書いた通り、何年も1,2チームしか国内予選を通過できなかった阪大が、国内で3チーム、海外の国際大会に2チーム送り出せるほどまで成長を遂げ、今ひそかにWFの繰り上がりを渇望するところまできました。

また、在学中に力を入れた事の1つに阪大の運営の厳しい審査を通過し、阪大公認団体として阪大競技プログラミング部「RAINBOU」を立ち上げたことがあります。 僕としても、ICPCなどの規模の大きなコンテストでのノウハウを知見として積み上げる場としてRAINBOUが有効活用されているのを現在進行形で見てきました。 理想として、競プロerにとって安定した居場所をつくり、今まで蓄積してきた情報を惜しみなく交換できる場を作るということを目指してきました。 申請中、進捗の悪さで途中挫折しかかった時もありましたが、踏ん張って公認を得られてよかったです。

公認団体が活用された例 (出典: https://kowerkoint.hatenablog.com/entry/2024/01/09/220819 )
時代の流れがあるので強くは言えないのですが、これからの阪大競プロ部を支える柱として後輩たちにも頑張ってほしいなと願っています。

最後になりますが、もし僕たちのチームが繰り上げでWFの出場権を得られるような奇跡が起こった場合、その時こそ今回体調不良で参加できなかったコーチのolpheさんと共に、4人揃ったkotamanegi_marunageとして一緒に参加してきたいと思います。WFの出場権が得られた場合、僕が阪大生として戦う最後の場になります。もし出場できる機会があれば皆様応援よろしくお願いいたします。



阪大とIISFの双方から合わせて6人分の旅費などの支援を受けました。 大阪大学最高!

量子競プロ学習サービスQookbookについて

この記事は 競プロ Advent Calendar 2023 の 13 日目の記事として書かれました。

未踏ターゲット事業で、競プロ風に量子コンピュータの勉強ができるサービスQookbookを開発しています。

目次

自己紹介

大阪大学大学院情報科学研究科 コンピュータサイエンス専攻M2のkotamanegi (@small_onions) です。 競技プログラミングでは、1か月弱ほど前に国際大学対抗プログラミングコンテスト (ICPC) アジア地区横浜大会にて競プロ人生ではじめて銅メダルをいただきました。

その他にも、伊野研究室で量子回路シミュレータの高速化をしたり、株式会社ALGO ARTISで最適化を学んだりしています。

さて、本題のQookbookの話に移ります。

何ができるの?

物理学の事前知識なしで、競技プログラミングのように問題を解きながら量子情報の知識を身に付けることができます。 左側には問題文やテキストが表示されるスペースが、右側にはソースコードを書き込むためのスペースがあります。 ソースコードを書いたらweb上でそのまま実行しながらデバッグができ、うまく動作しそうであれば提出して採点を受けることができます。

舞台裏になる問題作成ツールなどにも力を入れており、競技プログラミングにおける「インタラクティブ問題」が簡単に書ける仕組みを作成しています。 システム面の補強と並行して、将来的に次のようなコンテンツを追加していきたいと思っています。

なぜ作ろうとしたのか?

量子コンピュータの世界には、競プロerや情報系の方が好きそうな話題がゴロゴロと転がっているのに、別分野のように見えて敷居が高くなかなか参入できないからです。 僕が量子コンピュータの世界に飛び込んだきっかけは、藤井先生のつぶやきでした。

この後に藤井先生の下で、量子回路シミュレータ Qulacs の開発を担当するなど様々な経験をさせていただきました。 特に興味を持ったのはノイズなどで生じた誤りを訂正する量子誤り訂正や、量子プログラムをより単純な制御命令列に変換する量子コンパイラなどの分野でした。 量子誤り訂正については、表面符号と呼ばれる誤り訂正符号について 焼きなまし法で誤り訂正を行うという研究 や、 フェニック木 (BIT) を用いて誤り訂正を高速化するという研究 など、どこかで聞き覚えがあるアルゴリズムを使った研究がされています。

https://qiita.com/SamN/items/c2b6b4c28bae922bc634 より引用。表面符号では青色マスを2つペアにして繋ぐことで誤り訂正を行っています。繋ぎ方によって正しく誤りを訂正できる確率が変わります。

量子コンパイラについては、できるだけ計算資源を有効活用して短時間で計算が終わるように、様々な最適化手法を使ってスケジューリング問題を解くという研究がなされています。 有名な例として、量子回路を格子手術の命令列に落とし込むために、タイルを変形するパズル問題を解くという研究があります。

A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery (https://arxiv.org/abs/1808.02892)のFig.11より引用。 ヒューリスティックコンテストで出てきそうな図です。

このような研究を面白いと思いながら勉強していく中で痛感したのは、学習時点では地に足が付かないような内容が多く、内容の理解がとても難しいということです。 当時から初学者向けの教材は Quantum Native Dojo などネットの教材も含めて沢山ありましたが、難しい部分に行くにつれ自分がどこまで理解しているのかわからなくなっていきました。 理解を深めるために演習問題などを解くわけですが、実はちゃんと理解していないのにスルーしてそのまま進み、後でつまづきに気が付くといったことも頻繁にありました。

それに対して競技プログラミングは、理論の理解度が自己判定しやすいため確実に一歩ずつ進めるという特徴があります。 学びたいトピックに対して大量の演習問題があり、問題を解くプログラムを提出するとその場で採点されて採点結果が返ってきます。 演習問題を解くことまでは書籍でもできるのですが、その後の採点プロセスまでもを自動化することで、人力では不可能な刻み幅で理解度を判定することができています。

この競技プログラミングの特徴を、量子プログラミングの学習にも持ち込めないかと考えてQookbookの開発を始めました。 量子プログラミングもまた一つのプログラミングの系統で、アルゴリズムpythonプログラムなどとして記述されるので、いろいろと頑張れば競技プログラミングの枠組みに落とし込めそうだと考えました。 技術についても、高校生の頃に作った kotamanegi online judge のノウハウや、競技プログラミングなどで培った狂気の実装力を活用すれば1年弱で開発できるだろうと見積もり、未踏ターゲットに応募したところありがたいことに採択されて今に至ります。

最後に

競技プログラミングはコンテストが醍醐味の一つなので、もちろんコンテストをやります! 1/14(日)の13:00-17:00に、スコアを競う短期マラソン形式のコンテストを開催する予定です。

ささやかですが、副賞としてAmazonギフト券も用意しています。

  • 1位: 1万円
  • 2位: 5千円
  • 3位: 3千円
  • 4位〜10位: 1千円

コンテスト中も外部資料の参照はOKなので、もし予定が合えば気軽に参加していただけると嬉しいです。

謝辞

本サービスは、未踏ターゲット事業の支援を受けて開発しています。 未踏ターゲット事業では、担当PMの徳永PM様・鈴木TA様をはじめとして様々な方に助言をいただきました。 助言をいただけなければ、ここまで開発を進めることはできなかったように思います。 ここに深く感謝の意を表します。

ICPC 2023 Yokohama Regional 参加記

2023年11月25-26日に開催されたICPC 2023 Yokohama Regionalにチームkotamanegi_marunageで参加し、10完大学別順位3位・全体4位でした。 メンバーはvwxyzさん・kuhakuさん・kotamanegiで、コーチがolpheさんでした。

1日目 — リハーサル

僕は13時45分ごろに会場に着いて食事を取ったりしていました。

無事(?) 3人+1人で集合できて、受付時間内に会場に入ることができました。 リハーサルについて、Dをバグらせながらも、なんとか無事全問題をACすることができました。 リハーサル後は筑波大のチームGoodBye2023と一緒にサイゼリヤで食事を取っていました。

2日目 — コンテスト本番

チームメンバー(僕含む)は朝が弱いのでギリギリまで会場入りできませんでした。 記憶では9時ちょうど着ぐらいだったと思います。

コンテスト

戦略は、

  • kotamanegi: PCのセットアップとA問題のFA狙い
  • vwxyz: Bがインタラクティブ以外なら担当、そうでなければC問題以降を見る
  • kuhaku: Bがインタラクティブなら担当、そうでなければC問題以降を見る

でした。 結果としてはCを除く全問題ACの10完で、ある程度うまく戦略がはまったのではないかなと思います。

以下は記憶から掘り起こしてきた時系列情報です。

  • 0:00 問題とログイン用パスワードの封筒をうまく破ることに失敗。10秒程度のロス。
  • 0:08 FAは逃したものの、A問題を順当にAC。 vwxyzさんがB問題を書き始める。
  • 0:25 Bのサンプルが合わず、僕が読んですぐ解法が思い浮かんだD問題を実装しはじめる。
  • 0:40 DをAC。kuhakuさんにFを実装してもらい、その間に僕はB問題を考えていた。
  • 0:50 FをAC。僕がB問題を実装することに。
  • 0:58 BをAC。この時に10位前後で、阪大代表としてのプレッシャーが襲ってくる。とりあえず僕がK問題を、他の2人でE問題を解くことに。
  • 1:24 EをAC。僕がK問題を実装して、その間に2人でGとH問題の解法を考えてもらう。
  • 2:16 苦戦しながらKをAC。僕がG問題を読んだら5分ぐらいで解法が思い浮かび、そのまま実装。
  • 2:46 GをAC。H問題がフローということでライブラリ写経したり、解法のバグ直しなどを始める。
  • 3:52 HをAC。上位と比べて1完差があり、厳しい気持ちに。IとJを読み始める。
  • 4:10前後 J問題の解法(解説スライドのAC2)を思いつく。実行時間に関する証明ができていなかったのでvwxyzさんに止められたが、PCが空いているのでとりあえず実装することに。
  • 4:32 JをAC。最後にIに着手して、凸包の天啓が降る。
  • 4:50前後 サンプルが合うが、提出してみるとREで落ちてしまう。細かいところを変えて提出を繰り返す。
  • 4:58 IをAC。ラストスパートということで半分運任せの提出を繰り返しており、ふと採点結果欄を見たらACしていたので喜びを分かち合うよりも通っていた事に呆然となっていた。

5年の振り返り

B1から阪大の選手として5年間出場し続け、とうとう今年最後の年になりました。 最近は阪大内で活発に活動する競プロerが増えてきたのもあり、戦い続けるか悩んでいました。 本業の研究は勿論ですが6月から未踏ターゲットのPJが始動し、さらにAA社のアルバイトも入ったため練習時間を確保する事が困難になるのは明らかでした。 更にコーチを誰にお願いするか等の悩みもあり、「競プロにがっつり向き合う時間もないのだし、かつての先輩方のように後続の支援に回る事が自分の使命になるんだろうな」と思いつつ、選手として燃え尽きたいという気持ちとの板挟みになっていました。

5年間でのYokohama Regionalでの成績は初年度から21位→4位→4位→8位となっていました。そして今回の凍結前の順位は8位だったと思います。 凍結後の1時間でIとJの両方を通すことができたのは、5年間煮詰めた執念によるものだったのかもしれません。

結局全体での順位はまた4位でしたが、大学別では3位だったので初めて表彰台にのぼりメダルを受け取るという経験ができました。 競技終了2分前のブザービートACがなければあり得なかった展開だっただけにその現実を頭が受け入れていなくて挙動不審になっていたし、今となっては非常に恥ずかしいです。 まさか阪大が3位で表彰を受ける未来がくるとは想像できなかったもので…。

もう一つのハイライトとして、今年ついに阪大から3チームYokohama Regionalへの進出を決めることができました。

阪大からの国内予選の通過チーム数は5年間で1チーム→1チーム→2チーム→2チームと、通過チーム数が伸びていき今年ついに3チーム輩出することができました。 これはひとえに選手みなさんの努力と、阪大競プロ部RAINBOUに尽力いただいた方々・ICPCという場を設けてくださった方々・陰で支えてくださった皆様によるものだと思います。交流でもたくさんの方とお話しできて楽しかったです。本当にありがとうございました。





↑物理好きさんごめんね~🤣



宣伝

未踏ターゲットというIPA事業の支援を受けて、競プロライクに楽しく量子コンピュータの利用方法を学べるサービスを開発しています。 競プロ Advent Calendar 2023 - Adventar にも12月13日に寄稿する予定なのでよろしくお願いします。

ICPC2023 国内予選 参加記

2023年7月8日に開催されたICPC2023 国内予選にチームkotamanegi_marunageで参加し、5完14位でした。 メンバーはvwxyzさん・kuhakuさん・kotamanegiで、コーチがolpheさんでした。

コンテスト前

僕は12時に会場入りして、会場設営などを少しお手伝いしていました。 そのあとはリハーサルやプリンタの出力確認、初動の計画をしていました。

コンテスト中

今年の初動は問題文を印刷してから、僕がA問題を早解きするという計画でした。 初動はうまく行き、0:03:32でA問題を通すことができました。 A問題を通した直後、B問題に目を通したところ簡単に実装できそうだったので実装し、少しバグを出しながらも0:22:39にB問題を通しました。

その後は、D問題を僕とvwxyzさんが、C問題をkuhakuさんが解くことになりました。 D問題は解が7以下であることに気が付き、計算量が怖かったもののとりあえず総当たりコードを書くことになりました。 C問題とD問題の双方ともにバグを出してPCを取り合いながらも実装を進め、0:53:06にC問題が、0:58:46にD問題が通り4完でそこそこ良い順位に収まりました。

E問題は時間計算量 O(n^2 log^2 n) 程度のセグ木を用いた解法が思いついたのでそれを実装しつつ、裏でvwxyzさんとkuhakuさんに簡単な解法を考えてもらうことにしました。 実装量が多くバグに手こずっていると、kuhakuさんが簡単な解法を思いついて実装を交代することになりました。 結局バグが取れずに両方ともペナを出し、少し書き直した僕の解法で2:25:28にE問題のACを取ることができました。 この時点で13位程度になり、安心して順位表を眺めていました。 G問題を考察していたんですが、最小費用流に帰着できそうだね、と言ってたらそのまま終了しました。

コンテスト後

阪大から3チーム予選(ほぼ)通過が出たということで、達成感でいっぱいになりました。 コンテスト後半の成績的に阪大から3チーム予選通過しそうだな、という直感こそありましたが、ボーダーをきちんと覚えておらず不安でした。 コンテスト終了直後に順位表のボーダーを再確認し、3チームの予選通過が確定したことを確認できました。

3チーム通過しましたが、僕のチームは結構反省点が多い結果に終わりました。 E問題までの実装スピードが遅かったため、上位の決め手になるFとG問題に時間を割くことが難しく辛い気持ちになっていました。 実装ゲーが出たときに貢献できるよう、アジア地区予選でも頑張ります。

ICPC 2022 アジア地区予選 参加記

2022年12月27~28日に開催されたICPC 2022 Asia Yokohama RegionalにチームTLE_WARLDで参加しました。 メンバーはWA_TLEさん・vwxyzさん・kotamanegi、コーチはBadlyluckyさんです。 最初に結果を書くと、ABDEFGの6完で8位でした。

前日

初日のリハーサルやチーム紹介が予想以上に早く終わり、食事予約などを早めの時間に変更するなどで大忙しでした。 18:30から梅蘭金閣で飲茶セットを食べ、20:00には解散・各自就寝という理想的なスケジュールで動くことができました。 bairan-tougen.jp

コンテスト当日

早く寝たのが功を奏したのか、寝坊はしませんでした。 寝坊に備えて、部屋の鍵が共有できるホテルを選んでいたのですが、共有鍵は使われることなく終わりました。本当に良かったです。

コンテスト直前期

6:30に起床し、7:30ごろから朝食をとりました。 朝食会場には競プロerらしき方々を時々お見受けしました。宣伝の成果ですね(?)

a8pfactory.hatenablog.com

8:30ごろにホテル前で集合し、会場に向かいました。 名前が非常に似ている方とお話をしていたら、いつの間にか競プロerの列が後ろに出来上がっていてびっくりでした。

コンテスト中

コンテスト開始後すぐに、CLionの設定とA問題の確認をしました。 A問題は単純なスケジューリング問題だったので、すんなりとACできました。 実際にスケジュールを出力する必要があったので、ちょっとだけ面倒でした。

vwxyzさんにB問題を任せて、僕はしばらく他の問題を見ることにしました。 WA_TLEさんに問題概要を伝えながら取り組むべき問題を精査していました。

  • C: 難しそう
  • D: おそらく簡単枠、ただの実装
  • E: WA_TLEさんが解けたと主張していたので見なかった
  • F: 幾何、スルー
  • G: 木の制約が気になるが、簡単枠に見えた
  • H: 数学ゲー、スルー
  • I: 組合せ論、ちょっと考えたけど難しい
  • J: 幾何、スルー
  • K: スケジューリング問題、頑張れば解けなくもない実装枠

Bが通ったあと、WA_TLEさんからG問題の解法を教えてもらったので実装しました。 実はこれは嘘解法で、いったんWA_TLEさんにE問題を実装してもらった後、vwxyzさんが正しい解法に書き換えて無事ACできました。

マシンが空いている時間帯を見計らって、D問題を実装しACしました。 最初のsourceパターンを回転する代わりに、目標のtargetパターンを90度回転すればsourceパターンの座標系を変形することなく実装できました。 工夫をすれば実装が簡単にできるという面白い問題でした。

その後は、F問題などとK問題を反復横跳びしていたらコンテストがいつの間にか終了していました。 K問題を通せていれば4位ということで、悲しみでいっぱいです。

コンテスト後

カツサンドやドーナツを食べながら、スポンサーセッションを見学しました。 LegalForce社がLegalOn Technologies社に社名変更していたり、いい生活社のロゴが変わっていたりと、3年前のICPC2019からの時の流れを感じて懐かしい気持ちになりました。

解説を聞いた後は、交流を楽しんでいました。 企業の方からICPC初参加の方まで、様々なバックグラウンドの方がいらっしゃり大変楽しめました。

感想

久しぶりのICPCオンサイトということもあり、少し懐かしさを感じる場面が多かったです。 僕が3年前にオンサイトに初出場した後は、コロナ禍の影響でオンライン開催が続いていました。 今回こうしてオンサイトとして現地で集まれたのは運営とスポンサーの方のおかげだと思っています。 本当にありがとうございました。

天下一 Game Battle Contest 2021 Autumn 参加記

概要

天下一 Game Battle Contest 2021 Autumnにkotamanegiとして参加し、優勝しました。 前回の天下一 Game Battle Contest 2021 Springと合わせて2連覇を達成しました。 f:id:kotamanegi:20210923231731p:plain

ソースコードgithub.com にあります。

ラクティスセッション

時間がなく参加出来なかったのでぶっつけ本番になりちょっと不安でした。

コンテスト前半戦

まず問題文などを読みに行くと、今回はproduction環境とstaging環境が用意されておりstaging環境でテストが出来るということが判明しました。 このためproduction環境用とstaging環境用にプログラムをそれぞれ別々のコマンドで起動できるようサンプルやMakefileを改造しました。

その後はとりあえずサンプルプログラムを稼働させてスコアが出ることを確認しました。 次に各ゲームエージェントから最も近い資源を選んで向かうようにするとスコアが少し上がりましたが、この頃physics0523(@butsurizuki)さんがスコアをメキメキと上げていて周りが3桁台の時にすでに2000点に乗っており内心かなり焦りました。

突破口を探るべく実験していたところ、資源が出現する前に出待ちをするとスコアが大きく向上し1位に躍り出ました。

コンテスト後半戦

1位にはなったものの後ろから追われていたので、人が集まってきた段階で資源が消滅するより前に次の資源に移動するという処理を追加すると更にスコアが上がりました。 開始2.5時間もすると改善点が見つからなくなり、どの資源を優先的に取るかなどの細かい部分のパラメータチューニングをしていたらコンテストが終わりました。

感想

1位になってからは早く終わってくれと祈りながらビジュアライザを眺めづつポチポチ手動でパラメータを変えていました。 後続の追い上げが厳しかったので他人の失敗を喜ぶ悪い子になっていました。ごめんなさい。

次回も対戦よろしくおねがいします。

ISUCON11本選 kotamanegiの参加記

概要

ISUCON11本選にチームkotamanegiとして一人で参加し、学生2位になりました。 主要な改善点・工夫は

  • 自動デプロイスクリプトを書く
  • DBのindexをきちんと構築する
  • 負荷が大きくなってきた場合の強制タイムアウト処理を実装する
  • DBとZipファイルの処理を行うサーバとそれ以外の処理を行うサーバに3台のマシンを分離させる。

の4点でした。 結果は全体11位/学生2位となり、賞金10万円+Splunk賞とYahoo賞の2つの企業賞を獲得できました。 Splunk賞は全体11位、Yahoo賞はスコア下4桁が8200に最も近い学生チームが受賞ということで2つも受賞できてラッキーでした。

開戦前

チーム紹介など

f:id:kotamanegi:20210920114156j:plain

この時は賞金を取れると予想していなかったので期待に答えられなくてスマンやで〜と思っていました。 ですが優勝こそ逃したものの賞金は獲得できたので有言実行に近い結果を残せました。

僕は期待を裏切らない男です。(イキリ)

事前準備

複数台与えられた時のシステム構成を考えていました。 DB1台+Web2台で、Web2台間はnginxでいい感じに振り分けるつもりでした。

作業のタイムライン

作業メモをとっていないので順序は適当です。

前半戦

まずベンチマークをとった後、サーバにログインしようとするとエラーが出て質問を投げました。ISUCONポータルへの再ログインやGitHubへの新規SSH鍵の登録などをしていると治ったのですが、原因は謎です。

ログイン出来るようになった後は、初手でDBサーバを分離しました。 mysqlでroot権限でログインするためにsudo mysqlが必要だったのはしばらく困りましたが、基本的には予選と同じ流れでうまく行きました。

分離後、この段階でようやく当日マニュアルを読みはじめました。 学内システムの高速化というテーマだったので、成績確認よりもまずは提出物確認・アナウンスの確認を高速化した方がよいのかなぁと感じました。

提出物がzipで管理されていたので、ディスクIOを分離するために提出物確認APIを別サーバに分離するとジャッジ中の点数は上がりましたが途中で整合性が取れずにFailするようになってしまいました。

後半戦

サーバの負荷をtopコマンドで確認すると、DBサーバのCPU使用率がMAXのまましばらく停滞していることに気が付きました。とりあえずIndexを張ってみると途中でFailすることはなくなったものの、最後の整合性チェックでは相変わらずFailのままでした。

成績確認に関連するAPIがエラーを出していたので確認するとどうやらリクエスタイムアウト後も処理が続行されてDBサーバに負荷を掛け続けているらしいということがわかりました。 そこで同時実行数の設定値以上の数のリクエストが来たらtime.sleep(inf)を実行し強制的にタイムアウトにするという仕組みを実装しようと考えました。 さすがにこの解き方は想定外ではないかと思って質問を投げるとルール上OKとの返事が返ってきたので安心して実装できました。 この改善策を入れるとFailすることはなくなりました。

最後に細かい改善を入れたり、アナウンス用のDBサーバを別途用意しようとして失敗したりしている内に時間切れになりました。 アナウンス用のDBサーバを立てるのは想定解法だったらしいので悲しいです。

分析

成績確認用のAPIが原因でFailしがちだったのでそこを修繕出来て良かったと思っています。 Redisへの載せ替えなどは考えたのですが、再起動試験でFailしそうだと予想して予めインストールされていたソフトウェアだけを使ったのが結果として良かったと感じました。

アナウンス用のDBを別途用意するのは途中まで実装していたのですが、外部キー制約に引っかかってしまい解消することが出来ませんでした。外部キー制約そのものは外すと本選終了後のテストでコードレビューされてFailするのかなと考えていたので、まさか外しても良いものだとは思ってもいませんでした。外してよいかを質問でちゃんと確認しなかったのは反省点です。

Discordの感想戦

「推測するな、計測せよ」という標語がDiscordのあちこちで飛び交っていて、ほぼ推測のみの野生の勘と運だけで乗り切れてしまったとは言える雰囲気でなく心の中で懺悔していました。 結局会話の中でそれがバレてしまったんですが、「よくそんな丸腰でここまで来れたな」と言われてしまい、自分の運の強さを再認識した感じです。

来年は今年より成長している予定なので計測ツールを持っていこうと思います。

感想

ISUCON初参加初本選初優勝は果たせませんでしたが、初参加初本選初入賞は果たせたので大満足です。賞金10万円は欲望の赴くままに使わせていただこうと思います。