hogecoder

tsutaj 競技プログラミングの記録

2023 年の振り返り

月報

去年に引き続き、1 年の振り返りをしていきます。

競プロ

PAST 本を書いた

書籍を執筆する機会をいただけるなんて思ってもみませんでした。購入された方が何かしらの発見を得られるように頑張って書きました。

私が担当したのは 3, 4, 6, 7, 8 章なんですが、図を多めに使って視覚的に理解しやすくなるよう努めました。書籍について詳しく知りたい方は、こちらの記事もご覧ください。

tsutaj.hatenablog.com

JAG 国内予選・夏合宿・ICPC の手伝い

国内も夏合宿も、セット準備を少しだけ手伝いました。

JAG 夏合宿は 4 年ぶりに開催できました。開催にむけて rian さんがメチャクチャ頑張っていて、本当に全てを担当していてかなり大変そうだったので、来年からは現地の運営周り（場所や食事を取ったりとか）は自分がやるつもりです。来年も参加資格ある人は参加してね！なかったらスタッフとして参加してね！！

また、今年も ICPC アジア地区横浜大会 の手伝いをしました。去年は年末ということもあって一部日程しか参加できなかったんですが、今年はフル参加できました。来年もぜひ手伝いに行きたいです。

CodeQUEEN 決勝にスタッフ (Writer) として参加

CodeQUEEN 決勝 のWriter を頼まれたときはかなりビックリでした。やるからには最後まで飽きさせないようにしたいなぁということで、手を動かせる系の問題にしたつもりです。参加してくださった方々ありがとうございました。

競プロ LT を 2 回した

1 つは社内で、もう 1 つはユニークビジョンさんの LT 会で行いました。なんだかんだ作問を何年か経験していて、そのノウハウを還元したいなーという気持ちでやってました。

社会人になって、精進の時間があまり取れなくなっていくにつれて、競技者というよりは現役世代を応援する立場で界隈に貢献したいという気持ちが強くなってきました。JAG で夏合宿や ICPC などの運営を手伝ったり、スライドで知見を残すのも、これが原動力になっている気がします。また今年は執筆した本を大学の後輩に配ったり、CodeQUEEN という新しいオンサイトコンテストの手伝いができたりもして、とても充実感がありました。来年以降も何らかの形で競プロを陰ながら盛り上げられたらと思ってます。

あ、AHC についてはまだまだ新参者なので、これからもがんばります！

仕事

転職しました。X (Twitter) にも書いてますが、モノグサ株式会社にいます。もう早いもので入社してから 11 ヶ月経ちますが、楽しくやっていけてます。

今思えば、以前から教育に対して潜在的に興味はありました。人に何かを教えて、その人ができることの幅が広がるとたまらなく嬉しいですし、どうやったら効率的に学習が進むんだろうとかを考えるのも好きです。自分を分析してその興味に気づいたとき、入社したい気持ちがかなり強くなっていきました。

でも肝心の Web やモバイルアプリの開発経験はほとんどなく、趣味で少し触ったことがあるくらいの状態でした。さすがにまずいだろうということで、Udemy で Web アプリケーションの基礎を勉強したり、応用情報の参考書を引っ張り出して復習したりしました。今思えばだいぶ思い切った行動でしたが、ありがたいことに採用してくださり、今ではフロントエンドもバックエンドもモバイルアプリ開発もやっています。また、ただソフトウェア開発をするというだけじゃなく、「良い記憶体験のためには本質的に何が必要なんだろう？」と、枠組み自体を議論できる機会もあるのが個人的にはとても楽しいです。

あと、転職したことで副業も始めました。自分の裁量で好きなだけ仕事するのってなんか良いですね。無理しない程度にがんばりたい。

趣味

このアカウントではあまり今まで喋ってきてませんでしたが、合唱をずっとやってます。正確に言うと院生のときに競プロを優先したくて一旦やめて、社会人になってから再開してます。今も休日夜に練習に行ってます（それもあって AtCoder のコンテストにあまり出られない）

まだ社会人になって数年とかですが、良い意味でこの縁は一生続くだろうとつくづく思います。来年も本番がいくつかあるので楽しんでいきたい。

来年の目標

  • AtCoder ヒューリスティックで黄色になる
    • これ去年も書いてました。そもそも今年は AHC に 4 回しか参加できてないので、もうちょい参加回数を増やしたいです。精進してまともに参加したらいけるかも・・・！
  • JAG でもっと貢献
    • 作問のほうでもっと手を動かせればいいかな・・・。今年参加したイベントは来年も全部出る予定なので、またよろしくおねがいします。
  • データベーススペシャリストを取る
    • 午前Ⅰの免除がきくのが来年までなので、だいぶ取りたい。
  • 技術書を読む
    • 今年はちまちま技術書が読んでましたが、来年も自己研鑽は積んでいきたいね。

よいお年を〜

HTTF 2024 (AHC027) 参加記

AtCoder 競プロ (マラソン)

HTTF 2024 (AHC027) に参加しました。最終順位は 71 位でした。コンテストを通して焼きなましを初めてフル活用したので、いろいろ振り返りをしていきます。

