AtCoder Algorithm 黄色になりました

はじめに

5/31 の AtCoder Beginner Contest 408 で黄色コーダーになれました。 競プロに出会ってから約 7 年、途中離れていたのもありますが長かったですね…。

ロールバック再計算で 2005 になってました

自己紹介

上の画像を見ると分かるかもしれませんが、東京農工大学の修士 1 年です。 大学公認のプログラミング系サークルにも所属していて、競技プログラミング部門のリーダーだったりします(ICPC 国内が終わったら後輩に押し付ける引き継ぐ予定です)。

競プロに出会ったのは 2018 年で、初参加のコンテストは AtCoder Beginner Contest 100 でした。 初参加ながら(灰 diff とはいえ) C 問題を AC できたときの快感は今でも覚えています。 当時は水タッチして引退していました。どうせすぐ復帰するんだから消さなきゃよかったのに…

黄色になるまでにやったこと

知識

青になってから新しく覚えたアルゴリズムとかちゃんと覚えていないので、ざっと自分がある程度理解しているものを思いつく限り書き連ねておこうかと思います。

  • データ構造
    • Union-Find・重み付き Union-Find・Rollback 可能 Union-Find
    • セグメント木・遅延セグメント木・Binary Indexed Tree
    • K 番目の値を管理する Multi Set (これちゃんとした名称あるんですか？)
    • Convex Hull Trick
  • グラフ
    • 最短経路系(Dijkstra・Bellman-Ford・Warshall-Floyd)
    • LowLink
    • Kruskal
    • 強連結成分分解
    • フロー・最小費用流(Dinic・Ford-Fullkerson・Primal-Dual)
  • 木
    • 直径
    • Heavy Light Decomposition
    • Lowest Common Ancestor
    • Auxiliary Tree (指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木)
  • 文字列
    • Z-Algorithm
    • Trie 木
    • ローリングハッシュ
    • Manacher
  • その他
    • 平方分割・Mo
    • FPS 関連 (基本的な式変形・多項式の exp, log, inv など)

「名前だけなら知っている」は結構あるんですが、ちゃんと勉強したのは意外とないですね。

実装力の強化

ライブラリを整備したり、毎週の部活のバチャに参加したりしました。

精進の記録

2500 問解いたらしい

青 diff は半分くらい解いたらしい

おわりに

まずは憧れの暖色コーダーになれて嬉しいです。 最近派手な惨敗も少なく、また比較的得意な問題が多かったのもあって嚙み合ってくれた感が強いですが、久しぶりの Highest 更新からのチャンスを逃したら終わりだと思ったので頑張ってよかったです。

今後は ARC や ICPC に向けた精進をしっかりやっていきたいところです。 ちらっと見えている CodeForces のユーザー名を見ると分かるんですが、なんと青 (Expert) です。紫 (Candidate Master) ですらありません。 もっと言うと ARC の Rated 戦績がほぼ無です。純粋 ABC 培養人間です。次 ARC 出たらまず間違いなく落青します。 流石にこのままだと ICPC でまたボコボコにされる未来が見えるので、ARC・CodeForces・ICPC などで精進しようと思います。

私に ARC・ICPC で戦える考察力を身につけさせてくれるコーチを募集しています…

ICPC 2024 Asia Yokohama Regional 不参加記

Day -6

ぼく「来週は ICPC だ！がんばるぞ～」

Day -2

先生「コロナです」

ぼく「え？」

と、いうわけで

ICPC 2024 Asia Yokohama Regional 不参加記です。

ついでに 農工大 Advent Calendar 2024 19 日目の記事です。 技術系かどうかは怪しいですが許してもらいましょう。

水曜日にコロナウイルスに感染して ICPC キャンセルさせられたので、当日自分が何をしていたかを書きます。

Day 1 (12/21)

この日は午前 9 時に目覚めました。症状は大体治っており、多少の咳とカスみたいな声しか出ないという状態でした。

Twitter を眺めると選手の皆さんが続々と横浜に集まっているツイートを見かけていいな～という気持ちになりました。

