夏の終わり

今日明日をもって 2 か月あった夏休みが終わるので、振り返ってみます。

競技プログラミング

もともと、夏休みは競プロをたくさんやる予定でした。実際、そこそこの時間を費やしました。以下やったことを書いてみます。

PAST の過去問

以前 tsutaj さんから PAST 本の献本を頂いたので、これを読みながら PAST の過去問を解きました。

最初はバチャ形式でやろうと思っていたのですが、 5 時間連続で向き合うのが結構きつくて結局いつもの精進と同じ感じで解きました。前半の問題は実装が大変な問題が多く、後半は典型アルゴリズムや競プロ特有のテクニックや考察が多かった印象です。後ろのボス問(?)やフローの知識が必要な問題にはまだ手を付けていません。

自分が特に勉強になったなと思ったのは次の問題です。

atcoder.jp

atcoder.jp

atcoder.jp

時間があればぜひ解いてみてください。 ABC で出題されたら水 diff くらいにはなりそうな問題たちです。

ARC の精進

ここに水diff以下の問題を集めて解いていました。 やはり ARC の問題は難しいですね。。。 2 か月ほど期間を設けはしたのですが、結局全問題を解き切ることはできませんでした。

ARC では ABC と違い「何回も過去問で見たような問題」があまり出ませんので、パターンマッチングが通用しません。それが個人的に一番の苦手ポイントです。

ですが、「どういったところに着目するか」だとか考察の手順みたいな、もっと根本的で抽象的な部分で、 ARC の問題たちには共通しているところがある気がしています。今はまだそれが見えていませんが、いずれ掴みたいです。

復習

夏前から、新しく「記録」の概念を取り入れてみました。やってることは単純で、出会った中で解けなかった問題や印象に残った問題を、解法のポイントやコメント、解きなおそうと思ったらその期限の目安などと一緒にスプレッドシートに記録するだけです。

解きなおすか否かの基準は「解けなかった」「解けたけど完全に理解できていない」「いい問題だと思った」など割と適当です。

正直解きなおしの作業はあまり楽しくないです。一度見た問題なので新鮮味に欠けますし、解けなかった問題となると「解けなかった」という失敗体験がよみがえって嫌な気持ちになるからです。

ただ、解きなおしをして新しい発見をしたり、昔は解けなかった問題が解けて嬉しい気持ちになることがあるのも事実なので、もう少し続けてみようと思います。

ちなみに、「記録」の一環として、特に学びがあったと感じる問題はスプレッドシートだけでなく ScrapBox にも記録するようにしています。スプレッドシートよりも詳細に学びや考察の道筋を記録できるので気に入っています。

オンサイト

帰省に際して、東京近辺で開催されたオンサイトイベントにいくつか参加しました。

  1. Maximum-Cap 2023
  2. ITF.PC 2023
  3. JAG 夏合宿

夏合宿に関しては参加記も書いたので、そちらもよければ読んでいただけると嬉しいです。

人見知りなので結構びくびくしながら参加したんですが、結果的にどれも参加してよかったです。

特に、

  1. チーム戦の練習になった
  2. 競プロ er と交流できて、いい刺激になった
  3. 楽しかった

あたりが参加してよかったと思うポイントです。

北海道に住んでるとなかなかこういった機会がないので、参加できるときに参加できるオンサイトには参加していきたいなと思います。

アニメ

暇なのでアニメを何本か見ました。せっかくアマプラに入ったしね。

ぼっち・ざ・ろっく！

去年の秋に放送されていたと思いますが、今更見ました。正直、こんなに感動するとは思いませんでした。あれだけ人気があるのもうなずけます。

土壇場でバンドのために覚醒するぼっちちゃんがかっこよかったです。

サマータイムレンダ

友人に勧められて見ました。ホラー要素とミステリー要素が両方あって面白かったです。面白すぎて私は 24 話連続で見てしまったのですが、1話1話考察を挟みながらもう少しゆっくり見ればよかったなと少し後悔しています。

幼女戦記

タイトルと「転生もの」という情報から敬遠していたのですが、見てみたらドはまりしました。主人公のセリフの言い回しや、たまに挟まるコミカルなシーンがハマりポイントでした。あと ED がかっこよくて好きです。小説版があるみたいなので全巻購入することを検討しています。

