ICPC Asia Yokohama Regional Contest 2023 参加記

図1. ICPC 会場の様子

はじめに

2023/11/25 - 11/26 に開催された ICPC アジア地区横浜大会にチーム masamune として参加したので、記憶が飛ばないうちに記します。

自己紹介

まーたというハンドルネームです。各種サイトには ma_tw というユーザ名を使っています。一応アルファベットだと Marta なのかなと思っています。

編集時点で競プロは水色。早く青になりたいと思いつつ、精進ができていません。

masamune について

チームメイトのお二方は momoyuu さんと だれ さん。編集時点でどちらも AtCoder 黄色なので、黄黄水とかなり実力に差があるチームとなっています。実のところいろいろとありがたいことがあり私はこのチームのメンバーとなれています。2 人に追いつけるよう頑張ります。

Day 1

正午ごろ、日本大通り駅に到着。チームで昼食を摂ろうという話をしていたのですが、日本大通り周辺地帯にあるのは高級レストランばかりで入りやすい店が少ないことが判明。最終的に無事ファミレスに入れました。

13:15 頃には既に会場に到着。噂には聞いていたものの、実際に受付から全て英語だったのであまり慣れない感覚でした。実はその日はコーチが欠席で、それを伝える仕事を任されてしまったのですが、シンプルに "Our coach is absent today because he's sick." とかで乗り切りました。

あの時点で知り合いがいないか見回していたのですが、どうにもピンと来る人が居ず断念。そんな感じで割とぼうっと過ごしていたら早速開会式の時間に。システムの説明での Clar の内容が印象に残っています。

リハーサル

事前にエディタをどうするか話していたのですが、結局 VSCodium を使うことに。私は B 以降の読解やインタラクティブツールの使用のほか、US 配列へ慣れるために D の実装も担当しました。D は選び方が n!! になることがミソですね。ところで US 配列には大苦戦していました。特に括弧の位置がキー 1 つ分だけずれていたりするのが厳しいです。

リハーサル後

リハーサル後はチーム紹介の時間に。ここでも私がスピーカーとして抜擢されてしまいました。喋ることそのものはそれなりにうまくできましたが、原稿に目が向きがちだったのが反省ポイントです。

図2. チーム紹介スライド

夕食は masamune + nok0 さんの 4 人で中華街へ。どこも混雑の中入れたお店 (名前を忘れた) では、食べ放題でないメニューを受け取るために店員さんを呼ぶまでに 10 分かかるなどいろいろありました。なお料理はとても美味しかったです。写真は撮っていませんでした。

その後 nok0 さんに誘われ 2 人でゲーセンへ。チュウニズムが 1 台しか無かったため順番に 1 クレジットずつプレイしました。私のリクエスト (無茶振り？) で nok0 さんに盟月と Chaotic Ørder をプレイしてもらいました。私も早く虹レになりたいです。

そんなこんなで宿泊先へ。

Day 2

図3. 朝の起床確認

全員無事起床したのを確認して、安心して会場へ。ここでコーチとも合流しました。ところがここで問題が発生します。既に駅には到着したはずのチームメイトの 2 人がいつまで経っても会場へ来ません。

図4. 迷子

なんと逆方面に向かってしまい迷ったとのこと。結局入場が開始して随分経ってから 2 人が到着。焦りました。

コンテスト

説明も終わりコンテストの時間に。だれさんが A を解いている間に私は B 以降の読解をして紙に問題を要約していきます。

B

プレイヤーのランクを一定の規則に従って上げる。与えられた条件がややわかりにくい。

C

観覧車のゴンドラを塗り分け、同じ色のペアを線分で結んだとき線分が交わらない場合の数。読んでいた時は最難であることも知らず淡々と読解。

E

a - b - c という並びの条件が複数与えられたときの順列の数え上げ。

G

カードが並んでいて、サイコロを振る度に左から出た目と \mathrm{mod} \ 6 で合同なものを消していく。最後に i 枚目が残る確率。

K

インタラクティブ。正方形の中の円があるので、こちらが指定した線分との共通長さを尋ねることにより半径と中心座標を求める。

途中 momoyuu さんが H を解くのに Dinic 法ライブラリを写経したりもしました。ここでもやはり US 配列に悩まされていました。練習しなければ。ちなみに H が落ちたとき私にかなりの疑いの目が向けられました。こわいですね。(ライブラリにも写経にも間違いはありませんでした。)

K は私がそれなりに考察に寄与しました。1 つの座標について、2 つの長さがわかればそこから初等幾何の力で座標と半径を求められるのではないかと頑張っていました。(実際に方程式を解いていたのはだれさんです。)

そのほかに、開始直後の環境構築をしたり、例のごとくインタラクティブ問題のテストを担当したりしていました。

その他の問題の感想についてはチームメイトお二人の参加記をご覧ください。(書くのかな？)

昼食ではお弁当が配られました。片手で食べやすいよう考慮されていると聞いていましたが、実際おにぎりとサンドイッチがメインでした。特におにぎりは味付けが絶妙で美味でした。他にもラムネやチョコをつまんでいました。

コンテスト中の机にはメンダコと、 masamune の守護神として福翁自伝を置いていました。メンダコは momoyuu さんの思考のお供になれていたようです。

コンテスト後

5 時間のコンテストもあっという間、コンテスト終了です。私としては頑張って考察していた K を通したかったです。いろいろ思いはありますが、まずはお疲れさまの時間です。途中でリアルの旧友と会ったりしたほか、会場の中をぶらぶらと歩いたりしていました。このタイミングで JAG 夏合宿で同室だった log K さんと会い、感想を話したりもしました。