また今年の T シャツ情報も流れてきて、このときそういえばと思ったのでチームメイトに T シャツとか貰えるのか聞いてくれませんかとお願いしました。 （参加していないのに貰うのも若干気が引けましたが、やっぱり欲しい気持ちが圧倒したので）

どうやらチーム紹介のダブルクオーテーションが 2 倍になる現象が発生し、AA が崩れるという事態が発生していることも知りました。 弊チームの Discord を見ると弊チームの AA にもダブルクオーテーションが使われているのでどうなっているかなと思ったら、うしさんがちょっと可哀想なことになっていました。

※ちなみにチーム紹介を書いたのは new_textfile さんです。

リハーサルが終わったと思われる時間帯に、T シャツが貰えることを教えてもらいました。ついでに名札やクリアファイルも貰えたらしいです。本当にありがとうございます…！

Day 1 のハイライト

夜は ABC に参加しました。冷えました。悲しいです。

24 時頃就寝しました。

Day 2 (12/22)

開始時刻が早まっていたらしく、起きたらコンテストが始まる 5 分前でした。慌てて配信をつけます。

しばらくは配信と Twitter を 2 窓し、1 人で盛り上がっていました。（後日談 : 懇親会でどなたかに僕の行動が言及されていたらしいことを漁師さんに聞きました　恥ずかしっ）

んぐコーチに novvcovv の位置を聞くと、ちょうど配信の会場カメラから映る位置でした。 よく見ると明らかに見覚えのある姿勢の悪さで椅子に座っている人が見えます。漁師さんでした。

※基本的には A01 の Screenwalkers の左前のカメラからの映像が映し出されていて、novvcovv は B03 でした。

10:45 に AOJ のミラーコンテストが開始されたので、簡単枠の解説を始めようとしていた配信を一旦ミュートし、僕も問題を読みました。

ここから novvcovv の順位を見守りながら問題読解などをしていました。普通に問題番号順に読みました。

A は流石に簡単ですが、B が普通に難しいです。ぱっと見で解けなくて困りました。

他の問題に目を通します。C はめっちゃ問題文が長くて嫌な気持ちになりましたが、じっくり読んで少し考えるとすぐ解法が浮かびました。

D は概要は理解したのですが、難しいです。放置しました。

E は実装が大変そうですが簡単でした。F は幾何っぽそうなので飛ばして、G を読みました。

インタラクティブだしどうせ二分探索っぽいことをやるんだろって気持ちになりますが分からないので飛ばしました。

H は見た目が嫌そうで飛ばし、I を読みます。問題が分かりやすく、どうせセグ木に乗るんだろうなと思いつつ考えましたが分かりませんでした。

J はどこも手を付けてないので飛ばして K を読みます。bit DP っぽいことをするのかと思いましたが 2023-E が未だに理解できていないレベルの bit DP 力ではどうするのか分かりませんでした。

L を読みます。区間 DP まではすぐ見えたので、頑張れば解けそうです。

というわけで配信をつけて、気になった問題の解説パートを聞きました。A, C はあっていたっぽくて良かったです。B, D, I はなるほどな、という感じでした。

ミラーコンテストで L を解こうと試みたんですが解けませんでした。悲しい。

そうこうしているうちに順位表では novvcovv が 6 完していました。どういうことでしょうか。

順位表凍結後はぼーっとしていました。novvcovv が D に提出をしていてびっくりします。

コンテスト終了後は Twitter を眺めて過ごし、解説と Yes/No を楽しみました。novvcovv の D は CE だったようです。

Day 4

漁師さんから T シャツとクリアファイル、名札などを受け取りました。

どうやら順位が印刷された参加証も僕の分があるらしい（え！？）ですが、それは全員分んぐさんが持っているらしいです。そのうち受け取ります。

おわりに

まずは novvcovv の漁師さん、new_textfile さん、んぐコーチ、ご迷惑をおかけして申し訳ありませんでした…。来年は体調に気をつけます。 （どうやら横浜でインフル A 型に罹った人が何人かいるらしいですね、お大事になさってください…。）