Another

ホラー系です。ミスリードや伏線が散りばめられていて面白かったです。人が死にまくるアニメとして有名ですが、本当に当たり前のように人が死んでいきます。人ってこんなに簡単に死ぬのか。。。

麻雀

暇なときに雀魂をやっていました。今年の 2 月くらいに雀豪に昇格したのですが、現時点でそのときのレートよりほとんど上がっていません。玉の間での平均順位も 2.5 台で、限界を感じています。

上がるためにはもう少し牌効率や押し引きの勉強をする必要がありそうです。まあ気長にやっていきたいと思います。

音楽

例のごとく YouTube などで音楽を漁っていました。

www.youtube.com

さっきも書いた幼女戦記の ED です。

www.youtube.com

2014 年のボカロ曲みたいです。初めて聞いたときは「こんなボカロ曲があったのか」と衝撃的でした。聞き終わったあとに残るなんとも言えない寂寥感が好きです。

www.youtube.com

youtu.be

2 曲ともぼっち・ざ・ろっく！の劇中歌です。歌詞もメロディーも心に残るいい曲です。精進中に聴くこともあります(気分が上がります)

www.youtube.com

投稿者のしぐれうい様については存じ上げていなかったのですが、初めて聞いたときに MV の女の子のダンスとメロディーにハマってそれ以降何回もリピートしています。最近はショートもこれに汚染されてきています。助けてください。

研究室

3 年の後期になるとぼちぼち研究室配属が始まります。夏休みの間にじっくり考える予定でしたが、気づけば夏休みも終わりです。何も考えていません。マズいです。

将来

何も考えていません。マズいです。





皆さんはどのような夏を過ごされましたでしょうか。今年も早いものでもう 10 月です。季節の変わり目は体調を崩しやすいと言います。皆さんも体調には気を付けてお過ごしください。

JAG 夏合宿 2023 参加記

こんにちは。Today03 と申します。今回は JAG 夏合宿 2023 に参加したので、感想などを記していきたいと思います。

きっかけ

私は今年の ICPC 国内予選には出場しませんでした。これは、2027 年度の大学院卒業(予定)までの 3 年で 3 回出れるように参加権を残しておきたかったからです。

というわけでほぼすべての参加者がアジア地区予選への出場権を得ていると思われる中、ソロでの参加という形になりました。

私が今回の夏合宿に参加したのは、夏合宿の募集要項の対象者の項に

今年度の地区大会または来年度以降の ICPC に参加資格のある方すべて。

と記載されていたのが決め手でした。結果から言えば、参加して本当によかったです。

申し込み～当日まで

9/8 あたりまでに参加料を振り込むよう案内がありましたが、当然のごとく締切日の振込手数料がかからない時間帯ギリギリに振り込みました。。。

Day1 コンテスト前

開始日の午前に荷造りをしました。持ち物は以下の通りです。

  • PC
  • 各種充電器
  • 蟻本・PAST 本
  • 筆記用具・A4 ルーズリーフ
  • クリップボード
  • 2 泊分の着替え
  • 歯ブラシ・歯磨き粉等
  • ポケット英和辞典
  • ライブラリ
  • iPad

持ってくればよかったもの

  • 歯磨き用のコップ
  • スリッパ

持ってきたけど使わなかったもの

Day1 コンテスト

ソロ参加だったので即席でチームを組む必要があり、2 人で参加されていた香川高専のお二人 (take000 さん、misonikomipan さん) のチーム -O3 に入れてもらいました。

C++ を書ける take さんがメイン実装担当、私がサブ実装担当、misonikomipan さんが英語解読担当ということになりました。

Day1 は 2022 年の韓国の国内予選のセットでした。以下通した問題順に振り返ります。

A

いちばんの簡単枠 (?) でした。 take000 さんにささっと実装してもらってAC。

C

簡単枠 2 。ABC313-C と全く同じ問題です。これもささっと考察・実装を終えて AC 。

E

簡単枠 3 。最初問題文を誤読していて 1 ペナを出してしまいましたが、 misonikomipan さんが誤読に気づいてくれて何とか AC 。

G