作問陣の方々には申し訳ないですが、解説はあまり聞く余裕がありませんでした。

さて、解説やスポンサーのスピーチが終わり YesNo の時間に。masamune も 1 つ Yes を貰いましたが、最終的な順位は 29 位でした。また来年挑戦したいです。それはそうと Yes を貰えると会場に拍手が沸くので嬉しいですね。

図5. 順位表

優勝はノーペナ全完の Speed Star。異次元という言葉がふさわしいです。

懇親会

表彰等の後は隣の会場で立食懇親会。会場ではさきの log K さんのほか、JAG でチームを組んだ おここ さんとたくさんお話をしました。他にも rin204 さんや、chokudai さん、けんちょんさんなど有名な方と交流でき、とても楽しく貴重な経験となりました。これは個人的なことですが、私は元々会話があまり得意でなかったのにもかかわらず、他の方のおかげでたくさんコミュニケーションができたのも嬉しかったです。

そして以前会ったことのある方々が皆さん私のことを覚えていてくれたので、ありがたく思っていました。

ちなみにコンテスト中にいろいろなものをつまんでいたため、料理はあまり食べられませんでした。少しもったいない思いです。

その後 momoyuu さん、 SPD さんと会話しながら駅に向かい帰路につきました。

おわりに

今回が私の初めての ICPC の参加でしたが、このようにアジア大会に出場できたことはとても嬉しいです。来年はぜひもっと強くなって、もっとチームに貢献する形で再挑戦したいです。また来年は慶應大学からもっと多くのチームがアジア大会に進出できることを期待しています。

最後になりますが、チームメイトとコーチのお三方、主催者とスタッフの方々、選手の皆さん、その他 ICPC に関わってくださった全ての方々に感謝いたします。

拙い文章でしたが、お読みいただきありがとうございました。

AtCoder で水色になりました

はじめに

こんにちは。高校 3 年生の ma_tw と申します。この度、AtCoder で水色のレーティングに到達したため、その記録としてこの記事を書きました。(いわゆる色変記事です。)

筆者について

以前よりプログラミングに興味があり、高校 2 年生のとき少し Python を勉強していました。しかし特に作るものもなく、適当なコードを書いているだけでした。(ゲーム開発等にはあまり関心がありませんでした。)

そんなとき、競プロの存在を知ります。恐らくは Twitter で見かけたのだと思います。それで何となく AtCoder Beginner's Selection を解いてみたところ競プロに興味を持ちはじめ、コンテストに出始めるようになりました。またそのとき競プロには C++ が向いているということを知り、C++ を勉強しはじめました。そして今に至ります。

記録

初めてコンテストに参加したのが 2021/9/4 なので、およそ 1 年と 2 ヶ月での入水となります。

履修したアルゴリズム等

あくまでなんとなくです。(以下に並べたものの中でもまだまだなものもあります。)

  • 二分探索
  • DP
    • ナップサック DP
    • 区間 DP
    • bitDP
  • 累積和
  • いもす法
  • 座標圧縮
  • 繰り返し二乗法
  • 素数あれこれ
  • 基本的なゲーム問題
  • セグメント木 (ACL のみ)
  • UnionFind (ACL のみ)
  • DFS
  • BFS
    • 01BFS
  • ダイクストラ法
  • ワーシャルフロイド法
  • クラスカル法

心がけたこと

「たくさん問題を解く！」等は既に何度も言われているので、私なりに役に立ったと思うことを書きます。なお、これらはあくまで私個人の考えですので、参考程度に読んでください。

精進の際は教育的問題を解く

ABC 埋め等も大事だと思いますが、AOJ の Course*1 や、こちらの記事にまとまっている問題集など、いわゆる有名問題や練習問題として選ばれた問題などを積極的に解きました。これにより典型力は効率的についたと思います。

早さよりペナを出さないことを優先する

コンテスト中、早さを意識するあまり深く考えずに提出をした結果 WA が出てしまい、さらに焦ってボロボロになってしまうという経験が何度もありました。無闇に書いて投げるのではなく落ち着いて、ミスに気をつけながら解くほうがコンテストの結果は良かったです。

コンテスト中は精一杯解く

私は例えば ABC において、D が解けたあと気が緩んでしまい、「もういいか。E は無理かな」みたいな思考になりがちでした。ABC-D が碌に解けなかったころの感覚が残っているのだと思います。しかし実は E も考えればわかる問題であった、などということも多く、このような思考に陥るのは勿体ないです。E や F も解く気でしっかりと考察することで、5 完や 6 完を達成することも多くなりました。

これからの目標

とりあえず誕生日 (2023 年 6 月) までに AtCoder 青色を目標にします。そのために、

  • UnionFind を自分で実装
  • セグメント木 (遅延評価も) を自分で実装
  • フロー
  • よりレベルの高いゲーム問題 (Grundy 数等)
  • struct 関連に強くなる
  • 幾何

あたりを履修していこうと思います。(特にセグメント木実装とフローは頑張ります。) また、入水したらやろうと思っていたヒューリスティックにも挑戦していきます。

おわりに

正直、まだ入水した感覚が掴めていないです。競プロを始めた当初は遥か遠く思えた Rating 1200 という場所に到達できたということを考えると、なんだか感慨深いです。そもそも、自分がここまで競プロを続けられということが予想外でした。何はともあれ、さらなる高みを目指して、今後も取り組んでまいります。

稚拙な文章でしたが、最後まで読んでくださりありがとうございました。

*1:すみません、今見返したところ AOJ はあまり埋めていませんでした。