結果として novvcovv は 23 位だったようで、去年の sankaKsu が 55 位を大きく上回る成績でめちゃくちゃ凄いです。

来年はラストイヤーになるので、万全の態勢で臨めるようにしたいです。

以上です。最後になりますが、参加した選手の皆さんお疲れ様でした！WF・playoff 進出したチームの皆さんは引き続き頑張ってください！応援しています！！

ICPC 2024 国内予選　参加記

眠い＆疲れたので取り急ぎざっくりと　気が向いたらちゃんと書きます

new_textfileさんと漁師さんとチーム「novvcovv」で出てました。4完62位、学内1位で通過予定。

作戦

初動はlog_KがABをやり、漁師さんがC、new_textfileさんがDを見る。 それくらいしか作戦はなかった。

競技中

弊学はプリンター1台なので、問題文が来るまで時間がかかる。

A問題 (log_K, 2:21)

log_KがAの問題文を暗記→実装中に漁師さんがCを読む。

何故か if(n == 0) break; を if(n == 0); と書いていて30秒ほどロス。

リハーサルのときもしょうもないバグを量産していたので「こいつ今日大丈夫かな…」と思いながら修正してAC。

B問題 (log_K, 10:30)

log_KがBの問題文を暗記→実装中に漁師さんがCを読む→解けたらしいのでDを漁師さんとnew_textfileさんが読む。この辺で問題文が届いた気がして2人はモニターから離れる。

入力を勘違い（現在位置が与えられると思っていた）していてコードを書き直す羽目になり炎上しかけたが、落ち着いて実装しなおしてAC。

C問題 (漁師, 12:55)

なんか爆速で解いてた。

D問題 (考察 new_textfile & log_K, 実装 log_K, 38:19)

Bを終えた後概要を読み、new_textfileさんに「愚直シミュレーションして、一定範囲外かループになったら良い感じに」と言われる。 101×101の盤面に次に進む方角の情報を加えた3次元配列上で良い感じにやれば良さそうだったので、実装を引き受ける。

一発でサンプルは合わなかったが、サンプルが優しく1ケースずつバグを修正して提出したら1発ACした。えらい。 この時点で15位（瞬間最高）だった。

E問題 (考察 new_textfile & 漁師, 実装 new_textfile, WA)

問題読んでいないので何も言えない。ただ聞いていた感じ答えが Yes のケースを No と判定して通らないっぽくて辛そうだった。

F問題 (考察 漁師 & log_K, 実装 log_K, no sub)

漁師さんとあーだこーだ言い合っていると答えが高々4枚で、コインの方からシミュレーションすれば良さそうということに気付く。 実装が面倒くさそうで嫌だな～と思っていたら漁師さんに丸投げされてしまったので、ペーパーコーディングで実装方針を詰める作業に。

ある程度詰めたところでEが沼ったらしいので交代するも、普通に実装方針がカスすぎて超重実装に。 当然サンプルが合わず、Eを優先していたのでバグチェックする余裕もなく終了。

振り返り

Eは本当に何とも言えないが、Fは解けるべきだなあと深く反省。 考察力・実装力が足りない自覚があるので、横浜までに鍛えないと…（あと黄コーダーになりたいです）

ICPC 2023 Asia Yokohama Regional 参加記

はじめに

初めまして。チーム「sankaKsu」のlX57(log_K)です。ICPC 2023 Asia Yokohama Regional（アジア地区予選）に出場したので、その参加記です。

国内予選で学内1位だったとはいえ全体59位での通過だったので、WFを狙うというよりは一連の大会を楽しむ事をモットーに参加してきました。

行動録

0日目(11/24)

日中までに簡易ライブラリを整備しておこうと思っていたんですが、前日27時就寝だったこともあり数ヶ月切っておらずあまりにももっさりしていた髪をどうにかするために景気付けの散髪をした後部室で爆睡します。夜に労働を終えてから慌てて準備しました。

最終的には以下のライブラリを持っていきました。

  • グラフ・フロー系
    • ダイクストラ
    • ベルマンフォード
    • ワーシャルフロイド
    • 強連結成分分解
    • HL分解
    • 最大流（Dinic法）
    • 最小費用流（Primal Dual法）
  • データ構造系
    • セグメント木（通常・双対・遅延）
    • UnionFind
  • その他
    • テンプレ
    • ModInt
    • 組合せ