簡単枠 4 。メモ化再帰すればいいだけだということに気づいて実装させてもらいました。最初メモ配列のサイズを見誤って RE しましたが、少し大きめに取り直すことで AC 。

K

最初はダイクストラみたいなことをすればよさそうという結論になりましたが、よく読むとグラフ 1 つにつき 1 辺以下しか移動できないので DP で OK 。これも take000 さんに実装してもらって AC 。

F

かなり通されていたので残り時間はこの問題に取り組んでいました。 SCC をしてトポロジカルソートした後 DP すればいいよねとなり、かわるがわる実装していましたが、どうしても RE ・ TLE がとれずコンテスト終了。

よく読み直すと各頂点の出次数が 1 以下とあるので、わざわざ SCC なんてする必要は全くなかったようです。。。

Day1 コンテスト後

夕食を取った後ルームメイトと顔合わせをしました。 sotanishy さん、 Kite_kuma さん、 sunrize さんのお三方がルームメイトでした。最初はかなり緊張していましたが、全員気さくで面白い方でした。よかったです。

顔合わせの後はすこし休んだ後 ABC にでました。部屋にいる全員が ABC に出ていたため程よい緊張感が流れており、これまでで一番集中できたと思います。時間ギリギリに F の黄 diff を通して Rating+82 、青が射程圏内に入りました。かなり嬉しかったです。

ABC 後は一人で風呂に入りに行き (他のメンバーは ABC 前にすましていました) 0 時に就寝しました。 ABC による興奮と普段と違う環境によりなかなか寝付けませんでした。

Day2 コンテスト前

7 時に起床。身支度→朝食→コンビニで昼食購入→コンテスト準備という流れでした。昼食はおにぎりを 4 つ購入しましたが、個人的にはこれがちょうどよかったです。

Day2 コンテスト

Japan Alumni Group Summer Camp 2023 Day 2 - yukicoder

C

幾何でした。解説では直径に着目するというとても賢い解法でしたが、私たちはそれに気づかず頑張って角度を計算したりしました。わざわざ fraction 構造体を定義してちまちま計算して AC 。 take さんと交代しながら実装しましたが、なかなか辛かったです。

K

a→b→c の遷移ができないという条件の処理に困っていました。

各頂点について、累積コストと遷移元の頂点のペアの情報を保持しておけば、 DAG なので頂点を順番に見ていくことで DP ができます。あとは各頂点で次の遷移先をすべて探索し、 a→b→c の条件に当てはまらないような遷移元にあたるまでコストの累積コストが小さい順に探索するという操作をすれば OK です。この探索は全体で高々合計 O(K) 回でできることに気づき、方針を軽く説明して実装させてもらいました。

なんとか AC 。とても嬉しかったです。

これ以降は、順位表の状況的に A, H を中心に考察しようということになり、分担していました。

A

計算式をこねくり回しても何も見えてこずかなりつらかったのですが、実験コードを書いて実行してみると、 f ( k ) = ( k - 1) ^ N になることに気づき、慌てて実装、 AC しました。最初から実験しておけばよかったです。

H

take000 さんが実験コードを書いてくれ、 N に対して答えが 1 以上となるような K は O(\sqrt{N}) でわかることは分かったのですが、それ以上は何もわかりませんでした。他のチームの話を聞いてみるとエスパーで通したところが多かったようです。 K より簡単想定らしく、信じられなかった。。。

B

misonikomipan さんがいい感じのところまで考察を進めてくれて、僕が misonikomipan さんの手足となって実装していました。出力デバッグをしまくってサンプルを合わせようと四苦八苦していたのですが、コンテスト終了。

Day2 コンテスト後

夕食、風呂を済ませて、ルームメイトと大富豪をしました。大富豪 streak 、 tourist 出しなどのおもしろワードが飛び出していました。楽しかったです。

そのあと ARC に出ましたが、普通に冷えました。悲しい。

Day3 コンテスト前

朝食が質素でした。

Day3 コンテスト

(yukicoder に追加されたらリンクを貼ります)

A, B

簡単枠ということで take000 さんと私でそれぞれ A, B を実装して AC しました。ある程度素早く通せてよかったです。

J

順位表の通され具合と、問題のテーマから J が解きやすそうだと個人的に判断し、ずっと一人で取り組んでいました。他のお二方にはその他の問題の考察をお任せしていました。