問題はこちらです。

atcoder.jp

最終的な解法

超かんたんに説明すると、こういう解法でやりました。

  • 左手法で壁を伝う + 左手法で通らなかったところを DFS して初期解を作る
  • 初期解に対して時間いっぱい焼きなまし

seed = 0, score = 1516668

最終提出はこちらです。

atcoder.jp

左手法で壁を伝うだけでは、当然中のセルが埋まっていかないので、そこは DFS で埋めて初期解としました。DFS で全セルに訪問したら即座に帰るようにはしましたが、それ以外はサンプルの方法と同じです（ここどうにかしたかった・・・）

焼きなましについては、もういろいろ頑張りました。最終的に採用された近傍は以下のとおりです。

  1. 経路の挿入
    • 汚れやすさが大きいエリアに出張して戻ってくるイメージで、新しく経路を追加する
  2. 経路の削除と追加
    • ランダムに経路を削除した後、削除されたことで一度も訪れなくなったセルに少なくとも 1 回は訪れるように、経路を追加する
  3. 経路の削除のみ
    • 削除しても全セルを訪れている場合に対応
  4. 経路スワップ
    • 経路が overlap しないように気をつけながら、セル c_1 から c_2 までの経路を 2 つ選んで、その 2 つを入れ替える。
  5. 経路移動
    • セル c_1 から c_2 までの経路を任意の位置に移動させる
    • 移動させた経路については、元いた場所を通過させるように使うので、移動先の時刻で訪れているセルを p とおくと、 p から c_1 までの経路と、 c_2 から p までの経路も追加される。
  6. 隣接スワップ
    • 操作列（LRUD からなる列）で隣接している 2 文字を入れ替える
    • 種類の異なる 2 文字をスワップするとき、訪れなくなるセル・新たに訪れるセルが必ず 1 つずつできて他は（訪問時刻の意味でも）変わらないので、スコアの差分計算ができる

スコアの更新頻度が高かった近傍は 2 番, 4 番, 6 番 です。特に隣接スワップはコストの差分が O(\log L) *1 かつ戻すのも楽なのでかなりイテレーションが稼げました。

1 番, 3 番, 5 番は、スコアの更新頻度が少ない（特に 1 番は序盤しか効かない）ものの、無くすとスコアは悪化してしまいます。状態を大きく変えるのが偉いのかなぁと思っています。

左手法・初期解・焼きなまし後のビジュアライズ結果

すべて seed = 4 の結果です。

左手法 (score: invalid)

壁をつたっているだけなので、これではそもそも正解できません。

初期解 (score: 14355524)

左手法で壁をつたっていた解に対して肉付けが行われていることがわかります。

記事をかいてて思ったけど、この初期解あんまりよくないね・・・もっと良い作り方ができればよかったけど、わからなかった。

焼きなまし後 (score: 8066790)

焼きなましでけっこう改善します。焼きなましすごい。

良かった点

  • 焼きなましをフル活用できた
    • 今まで貪欲ばっかりやってて、あまり焼きなましまでたどり着けたことがなかったんですが、今回はしっかり使えたのでよかったです。
  • 隣接スワップを思いついた
    • 終了前日に思いついて、実装したら順位が 40 個くらい上がりました！その日は 10 時間くらい何も進捗がなくて心が折れかけてたんですが、最後に改善できて本当にうれしかったです。やっぱり軽い近傍は考えるべきだなあ。
  • 1000 ケースを回して、 N ごとに結果を比較して良し悪しを判断できた
    • 毎回やってることではあるんですが、たくさんのケースで比較するようにしています。コンテストの順位は相対評価スコアで決まるので、前の結果を s_p、今の結果を s_c としたとき、 \log\left( \frac{s_p}{s_c} \right) の正負を見て良し悪しを判断していました。こうすると N が違ってもそこそこ似た指標で比較できると思っています。

反省点

  • 初期解はもう少しいい感じに求めたかった
    • 解説放送や感想戦を見ていると、まだ訪れてことがない地点までの最短経路で辿る人が多いみたい？それはコンテスト中に試せるべきだった（コンテスト中には思い浮かんでいなかったんですが）
  • ある地点から 1 周している経路をひっくり返す近傍は思いつきたかった
    • 下のスライドで「操作 2」として紹介されている近傍のことです。

  • もっと良い（速い？）近傍を思いつきたかった
    • 最終提出であっても Time Limit を 5 倍とかにすると有意にスコアが良くなるので、時間内に良い解にたどり着いてない感じでした。こういうときは効率の良い近傍にするか速くするかのどっちかしかないと思うので、そこの引き出しをもっと増やしていきたい気持ちです。

ちょっとずつ AHC の勘所がつかめてきたかな？という感じです。とはいえ初期解とか細かいところとか、まだまだ粗い部分もあるので、そこがもっと詰められるようになりたいところ。次もがんばります！

*1:より詳しくいうと、スワップによって新たに訪れるセル・訪れなくなるセルの訪問回数をそれぞれ n_1, n_2 としたときに O(\log n_1 + \log n_2) くらいになっていて、 n は小さいのでかなり軽い