正直ダイクストラとかUnionFindとかならソラで書けるんですが、変にバグらせたくないので用意しました。我が家にプリンターがないのでチームメイトのSakasu君に印刷をお願いします。

そして荷造りをして24時半に寝ました。ここ数日の僕の就寝時刻が27時〜30時だったことを考えるとめちゃくちゃ早寝ですね。参考になるか分かりませんが持ち物は以下の通りでした。

  • 競技関連
    • 蟻本・鉄則本
    • コピー用紙
    • ぬいぐるみ
  • 生活関連
    • スマホ・iPad一式
    • モバイルバッテリー
    • 財布
    • 着替え（2日目の服と部屋着）
  • パソコン一式
  • 筆記用具

1日目

8時半にアラームをセットしていたのに7時前に叩き起こされて悲しくなります。いつも不健康な生活を送っているので、7時前に起きたのはめちゃくちゃ久しぶりです。睡眠アプリによると7/6ぶりだそうです。朝は昨晩のカレーを食べました。

10時にsunrize君・qLethonコーチと近くの駅で待ち合わせをしているので、それまで家でのんびりします。ついでにこれを書き始めます。これを書くのに使う写真とかいっぱい撮らなきゃな〜って思いつつルールを読んでいたらリハーサルでも会場内の写真は撮っちゃダメっぽいことが分かりほにょります。ほにょっていたらコーチが遅刻しました。

12時半に日本大通り駅に着弾する行程を組んでましたが、なんやかんや20分くらい早く到着します。会場の雰囲気にわくわくしたり、Tシャツににこにこしたりして待っていました。

リハーサルが始まって、US配列に苦しみながらもCまで解いてなるほどね～ってなりながら印刷テストをしたらtotoriさんがめちゃくちゃニヤニヤしながら届けてくれてコーチ共々爆笑してしまいました。

自己紹介パートはSakasu君に丸投げしました。弊学は「Tokyo University of Agriculture and Technology」なんですが（長い）、Sakasu君がAgricultureとTechnologyを逆に言いかけてあわや東京工農大学になるところでした。

全行程終わった後宿泊場所のゲストハウスへ行き、荷物を置いてから横浜中華街でご飯を食べました。

この日のABCはなんやかんやあってUnratedで出ましたが、結構悲惨なことになりました。その後夜食を食べて風呂に入って個人比早めに寝ました。

2日目

7時に起きたので寝坊は回避しました。コーチと朝飯買いに外出たら雨が降ってて悲しくなります。

優雅に朝シャワーなどを浴びて会場に向かいましたが、着く頃には雨でびしゃびしゃになってました。来年は傘をちゃんと持ってきましょう。

なんかそれっぽい写真を撮ってそれっぽいツイートをして気合を入れます。自撮りって難しいですね。

席に着き、注意事項を聞いてコンテスト開始まで待機します。支給されていたおやつセットがメロンパン・ラムネ・チョコ・グミ・ポテトスティックなど充実していました（ところで僕の残りのおやつセットないんですけど、sunrize君かSakasu君にパクられたかな？）

9:30〜14:30 コンテスト

まずテンプレを写経してから、Aを読みます。解法は一瞬でしたが実装が割とあってびっくりします。特に沼にハマることなくAC。

次にBを読みます。 c の制約が小さく、\textrm{O}(nc) が通りそうなので実装しますがTLEします。その後尺取りを考えるもサンプルが合わず、その間にチームメンバーがFを解いたらしいのでBと一緒に丸投げして、一旦別の問題を読みます。ここまで1時間です。

Bの事は忘れてDを読みます。文字列長 n に対して文字列ハッシュ+区間DPの \textrm{O}(n^{3}) が思い浮かぶので、紙で考察をまとめつつ頃合いを見て交代、実装します。途中で何度かバグを踏んで実装に手こずりますがなんとかサンプルが通ったので投げるとWAが帰って悲しくなります。悲しくなったのでまた交代します。