編集距離は前から決定していけるので、グリッドの全文字について、その文字が T の何文字目にあたるかを全探索するような DP をすればよさそうという結論に至り

dp _ {i , j , idx} = T の idx 文字目がグリッドの (i, j) の文字目になるときの編集距離の最小値 のように DP テーブルを定義して実装しましたが WA 。 色々なテストケースを試していると

2 2 
ab
dc
abxcd

で 2 と出力してしまっていることに気づき、修正。 それぞれのマスで「待機」するような遷移があれば 1 にできますが、工夫しないと O ( H W T ^ 2 ) になります。 ep _ {i, j, idx} = \min(dp _ {i, j, 0} + idx - 1, dp _ {i, j, 1} + idx - 2, ..., dp _ {i, j, idx - 1}) を定義することで高速化して再度提出しますが、 WA 。

ランダムテストを書いてみると、

4 4 
xaxx
xbxx
xxcx
xxdx
abcd

で 2 と出力してしまうことに気づきました。どうやら各 idx での更新が終わった時に自身の値と「他のマスの値+距離」を比較して DP テーブルを更新する必要がありそうです。最初は各 idx でダイクストラをしましたが、最大ケースで 30 秒ほどかかってしまうことがわかり断念。よく考えると DP 値が左・下方向と右・上方向に伝播するように 2 重 for ループでの更新をそれぞれ 1 回ずつやればいいことに気づいて実装、提出しました。 AC 。

時間がかかりすぎな感じがしますが、自力でマズいケースを見つけて修正しての AC だったので嬉しかったです。

そのあとはお二方が C, I をいい感じのところまで考察していてくれていたので詰め切ろうと 3 人で頑張っていましたが、力及ばずコンテスト終了。

Day3 コンテスト後

北大勢や tsutaj さんと少しお話をした後解散しました。

総評

3 日間で合計 13 時間 (AtCoder のコンテストを含めると 17 時間弱) も競プロをやりました。これほどの時間と集中度で競プロをやったのは人生で初めてかもしれません。

また、たくさんの競プロ er と交流できて、刺激ももらうことができました。本当にいい経験になったと思います。参加してよかったです。

素晴らしい合宿を開催してくださった JAG の皆様に感謝。

余談

私より何倍も強い方々が真剣に凹んだりしてるのを見て、自分もがんばらなきゃな。。。という気持ちになりました。来年は国内予選に出る予定なので、予選を突破して、今年よりも強くなって、また夏合宿に参加したいです。精進します。

AHC020 参加記

こんにちは。Today03 と申します。 今回は AHC020 に参加したので、感想や戦略などを記していきたいと思います。

コンテスト前～開始

前日の ABC の興奮によりなかなか寝付けず、起きたらなんと 14 時 58 分になっていました。飛び起きて PC 起動 & 参加登録。冷静に考えるとアルゴリズムのコンテストと違って 1 分 1 秒を争うようなものではないのでいったん心を落ち着かせながら問題文に目を通しました。

atcoder.jp

前回参加した AHC016 よりも問題概要は理解しやすかったです。

問題概要

  • N個の放送局 ( N=100) とそれをつなぐ M 本の辺、 K 人の住人 ( 2000 \le K \le 5000 ) がいます。

  • 住民と放送局の座標、辺の重みが与えられます。

  • 各放送局は (0,0) にある放送局と連結でなければ機能しません。

  • 各放送局は「強度(=放送半径)」を設定することにより、一定の半径以内にいる住民に放送を届けることができます。

  • コストは使う辺の重み、各放送局の強度の 2 乗(=面積)の総和により定められます。

  • コストが小さいほど得点は大きくなります。また、放送が届かない住民がいると得点は大幅に小さくなります。得点を最大化してください。

正確な記述ではないですが、大体上に書いたような感じです。問題文を見たとき、「あ、これはアルゴリズムの知識である程度戦えそうだ」と感じました。第一印象は以下のような感じです。

第一印象

  • とりあえず、辺のコストに関しては最小全域木を構築してやればよさそう。

  • となると鍵は各放送局の強度の決め方になるけど、とりあえず、「各住民が自分と一番距離の近い放送局の放送範囲に収まる」ように決めてみよう。