相変わらずチームメンバーにBを丸投げして、僕はDの粗探しをしますがバグを直して提出→WA、ハッシュ衝突を疑い変えてみる→WAとことごとく落とされこれも一旦諦めます。

GとKを読み、Kの方が行けそうなので実装します。自分の解法では最悪ケースちょうど1024回クエリを消化するのですが、これもWAを吐いてきます。

合間合間にチームメンバーがBの修正→提出をやっていましたがどれも落とされ、結局2完55位という成績に終わりました。

解説パート・結果発表

解説パートが始まる前の小休憩の時間に、近くのテーブルにJAG夏合宿で同室だったまーたさんを見つけたので難しいねという話をしていました。（チームmasamune自体は6完してました、凄い）

肝心の解説パートですが、Bが \textrm{O}(nc) でも通せるみたいなこととDが凄い簡単そうに解説されてたのとKがディスク内の1点が分かると追加で4回クエリをすることで特定できるのが何故なのか分からなくて頭の中が「？」になってました。

結果発表パートは面白かったです。すべてのオンサイトであれやりませんか？

余談ですが持って行ったぬいぐるみが紹介されていました。ぬいぐるみの服と帽子は親が趣味で編んだもので、親は「実質優勝しました」と言っていました。

交流会

コンテスト中に色々食べたせいで全然お腹が減っておらず、あまり食べられませんでした。というか提供されていたメニューのカロリーが軒並み高くて笑ってました。

大学生になってからのオンサイトは初めてなので、ちゃんと交流ができるかめちゃくちゃ不安でしたが、交流会でもまーたさんと会話をしたのを皮切りにmasamuneの皆さんやおここさん、nok0さん、物理好きさん、hourenさん、熨斗袋さん、itigoさん、わくさん、olpheさん、kotamanegiさん、shobonvipさん、shinchanさんと色んな人と交流できて楽しかったです（あとJAG夏合宿で認知できていたのでSSRSさんにも挨拶をしましたが、自分の会話能力が低すぎて上手く会話できず変な人だと思われた気がします、すみません…）。

名刺を作っておくべきだなと思いました。もちろん作っていなかったのでいちいちTwitterのプロフィールを見せる人になってました。それと意外とTwitterが認知されててびっくりしました。

あとchokudaiさんとけんちょんさんと写真を撮っていただきました、本当にありがとうございました！

他にも企業の方から貴重なインターンのお話を伺ったり、謎のハウリングで耳を破壊されたり、スタッフが風船をすべて割って拍手が起きたりと楽しかったです。

帰路

デスク近くにぶら下がっていたラミネートされたチーム看板が思ったよりでかくてリュックに入らず手で持って帰りました。帰りの電車でめちゃくちゃ見られました。参加証と共に大事に部屋に飾っておこうと思います。

Day 3

25時に寝て、15時半に起きました。たっぷり14時間半寝ました。今11/28の午前2時にこれを書いていますが全く眠くなくて困っています。あと今週中間試験と中間レポートがあってやばいです。ﾀｽｹﾃｸﾀﾞｻｲ

おわりに

去年のICPCは国内予選落ちだったので、今年はアジア予選に進出できてとても嬉しかったです。簡潔に参加記を書こうと思っていたのにここまで結構書いちゃったくらいには2日間楽しく、また有意義に過ごせたと思います。

ただ、肝心のコンテストは全く歯が立たず、応援してくださった同校の方々に良い結果を見せられず悔しかったです。国内予選時からAtCoderのレートが400くらい上がって、青コーダーになっていたので多少がなんとかできるだろうと思っていたのですが、青になっても何もできなかったです。来年は暖色になって国内予選に臨みたいと思います。

最後になりましたが、国内予選・アジア予選と共に戦ってくれたsankaKsuのsunrize君・Sakasu君、それからコーチのqLethonさん、当日応援してくださった農工大MCC競技プログラミング部門の皆さんおよび家族、そしてICPCの運営・スタッフ・審判団の皆さん本当にありがとうございました。