そんなこんなで実装して提出したコードがこれです。 結果は 411516112 点。この時点で 22 位、橙パフォ相当の得点が出て非常にびっくりしました。

（グラフはこちらのものを使わせていただいております。）

改善 1

ここまでは、各住民について「自分と一番距離の近い放送局の放送範囲に収まる」ように放送局の強度を決めていましたが、これだと無駄があるように感じました。「住民 A は放送局 B と一番近いけど、それより遠くにある放送局 C の放送範囲をちょっとだけ広げればその方が結果的に軽いコストで済むのにな」みたいなケースがあると思ったからです。というわけで、強度の決め方を次のようにしました。（住民ベースの決め方になります）

  • 各住民について「どの放送局に属するか」を次のように決める。

  • 放送局を全探索し、「住民がその放送局の放送範囲に収まるために追加で必要なコスト」が最小になるような放送局を選んで、そこに属するようにする。

そんな感じで実装して提出したコードがこれです。得点は 440108423 点、なんとびっくり、その時点で 10 位に入る得点が取れました。

ここでいったん休憩して順位表を眺めたりコンビニにたけのこの里を買いに行って食べたりしていました。

改善 2

しばらく休憩してから、また改善に取り掛かりました。 先ほどの提出を visualize してみると、次のような感じになっていました。

この画像からわかる通り、明らかに無駄な点が2つあります。

  • 使用していないのに、 (0,0) の放送局と辺でつながっているニート放送局がいる。

  • 円がかぶっている箇所がかなり多い。

前者については (0,0) から DFS をすることによってある程度解決できます。(解説放送では Prim 法を改良したアルゴリズムが紹介されていました。また、Twitterのタイムラインでは「最小シュタイナー木」なるものの考え方を使うとよいという情報がありました。ここに関しては単に DFS するよりもよい解決策があるはずです。)

問題は後者の方で、自分のアルゴリズムの能力ではなかなか改善することができませんでした。

とりあえず DFS した解を提出しました。(これ)

ニートの処理は少なからず効果があったようで、得点は 453993080 点。また少し順位が上昇しました。

改善 3

これ以降は手探りで改善していく状況が続きました。手元でいろいろ試していたはずですが、コードをすべて一つのファイルで管理していたため、記録が残っていませんでした。最終的な提出はこれです。フォーマッタをかけずに提出したので非常に見にくいコードになっております。申し訳ありません。

これまでの方法でいったん各住民が属する放送局を決定した後、次のような貪欲法を回しました。

  • ある放送局が別の放送局の最遠住民（放送範囲の一番端にいる住民）を奪い取ることを考える。

  • これにより少しでもコストが減るなら採用、減らないなら無視。

これを念のため時間の限り回すようなコードを実装しました。

少しは効果があったようで、30 位だけ順位が上がりました。得点 462915587 点です。

visualize すると次のような感じでした。かなり地味ですが、細かい部分の円の面積やかぶりが減っています。

コンテスト終了

これ以降もいろいろ試して提出してみましたが、結局改善はできず、コンテスト終了。最終提出の直前に北海道に大きめの地震が来ました。怖かったです。「AHC やめれないんだけどｗｗｗｗ」みたいなツイートをしようかと思いましたがさすがに自重しました。

最終結果

最高得点は 462915587 点で最終順位は 167 位、パフォーマンス 1813 を出すことができました。自分にしてはよくできたと思っています。

いろいろと振り返り

あまりヒューリスティック特有(?)の技術を使えなかったのは心残りな点です。解説放送や感想戦を見た限り、上位勢は山登りや焼きなましなどのランダム性のある探索をしている人が多かったようです。このあたりの知識や技術は復習しつつ身に付けていきたいですね。

今回は初めてしっかり取り組んだ AHC でしたが（過去2回出ていますが、 1 回は参加登録しただけ、もう 1 回は何も分からずほぼ最低ランクの順位をとってしまっていました。）、アルゴの知識もかなり活用できて、とても楽しむことができました。てりーさん、作問ありがとうございました。これからも AHC 楽しんでいきたいと思います。

拙い記事でしたが、最後までご覧くださって本当にありがとうございました。何かの参考になれば幸いです。