## はじめに

※ ↓ 元の記事 ↓

[元の記事](https://zenn.dev/through/articles/ebe77ac5d02f2d)

この度、強化学習によるテトリスの AI を作成してみました。想像以上にうまくいき、最終的には半永久的にラインを消してくれる AI に成長してくれたので、今回はその記録として AI を作成した過程をここに記していきます！

## 今回の AI の概要

今回作成したテトリス AI の概要は以下の通りです。

1. 特定のゲームの状態から可能な行動パターンを全てシミュレーションする
2. 行動後の状態を入力情報として **Neural Network** に**今後の報酬の期待値**を推測させる
3. 今後の報酬の期待値が一番高くなる行動を実際の行動として選択して遷移する (貪欲方策)
4. Game Over になるまで 1 ~ 3 を繰り返す

![](structure_img.png)
*Tetris AI を可視化した図*

何も知らない頃は『AI ってどうやって動いてるんだ？』と自分は思っていたんですが、動作原理は非常にシンプルです。強化学習とは、この今後の報酬の期待値を推測する Neural Network を作成する部分に値します。

## テトリス環境の作成

テトリス環境の用意の仕方は主に以下の 3 種類で検討しました。

1. テトリス環境を自作して Gym 化させる
   - メリット：ルールや仕様を独自に変更できる
   - デメリット：作成に少し時間がかかる
2. 本家テトリスをキャプチャする
   - メリット：本家準拠の本格的なAI作成が出来る
   - デメリット：キャプチャする環境準備が大変
3. 既存の Gymnasium のテトリス環境を使う
   - メリット：楽
   - デメリット：カスタマイズ性が少ない

[gymnasium](https://gymnasium.farama.org/environments/atari/tetris/)

Gym とは、機械学習の環境を提供するオープンソースのプラットフォームのことです。自分の作成した環境を Gym に準拠して作成することでより簡潔に機械学習が出来るようになります。

それぞれにメリット・デメリットがあると思いますが、『ルールや仕様を独自に変更できる』が決定打になり、今回は **自作のテトリス環境** を用意しました。ターミナルで動く単純なテトリスを作成した為、そこまで時間はかかりませんでした。また作るのがシンプルに面白かったので結果的に良かったです。テトリス環境の仕様は以下のように設定しました。

**スコアリング**
- ミノを設置する毎にスコアが $+1$ 点
- ライン消去による追加スコア：
  - 1ライン：$+100$ 点
  - 2ライン：$+300$ 点
  - 3ライン：$+500$ 点
  - 4ライン（テトリス）：$+800$ 点

**行動集合**
- 1 回の行動：「回転 → 横移動 → ハードドロップ」 または 「ホールド」
- 定義：
  - $Action(a, b)$：ミノを $y$ 軸方向（横方向）の座標 $a$ に移動し、時計回りに $b$ 回 90° 回転
  - 行動集合 $A$：$A$ $=$ $\{Action(x,y)$ $\mid$ $x \in [-2, 8],$ $y \in [0, 3]\}$

今回の自作環境では各ミノを行列で管理しており、Iミノの場合は $4×4$, Oミノの場合は $2×2$, それ以外は $3×3$ で表現をし、行列の左上を現在のミノの位置と定義しています。またフィールドサイズは本家に準拠して、$(Height, Width) = (20, 10)$ としています。そのため、下記画像の様に $[-2,8]$ にミノが存在することがあります。

![](range_of_motion.png)
*ミノの可動域の左端・右端のケース*

実装初期は一般的なテトリスと同じく「回転」or 「横・下移動」 or 「ハードドロップ」 or 「ホールド」としていたのですが、これだと回転や左右移動による **無駄なループ** が発生してしまうケースが多々あり、学習がなかなかうまく進みませんでした。その為、回転と横移動とハードドロップの 1 セットを 1 つの行動の候補としました。また今回の行動だと最後がハードドロップで終了する為 Spin 系統の技は入っていません。

![](inf_loop.png)
*横移動や回転により起こってしまう無限ループ*

よって（横移動）×（回転）×（ハードドロップ）+ ホールド が全行動パターンになり、今回の行動パターンとしては場面によって最大で $(8-(-2)+1)$ $× 4$ $× 1$ $+ 1$ $=$ $45$ 通りを考慮しています。

## Neural Network の Model と学習

今回用いた Model の詳細は以下の通りになっています。

- $Input(14)$ $\rightarrow$ $Dense(64)$ $\rightarrow$ $Dense(128)$ $\rightarrow$ $Dense(64)$ $\rightarrow$ $Output(1)$
- 損失関数：Mean Squared Error (平均二乗誤差)
- 最適化アルゴリズム：Adam (学習率 $lr = 0.001$)
- 割引率：$discount = 0.99$
- 学習時の行動選択：$\epsilon - greedy$
    - $\epsilon_{start} = 1.000$
    - $\epsilon$ の減衰率 $\epsilon_{decay} = 0.995$ (指数減衰)
    - $\epsilon$ の最小値 $\epsilon_{min} = 0.05$

### 一般的な Deep-Q-Network との違い

深層強化学習と言えば、一番最初に出てくるのはおそらく Deep-Q-Network でしょう。（以降 DQN と呼びます。ドキュンではないです。）今回の NN は一般的な DQN とは違っていて以下の図のようになっています。一般的な DQN は現在の状態を入力として **全ての行動の行動価値** を求める為、その出力の中で行動価値が一番高い行動がそのモデルが示す最適な行動であると推測できます。

ただ今回の自分の NN は、ある状態から **今後の報酬の期待値** を求めるモデルになっています。そのため今の状態から可能な行動を列挙し、その行動後の各状態をモデルに通して今後の報酬の期待値を求めるということをします。そしてその中で期待値が一番高い行動がそのモデルが示す最適な行動ということになります。

![](DQN_NN.png)
*一般的な DQN と今回の NN の違い*

当初は DQN を作成しようとしたのですが何故か上手くいきませんでした。（実装ミスなのかモデルが単純すぎたのか、はたまた行動集合の定義が良くなかったのか…）そのためモデルで求めるものを汎化して、「全ての行動の行動価値」ではなく「今後の報酬の期待値」として学習させてみたところうまくいったので、このモデルを採用しました。

ただし理論上 DQN はできるはずなので、今後も色々実験して試していこうと思っています。

### 層の深さの設定

初めは 128 ⇒ 64 の 2 層のネットワークを使用して学習をしていましたが、これだとラインを全然消してくれませんでした。そこで 64 ⇒ 64 ⇒ 32 の 3 層のネットワークに変更したところ、ラインを消してくれる AI まで成長してくれました。

この 2 つのネットワークを考えると、前者のネットワークが持つパラメータの数は $8254$ 個であるのに対し、後者のネットワークは $6176$ 個とパラメータの数は 75 % 程になっているのに精度は圧倒的に後者の方が良かったので、層を深くすることで表現能力が大幅に上がるということを体感しました。

最終的には表現能力には多少の余裕を持たせた方がよいと考え、層を広くして 64 ⇒ 128 ⇒ 64 の 3 層にしています。

### パラメータ更新（TD誤差）

パラメータの更新は TD 誤差を用いた更新式を用いています。今回類推する時刻 $t$ の状態価値を $V^{\pi}(s_t)$、行動後の即時報酬 $r_t$、割引率 $\gamma$ として以下の様になります。

$$V^{\pi}(s_t) \leftarrow (1 - \alpha)V^{\pi}(s_t) + \alpha(r_t + \gamma V^{\pi}(s_{t+1}))$$

TD 誤差を初めて聞いたという方は以下の記事が分かり易いので是非見てみてください。

[DQN](https://qiita.com/icoxfog417/items/242439ecd1a477ece312)

## より賢く学習をさせる

### 入力を盤面特徴量に変更

以前のモデルでは、盤面の情報（各セルに配置されたブロックの種類を示す配列を1次元化したもの）と、ネクストミノとホールドミノの種類を連結した配列を入力として使用していました。しかしこの入力情報だと現実的にはまず起こり得ない盤面の情報も考慮されており、冗長な部分が多く含まれています。よって学習の安定性を確保するために、入力情報は今後の報酬の期待値を適切に推定するのに必要な盤面の特徴量に絞って使用します。

今回の学習で用いた盤面の特徴量は以下の通りにしています。

1. 各空マスにおける自身より上部にあるブロックの総和（hole_count）
2. 直近でライン消しをしたミノの設置高さ（latest_clear_mino_heght）
3. 横方向に空マスとブロックマスが隣合う箇所の総数（row_transitions）
4. 縦方向に空マスとブロックマスが隣合う箇所の総数（column_transitions）
5. 隣り合う列の最も高いブロックの差の総和（bumpiness）
6. 左右が空マスのブロックマスが $k$ 連続続く時の $\sum{\frac{k(k+1)}{2}}$（cumulative_wells）
7. 中央 4 列のうちの最大の高さ（center_max_height）
8. 各列の最も高いブロックの高さの総和（aggregate_height）

この 8 つの特徴量に加えて、ネクストミノ 3 つ + ホールドミノの種類の番号を入力として学習を行いました。

### 経験再生 (Experience Replay)

経験再生とは、過去のシミュレーションデータを経験バッファ（Experience Buffer）に蓄積しておき、このデータからいくつかのデータを抽出してモデルを学習する手法です。経験再生は方策オフ（off-policy）の学習手法であり、この性質によって以下のような利点が生まれます。

#### 方策オフ学習の利点

方策オフ学習では、エージェントの行動ポリシー（方策）と収集されたデータの関連性がなく、シミュレーションとは独立して学習が行われます。この性質により、経験再生では次のような利点があります。

- **過去のデータの再利用**：方策オフの性質により、経験再生では過去の経験をメモリに蓄積し、効率的に再利用することができます。これにより、データの再利用率が高まり、学習効率が向上します。
- **データの時系列要素の低減**：シミュレーションデータをバッファに蓄積してランダムにサンプリングするため、経験再生では時系列な要素が低減されます。このことが過学習のリスクを減少させ、学習の安定性を向上させます。

ただこのままだとラインはよく消してくれるものの、下部でラインを消していくことを学習するより前に、上部だけでも十分にラインを消せることを学習してまう現象が起こります。そして上部だけで解決できるようになるとバッファに溜まる学習データも上部のものが増えてきて、一気に過学習が進んでしまいます。

このような学習データが学習進度によって偏ってしまう現象を防ぐべく、経験バッファを **画面上部・下部の二つ** で持って、上部と下部から同じ数だけデータをランダムサンプリングして、それらを合わせたデータを 1 つのバッチとしてバッチ学習をさせました。すると画面下部と上部がうまく連結され、安定してラインを消してくれる AI が作成出来ました。gif ではそもそも高く積まれることが少ないですが、実際に高く積まれたときでも安定して画面下部まで戻ってくることが可能です。

![](NN7.gif)
*最終的なテトリス AI のシミュレーション*

## 番外編（火力の高い AI を作る）

番外編として、生き延びる AI とは別で火力の高い（スコア効率の良い）AI も作ってみたいなと思ったので作ってみました。ここまでで作成した AI もそこそこスコア効率が良いですが、もう少し工夫して 3・4 Line 消しの頻度が増えるようにしてみました。まだまだ改善途中なのですが、やったことはざっくりいうと下記になります。

- 3・4 Line 消しの学習データを経験バッファに長居させる
- 積み込みが綺麗であるほど追加報酬を入れて Fine-Turning 
- 3・4 Line 消しが出来る場合は優先的に行う

1, 2 つ目は3・4 Line 消しの頻度を高めるべく、積み込みがうまくいくようにするために設定しています。また 3 つ目は生存率を高めるためにやっています。火力の高い AI は一度に多くのラインを消す都合上、ミノを溜め込んでしまう傾向があります。積み込みは凄く綺麗にできても積みすぎてゲームオーバーになってしまう悲しい AI になってしまうのを防ぐべく、適度に 3・4 Line 消しを消費することで事故を起きにくくしています。
（※ 下記の gif は積み込みがある方が映えるため 3・4 Line 消しの頻度を少な目にしています）

ただ、ミノの来る順番によってはかみ合わずに、積み込みがうまくいかずにゲームオーバーになってしまうことがそこそこあります。生存の長さとしては、先ほどの半永久的にラインを消してくれる AI は 100,000 ラインは優に超えてきますが、この AI は現状だと平均 30,000 Line ほどでゲームオーバーになってしまうため、まだ改良は必要そうです。

![](Extra.gif)
*火力の高い AI のシミュレーション（見た目はすごく良い）*

## 終わりに

[tweet](https://x.com/through__TH__/status/1770449883453083797)

今回の学習の経過を X（旧Twitter）に乗せていたのですが、改めてみるとしっかり成長している過程が見えてとても良いです。今回記事を書いてる際に、情報が整理できて改善点や今後やりたいことが続々出てきたので、時間がある時にやってみようかなと思っています。（うまくいったら記事を更新するかも？）

- 設置個所を全探索して行動パターンを生成することで Spin にも対応する
- DQN や SAC のような他のアルゴリズムでも AI を作成してみる
- 使用する特徴量の相関分析をして入力の質を高める
- 1 操作当たりの時間制限を用いてヒューリスティック的な手法で AI を作成して比較してみる
- フィールドの大きさ・形・出現ミノ等を変更したり、対戦ルールに発展させたりする

今回の開発は松尾研主催の RL Spring Seminer 2024 の課題として、友人 2 人含め 3 人 （@through__TH__, @sor4chi, @solehamugoiyo3）で開発をしました。

[ソースコード](https://github.com/seihirochi/tetris-project)

ずっと手を出せていなかった機械学習に手を出せた良い機会になったので楽しかったです。テトリス AI はゲーム AI の題材として扱いやすいと感じたので、みなさんも是非作ってみてください！


Neural Network を用いた深層強化学習

強化学習でテトリス AI 作成

## 2023 年の振り替えり
2023 年は今までで一番過ぎるのが早く感じていて、もうジャネーの法則を凄く感じる年でした。今年もあと 10 時間を切ったということで、2023 年度やったことを思い出しながら適当につらつら書き上げていきます。
大きいことからどうでもいいことまで書いていきます。

### プログラミング系統

- この Portfolio サイトを作る
- Future のインターンに参加
- Future で継続開発バイト
- Future で内々定を貰う
- ISUCON に参戦する
- Maximum-Cup にて色々な競プロer と知り合いになる
- 他にもオンサイトコンテストに参加する (MMA Contest や TTPC2023)
- AtCoder Algorithm 入青
- AtCoder Heuristic 入黄

### 日常系統

- 成人式
- 中学の部活・高校3年のクラスでの同窓会
- Maximum に web 研が正式に追加され活動が活発になる
- デスク環境が整備される (デュアルモニター,モニターライト,webカメラとか)
- 5 年使ってた Motorola G7 Plus を Google Pixel 7A に変えてサクサクになる
- 時計を集めてる人の気持ちが分かるようになる
- Pokemon Sleep にドはまりする
- 積み立て NISA を始める

## 来年の抱負

- 大学院 or 就職 を選ぶ
- AtCoder Algorithm 入黄
- AtCoder Heuristic 入橙
- CodeForces 入紫
- ICPC Regional 出場
- Kaggle で Expart になる

## まとめ
文字に起こしてみると若干少なく感じるけど、1つ1つが大き目な出来事で面白い一年でした。選択によっては大学生活最後の 1 年になるかもしれないので 2024 年はもっと面白いことをしていく！

ps : 2024.05.07
大学院に進学することになったので、自分のやりたいこと（数理最適化や機械学習関連）を突き詰めて技術力を向上させる1年にしていく！

2023年の出来事の軽いまとめ記事

2023年度総決算

## はじめに
こんにちは、through です。

先日行われた AHC029 にて Heuristic で黄色になりました！Algorithm ではなく Heuristic ではありますが、晴れてずっとなりたかった暖色コーダーを名乗ることが出来るようになりました。つい最近 Algorithm の方で入青を達したばかり (今は水色に落ちてしまいましたが…) で、2023年終盤に色変を 2 回も出来てとても嬉しい限りです。

[tweet](https://x.com/through__TH__/status/1739784842961965374?s=20)

![](jwxybxe7ro3k3brmrxbu)
*入黄に至るまでのレート遷移*

Heuristic 初参加は 2021.12.12 の AHC007 で、競技プログラミングを始めて 2 週間足らずの競技プログラミングを始めたての時だったようです。当時は AHC の問題を AC することすら出来ませんでした…。ただその次の 2022.02.26 の AHC008 にて青 performance を獲得することが出来、AHC にハマっていきました。

成績表を見たところ、自分の AHC の parformance 上位 5 位は全て 2023 年に参加したコンテストでした。きちんと実装力が上がっているのが垣間見えて嬉しいです。

![](yypizumrm2jxagdvobse)
*performance 順の成績表の図*

以下では、記録として黄色になるまでにしたこと、今後したい事、Heuristic の楽しいと思うところをさらしていこうと思います。

## 黄色になるまでにしたこと・感じたこと
自分が黄色になるまでにしたことは、**時間リソースを使った手法の習得** です。

Heuristic の問題は、厳密解を求めることが出来ない問題において、条件に相応しい解法を出した人の勝ちです。その為実行制限時間内であれば出来るだけイテレーションを回して、良い解を探索するのが自明で良いです。

実際に自分が習得した時間リソースを使った手法は以下の 3 つです。

- 焼きなまし法
- ビームサーチ
- モンテカルロ法

これらが習得出来れば殆どの問題で戦うことが時間リソースを使って戦うことが出来るようになると思います。習得したと言っても練度は上位の方より遥かに劣るので、橙色になるには問題に相応しい応用の仕方を会得する必要があると痛感しています。

しかしこれらを習得しないと Heuristic で戦えないのか、というとそうでもないです。これらのアルゴリズムを知らなくても、問題の核を得たルールベースの解法を実装するだけで黄色や橙色になることは出来ると思います。実際に自分は AHC026 で的を得たルールベース解を作成しただけで黄色後半 perf を取得することが出来ました。

よって、Heuristic において結局一番大切なのは、**問題における重要な要素の考察** だと感じます。実際に頑張って時間リソースを使った手法でシミュレーション出来ても、いざ感想戦になると上位の方のルールベースに完敗することが多々あります (悲しい) 。ヒューリスティックで黄色を目指すにはこういった新たな手法を習得するよりも、まず上位の方の思考プロセスを学ぶのが意外と近道かもしれません。

### 焼きなまし法がうまくいかない時の考察

個人的には焼きなまし法が好きで、習得したものの中では得意です。実際のコンテストで一番成績が良かった MCDigital プログラミングコンテスト2023 (AHC019) では焼きなまし法で 37 位になり 順位表 2 ページ目に入ることが出来ました。上位の実力者の方には全く及ばないですが、今自分が焼きなまし法を実装する時に心がけていることを記そうと思います。

それは **近傍・評価関数・初期解・焼きなましの温度の対応を想像する** ことです。

そもそも焼きなまし法のベースに山登り法というものがあります。これは現在の解から少しずらした近傍を求めて、現在の解より近傍の評価値が良い時にその近傍に移る、という操作を時間一杯行う手法です。焼きなまし法はこの近傍に移る条件を緩和させて、評価値が良くない時でも確率的に遷移を許すことで多様性を確保しようという手法になります。

自分の場合、山登り法を実装した後に焼きなまし法に移すとスコアが落ちる or 変わらない ということが頻繁に起きます。経験的にこれは近傍・評価関数・初期解・焼きなましの温度等、それぞれ単体で良い案だったとしても対応関係が良くないです。近傍が大きすぎると焼きなました時にブレブレの解に変貌し、近傍が小さいと局所解にハマって結局山登りとスコアが変わらない、という風なことが起きます。

なので自分が焼きなまし法をする時はこれらの対応を頭の中で想像して考察を進めています。簡単な例で示してみます。例えば以下の評価関数があり、小さめな近傍で山登り法をすることを考えます。

![](ej4uy509fycatxg9krws)

ここで赤点から評価関数が高い方向に遷移する山登り法を実装すると以下になりそうです。

![](uaw9oolctjjjild3isnm)

ただ右の山の方が高いのでそっちに行きたくなります。そこで右の山に移るようにするために、焼きなまし法にして良くない方向への遷移を許すと、以下の様になりそうなのが想像出来ます。

![](ir84h6shz1if8xilparo)

ただここで、以下のようなことが懸念されます。
- 焼きなまし法の良くない方向への採用確率が高すぎたり、近傍を大きく取りすぎたりして、**一回右の山に移ったのにまた左の山に戻ってきてしまうことが多い** 
- 焼きなまし法の採用確率が低すぎて、**そもそも一回も右の山に移れてない**
- 評価関数の緩急が激しい・局所解が多すぎる等の原因で、**遷移がうまく進まない**
- 初期解 (最初の赤点) がはるか遠くの離れたところにあり、変な場所でスタックしている (**初期解が雑過ぎるとそもそも山登り法すらうまくいかない時がある**)

こういうことが起きないように適切な近傍・評価関数・焼きなましの温度の対応が重要だと思っています。実際の評価関数や近傍は例のような簡単な関数では表せず複雑なので、具体的に想像することは難しいです。しかし焼きなまし法がうまくいかない時は、根底にこれに似た現象が起こっている可能性があるという推測が必要だと思っています。自分は大まかにこういう想像をして、出来るだけ評価関数の最高地点に到達する為にはどういう近傍や評価関数等が必要かを考えて調整するとうまくいくことが多いです。

「焼きなまし法が全然出来ない…」という方はこういう意識をするとうまくいくことがあるかもしれません。

## 今後したいなと思った事
### クラウド上でのテスト並列実行
自分はテストケースを回す時、ローカル環境で適当にシェルスクリプトを書いて 20 ~ 30 分かけて数百ケースを回すというとても非効率なやり方で行っています。しかもローカルの処理性能がジャッジ時の性能より遥かに劣るので提出したらスコアが想定より上下することが多く結構戸惑います。クラウド上でテストを回すと数千ケースが数十秒ほどで終わるらしいので、今後橙色を目指すうえでやっておくべきかなと思います。

### Optuna を用いたハイパーパラメータ最適化
現在は手動でお気持ちパラメータ調整をしています。これはダメですね…。世には便利な Optuna というハイパーパラメータを効率よく探索してくれるフレームワークがあるので、今後はこれを利用して空き時間にパラメータ調整を行うようににしたいと思いました。

[Optuna](https://optuna.org/)

## Heuristic のどこが楽しい？
自分は競技プログラミングを始めてからほとんどの Heuristic のコンテストに参加していますが、何が楽しくてハマったのかをまとめてみました。

### ビジュアライザ
Heuristic と言ったらビジュアライザです。最近の問題では自分の解法を視覚的に見ることが出来るビジュアライザを問題と一緒に提供してくれているので、気軽に自分のプログラムの挙動を確認することが出来ます。特に web 版のビジュアライザは多機能 & 使い方が簡単で、自分がプログラムを作ってその出力を張り付けるだけです。ビジュアライザを見て想定通りの挙動を示してくれた時の楽しさはひとしおです。上位の方はよくコンテスト中に自作している方がいて、いつかは自分も自作ビジュアライザを作ってみたいなーと思っています。

個人的には Seed = 0 の結果だけ共有 OK というルールの時のコンテストがとても楽しかったので、またそういうコンテストが生えることを祈っています。

### 感想戦・公式解説放送
Heuristic のコンテストが終わると、X のタイムラインで色々な方が解法を出し合う感想戦が活発になります。Heuristic は自由度が高いコンテストであるが故に、人それぞれの解法があって他の方の考察を見るのがとても楽しく、色々な気付きがあります。

また公式解説放送では思考の順を追って説明してくれたり、度肝を抜く解法を解説してくれたりします。特に印象深いのは以下の AHC016 の解説放送で、実際にこの放送を見られた方は満場一致で度肝を抜かれたと思います。楽しいです。

[tweet](https://x.com/atcoder/status/1594273142746550273?s=20)

### 誰でも参加記を書いて解説に残せる
通常 Algorithm のコンテストでは解説の作成にレートの条件が課されています。例えば AtCoder Beginner Contest ではレートが 2000 以上にならないと解説作成が出来ないようになっています。

しかし AtCoder Heuristic Contest の場合はレートの制限が一切なく、様々な順位帯の参加者の記事を見て考察を知ることが出来るので凄く面白いです。是非皆さん参加記を書いて下さい！(他の人の参加記を沢山読みたい人)

![](spqhg77wwomdpstulerx)
*誰でも解説作成が出来、色々な人の参加記事を見ることが出来る*

### スポンサーからのグッズや景品
他のコンテスト同様に、企業さんがスポンサーをしているコンテストの場合は大体順位に応じてグッズや賞金が用意されています。そして Heuristic は参加人数が少ないこともあり、それらを取得出来る可能性が他のコンテストより遥かに高いです。

通常自分のレベル帯では、賞金やグッズは一度も取得出来てなくてもおかしくないですが、Heuristic のおかげで今まででグッズや賞金をそこそこ頂いています。嬉しい限りです。景品は T シャツとかタオルとか、Algorithm コンテストではあまり提供されないものもあります。競プロer が集まる場でこういうコンテストの景品を持っていくと結構うけます。

[tweet](https://x.com/through__TH__/status/1571000385359454209?s=20)

## 終わりに
数理最適化とか、機械学習とかを大学で研究しているぐらい強くないと黄色にはなれないんだろうなーと 1 年前に入青した時点では思っていましたが、結果的にそんなことはなく、無事黄色になることが出来ました。とても嬉しいです！

個人的には貪欲法を突き詰めるより、コンピュータの計算能力を活かしたシミュレーション、期待値計算等によって自分の想定を超える挙動を示した時に『Heuristic 最高！』となります。Algorithm とは違った嬉しさが込み上げてくるので、Heuristic に抵抗がある方も一度自身の考察をプログラムに起こせるまで粘って参加してみてください。

次は橙色ですが、ここからは流石に何か尖った武器が無いと修羅の道になりそうです。しかし Heuristic は単調非現象型のレートシステムなので、少しづつ上げていつかは橙に届くように精進していこうと思います！

ここまで読んでくださりありがとうございました！

Heuristic で黄色（上位約4%）到達

AHC入黄色変記事

## はじめに

※ ↓ 元の記事 ↓

[元の記事](https://zenn.dev/through/articles/fba81b6c5f4644)

どうも、青コーダーの through です。(言いたかっただけ)

先日行われた ABC330 にて青色になることが出来ました！2021.11.27 がコンテスト初参加なので約2年かかりました。長かった…。記録として初の色変記事 兼 ここまでの振り返りを書いていこうと思います！

![](tmlp1lxrojc99idrqsvt)
*現在に至るまでのレートの推移*

初めての Contest 参加から ABC が 102回 (ABC229 ~ ABC330) 、ARC が38回 (ARC131 ~ ARC168) 開催されていたようですが、自分はそのうち Unrated を含めて ABCに98回、ARCに36回参加していたようです。

ここ2年でのABC, ARCのコンテスト参加率は、**95.7142...% (134/140)** でした。
正直こんな参加していたとは自分でも驚きです。

そして AtCoder 社長の chokudai氏のブログによると…
> 青は超優秀です。学生時代を競技プログラミングに注ぎ込んでも、ここにたどり着けない学生は大量にいます。競技プログラミング未経験者では、このレベルと競技プログラミングで戦うことは殆どの場合は無理です。8割以上のIT企業において、アルゴリズム力はカンストです。一部企業においては、少し持て余してしまうかもしれません。

らしいです。ようやく超優秀になれました。これは嬉しい。

[直大さんの Blog](https://chokudai.hatenablog.com/entry/2019/02/11/155904)

## 自己紹介
- 名前 : through
- 所属 : 地方国立大学3年 情報系学部
- AtCoder歴 : 2021.11.27 ~ (記事公開時でジャスト2年)
- プログラミング歴 : 大学入学 ~
- 競プロ使用言語 : C++
- 現在 (2023.11.27) の精進の様子 ↓ 

![](psrruvlglb159zukc6nl)

![](nfe5me2l6l2taxdpn07g)

![](dpbbuhyvrmjoazjyb0zq)

自分はあんまり『埋める』という意識ではなく、適当に自分用の Virtual Contest を立ててそれをやったり、他の人のバチャコンに参加する感じでやってます。新しい問題を解くと同時に、過去にやった問題も出題される為復習も出来るので個人的に良い方法なのではと思っています。


## 水色 → 青色 になるまでにやったこと

### 1. ABCの水・青diff埋め
自分の適正レート帯を解くという誰もがやる王道です。ただし自分は、自分のレート帯より上位の問題を解いてアドレナリンを出すことをモットーにしているので、競プロを始めたての時から自分の1色上の問題を意識した精進をしています。その為水色のうちは、青diffも結構解いて精進していました。
実際に自分の適性難易度より上の問題が解けた時の喜びはひとしおです。( レートを爆上げして脳汁を解放することに価値を感じる人 )

水diff は Max 20分、青diff は Max 30分まで考えて、一度も手を動かせなかったらその場で解説を見るようにしてました。解説をいつ見ればよいか問題があると思いますが、自分は思いつかなそうと思ったら案外すぐ見てもいいんじゃないかというのが自論です。(勿論希少なコンテストはあまり見ないようにしたりとかはある。)

以下が **AtCoder Type Checker** での自分の評価です。ここから分かる通り、自分は他の水コーダーよりも解くのは遅いが、時折ABC6完・ARC3完をして一気に上げるタイプです。

[AtCoder Type Checker](https://atcoder-type-checker.herokuapp.com/)

![](znr2kqsw83u9eimm2cl8)
*実線より ↑ にあるほど多く解くタイプで、↓ にあるほど早く解くタイプ*

自分の所感なんですが、青になることが目的であれば、青diff を解く必要はあまりない気がします。青diff精進のおかげで、確かに青中上位の成績を取れる確率は上がったのですが、水色の速解が苦手なせいで速解回では中々良い成績が出せず、結局相殺されてかなりの期間停滞してしまいました。その為、**とりあえず青になりたい方は青ではなく水diff精進をおススメします！**
( レート爆上げで脳汁を解放したい方はどんどん青もやりましょう！ )

### 2. AtCoder Library Contest

AtCoder では、よく使う有名なデータ構造のいくつかが ACL (AtCoder Library) として使えるようになっています。個人的に ABC で実際に利用してACの役に立ったのは Modint, DSU, Fenwick Tree, SCC, Segment Tree, Lazy Segment Tree です。この6つが応用出来るのと出来ないとでは天と地の差があると個人的に思ってます。

( Lazy Segment Tree に関しては青相当な気がしますが、たまに公式の想定解法を無視してデータ構造の暴力で解ける時もあるので覚えておいて損なしだと思います )

自分は Convololution や Maxflow 等も履修してみましたが、青になる過程では使いませんでした。まだ応用までは出来ず扱いこなせてはいませんが、アルゴリズム自体はとても面白いので好きです。

[AtCoder Library Contest](https://atcoder.jp/contests/practice2)

### 3. EDPC A~Z (全部)

DP は個人的にアルゴリズムの中で一番好きなのでEDPCを全部解きました。

後半は青になるには不要だと思いますが、どの問題もこんな天才な考え方があるのかと毎回感心します。個人的に競プロを楽しむ上でとてもおススメの問題集なので、まだ最後までやっていない方は是非やってみてください！

個人的に天才pointが高めで好きな問題は、J, R, U, V, Y です。解説を見た時に感動しました。是非解いてみてください！

[EDPC](https://atcoder.jp/contests/dp)

![](ortcwwmblgfxj2ca9lw3)
*EDPC完走のしるし*

### 4. 競プロ典型90問 (~★5, ★6もちょっと)

新しいアルゴリズムの習得や考察の仕方をおさえる上で非常に重宝しました。解説が丁寧 & サンプルコードが付いているので、とても効率的に進められる教材だと思います！

この問題集を作成した方が自分と同学年の方であることを知った時は驚愕しました。素晴らしい教材を提供してくださって有難うございます<(_ _)>

[Typical90](https://atcoder.jp/contests/typical90)

## 競プロの振り返り

### 入灰 (2021.11.27)
AtCoder に出会ったのは 2021年11月 (大学1年の冬) でした。
大学入学するまでプログラミングは未経験でしたが、大学の友人にプログラミングに詳しい人が多く、その波に乗るようにweb系のプログラミングを触っていました。

いつものように Discord で友達と話していた時に AtCoder が話題に上がり、そこで初めて問題を解いたところドはまりしてしまい、いつの間にか競プロの虜になっていました。

というのも、自分は生粋のレーティングゲーム好きで、ポケモンやスプラトゥーン、ぷよぷよ等を結構やっていました。その為「頭を使うパズルレーティングゲーム (競技プログラミング)」 に魅力を感じ沼にハマっていくことになりました。

[tweet](https://twitter.com/through__TH__/status/1464640195312062474?s=20)

### 入茶 (2022.01.29)
初の色変は競プロを初めて2ヶ月くらいの頃で、正直この時期が一番精進していた気がします。冬休みが競プロで潰れた記憶と同時に、初めての色変で競プロコミュニティの方々が凄く祝ってくださりとても嬉しかった記憶が蘇ってきました。

当時これといって趣味と断言出来るほどのものはありませんでしたが、久しぶりに人にも『これに超ハマってる！』と言える程の趣味になりました。

[tweet](https://twitter.com/through__TH__/status/1487430373613387781?s=20)

### 入緑 (2022.04.16)
ちょうど学年が変わる頃に緑色になりました。そしてちょうどこの頃、大学のプログラミングサークルに入会し、初のリアルでの競プロ仲間をgetしました。弊サークルは当時人数が少なくかなり内輪ノリみたいな感じでしたが、競プロの会話が実際に出来るのはとても楽しくて新鮮でした。

[tweet](https://twitter.com/through__TH__/status/1515330601955786753?s=20)

### 入水 (2022.09.05)
夏休み中に入水しました。この頃を思い出そうとしましたが、正直あんまり記憶がありません。普通に夏休みを遊んだりのんびりしたりして満喫していた最中だったと思います。当時は半年後位に入青出来るだろーなーと思っていましたが、鬼の停滞期に入ることを当時は勿論知りませんでした。恐ろしい…。

[tweet](https://twitter.com/through__TH__/status/1566453545465163777?s=20)

### 待ちに待った入青 (2023.11.25)
待ちに待った入青はなんと前回の色変から 1年と2ヶ月もかかってしまいました。入っていたサークルでは上級生になり教える立場になったり、院進 or 就職を考えなければいけない時期になったりと時代の流れを感じますねー。(おじさん思想)　色変というものを忘れていましたが、実際に久しぶりに色変して、やっぱ色変は最高だなと改めて思いました。

X の競プロコミュニティはかなりあたたかく、色変はいつも多くの方々が祝ってくれます。控えめにいって最高です。お祝いリプ・いいねをくださった方々、ありがとうございます！！

[tweet](https://twitter.com/through__TH__/status/1728416471829872690?s=20)

## おわりに
ようやく長い間目標にしていた青色コーダーになることが出来てとても嬉しいです。『目標達成！』で終わる訳もなく、次の新しい目標に向けてどんどん精進していく所存です。

次の目標は「**学部生のうちに黄色になる**」ことです！

水色 ⇒ 青色になるのに 1年2ヵ月 と想像以上に時間がかかってしまいましたが、この目標を達成出来るようにこれからも自分のペースで精進を続けていきたいと思います！

ここまで読んでくださりありがとうございました！


2年かけてAtCoder青色になった話

## はじめに
through です。この度 トヨタ自動車プログラミングコンテスト2023#6（AHC026）にて、好成績を収める事が出来たので参加記を書きます！

結果　:　**1,399,432点　41位/789位** 

performance は **2329** で黄perf でした！

[成績表](https://atcoder.jp/users/through/history/share/ahc026)

自分は短期コンが大の苦手で、AHC026 以前での短期コンでの最高perfは水色だったので良い成績を取れて凄い嬉しいです。

## 問題概要
N(=200) 個の箱があり、初めは 20 個の箱が詰まれた山が M(=10) 個ある。各箱には 1~200 の数が振られているので、以下の操作を行い、**出来るだけ体力を温存するように**全ての箱を 箱1 から番号順に運び出してね。

1. 箱X とそれより上にある箱を、体力 (運ぶ箱の数+1) を消費して他の山に移動する。
3. 箱X が山の頂上にある時、体力消費無しで運び出す。

[AHC026問題](https://atcoder.jp/contests/ahc026/tasks/ahc026_a)

## 解法概要
各山を頂上から見て昇順になるようにソートされた状態にする貪欲です。
全ての山がソートされている盤面は必ず体力消費0で全ての箱を運び出すことが出来る為、勝利を意味します。

山のソートの仕方は以下の通りで行いました。

1. ソートしたい山の頂上から番号が単調減少な部分を取り出して他の山へ退避する。
2. 1 を山に箱が無くなるまで繰り返す。
3. 他の山に移した箱で山の頂上にあるもののうち、最大の番号の箱から元の山に戻す。

他の山に、単調減少を崩さずに移しておくことで、3の戻すという操作のみでソートが完了する & 複数の単調減少な部分を運ぶ時に手数が節約出来る という利点がある為この方法で行いました。

単調減少な部分が多数生成されてしまい退避可能な山が無くなるケースがありますが、その時は既に退避したもののうちサイズが一番小さいものとマージする処理を入れました。

![](simulation2)

これだけで本番最終82位 (1,394,313点) が取れます。

これに加えて以下の2つの工夫を入れました。
1. ソートの操作中に今取るべき箱が来た時はその時点で取る。
2. ソートの過程で退避する山は、山の最小要素が最大の山から順に選ぶ。

1 はソート中に運びたい番号があるなら勿論途中で取った方が、ソートすべき箱が減るので自明に体力が温存出来ます。2 は 1を行う上で、他の山がソートされている場合に他の山も巻き込みながら運び出しを進めることが出来る可能性が増えるので取り入れました。

この2つを実装すると 5000点 程上がり、本番最終41位 (1,399,432点) が取れます。

[最終提出](https://atcoder.jp/contests/ahc026/submissions/47306213)

![](simulation)
*Seed=0 Score = 9339*

## 今回の戦い方で良かった点

### 貪欲の考察を突き詰めた

　短期コンテストは時間との闘いがある為、一度間違った方針で時間を使ってしまうと、違う方針で試す時間が必然的に限られてきます。その為、いかに初めに核心に迫った考察を出来るかが重要です。

言葉で言うのは簡単ですが、実際にはそれが結構難しく、過去の短期コンテストでは問題の核心に迫った貪欲を書くだけで青perf~ が取れてしまう回が過去に何度もありました。例えば AHC015 Halloween candy や AHC021 Pyramid Sorting です。

[AHC015 Halloween candy](https://atcoder.jp/contests/ahc015/tasks/ahc015_a)

[AHC021 Pyramid Sorting](https://atcoder.jp/contests/ahc021/tasks/ahc021_a)

過去回の詳細はネタバレになるので省きますが、実際にこれらの回では貪欲を書くだけで、それぞれ 80位程度(2000 perf付近), 156位(1860 perf) を取ることが出来ます。( AHC015 は天才すぎて感動した。 )

実際に今回もソート貪欲の解法だと、雑に書いても最低 1,380,000点 (225位付近 1640 perf) 程度を取ることが出来ます。( 各山のソートは基本的に箱を出す・戻すの2回で完了するので、体力消費は悪くても 200(箱の数) * 2(操作回数) * 2(1回の操作コスト) = 800 程度で済む。 )

自分が今回貪欲を考察する上で、最初に沸いた発想が、『今とるべき番号の箱より上の部分を、最小要素が最大の山の上に退避させて、その番号の箱を取る』 という貪欲方針でした。
この方針だと遠い未来に山の移動を擦り付けられるので良さそうと思いましたが、結局後々の体力の負債になっていると感じた為、妥協せずにもっと良い方針が無いかを探りにいきました。いつもはすぐに乱択ベースな解法に頼ってしまうので、貪欲の考察を突き詰めたのは良かった点だなと思います。

### 実装・改善方針の目途が立つまで手を付けない
 今回は考察が定まっても、実装・実装後の改善方針 等の目途が立つまでは手を一切動かしませんでした。自分が残りの時間ですべきことを洗い出すことで、常に手を動かして無駄な時間を無くすことが出来、またバグを生みそうだなと思っていたソート部分もほとんどバグを生まずに実装出来ました。

## 感想
山登りや焼きなまし、ビームサーチ等の手法を用いずとも上位を取ることが出来、短期ならではの面白さを感じました。X の Timeline の感想戦を見ていると、ビームサーチ解法がとても気になったので時間がある時に実装してみたいと思います。

短期コンで 初の2桁順位 & 黄perf が取れたのでとても満足です！なんと少し諦めかけていた、**Heuristic年内入黄**が目前になったので、今年最後のAHC027にて入黄を果たしたいと思います！

![](iopih9goazwl8wjugeam)
*入黄まであともう少し！！*

AHC026参加記

## はじめに

こんにちは、through です。  
この度 MC Digital プログラミングコンテスト 2023(AHC019)にて、過去最高順位をとることが出来たので、記念に記事を書きたいと思います！

暫定テスト　　:　 **24,477,348,341 点   36 位 / 787 位**  
システムテスト:　**972,132,803,958 点   37 位 / 786 位**

performance は **2315** で初黄 performance でした！
heuristic分野でここまで戦えたのは初めてのなので、記念に記事を残します！

[AHC019 自分の最終提出](https://atcoder.jp/contests/ahc019/submissions/40288129)

## 問題概要

1×1×1 の立方体が接合されて出来たブロックを作成し、正面・右から見た時のシルエットが入力のシルエットと一致するようにブロックを配置する問題。

- 正面・右から見た時の入力シルエットの組は 2 組用意されている。
- 知育玩具としての開発が目的の為、作成するブロックは大きい方が point が高い。
- 各ブロックは両方のシルエットで使われる方が point が高い。

[AHC019問題ページ](https://atcoder.jp/contests/ahc019)

## 解法概要

部分破壊 &amp; 再構築 を行う焼きなまし法です。

### Block インスタンスを作って近傍探索

まず Block class を作成して、メソッドに Block 拡張・Block 縮小メソッドを導入します。
そうすることで簡単にブロックの管理が行えます。

ブロックに有り得る向きは 24 通り(サイコロの置き方と同じ)存在し、同じブロックをシルエット 1 とシルエット 2 の両方で用いる場合、向きが違う場合は伸ばす方向(dx,dy,dz)も異なります。
今回は各ブロックに向きを定義して、それに対応した dx,dy,dz を予め作成することで簡単に同型を保ったまま拡張出来ます。
![ahc_img0](ahc0_apoy3d)
_各ブロック毎に基準のベクトルを決めて z 方向に伸ばしたイメージ図_

### 初期解生成

初期解は以下のように生成しました。

1. 1×1×1 ブロックを両方の空間のランダムな場所に 1 つずつ置く。
2. 2 つのブロックの向きを全探索して最大限まで拡張する。
3. 一番拡張出来た方向を採用して反映する。
4. シルエットが完成するまで 1~3 を繰り返す。

![ahc_img1](ahc1_euz54b)
_試しに Seed = 0 を 1 ブロックだけやってみった結果_
↑ をみて分かるようにランダムな場所に 1×1×1 ブロックを置いて拡張しただけですが、十分に拡張出来ています。今回はまだシルエットが完成していない空間に対してこの方法を繰り返すことで解を生成しました。

コンテスト序盤は『最小限の 1×1×1 ブロックでシルエットを満たす配置を決める → ブロック拡張・合成・削除』という方針を取っていました。しかしブロックの行先が他のブロックに邪魔されていることが多かったり、合成出来るようなブロックペアが中々存在しなかったりして遷移の進み具合が遅かったので却下しました。

行先のブロック削除を実装すれば解決するとも思いましたが、行先が両方のシルエットに使用されているブロックの場合、片方を変更するともう片方にも影響が出てシルエットを満たさなくなる場面を考慮する必要があって大変な為、今回の方針に落ち着きました。

![ahc_img2](ahc2_lkjxey)
_橙方向に伸ばすとグレーブロックが縮んてシルエットが不適になるの図_

### 部分破壊 &amp; 再構築

これは過去の AHC の上位解法から着想を得ました。

ブロックが邪魔で拡張できないケースを出来るだけ少なくするべく、まとまった空間を用意したいと思った為、『ブロックを何個か完全に破壊して、それで出来た空間に対して再度解を構築する』という方針にしました。最終的にはブロックの破壊個数は 1 ~ 3 個の破壊のみに制限して、それぞれ予め自分で決めた確率で何個破壊するかを決めています。

この操作は具体的に、1 ブロック破壊によって『ブロックの移動・変形』、2,3 ブロック破壊によって『ブロックの合成・大きさの均一化』をすることを狙っています。

また複数ブロック破壊する時は、削除後の空間がより自由度の高いものになるように隣接ブロック同士を破壊しました。具体的には 1 つ削除するブロックを選んだ後に、素直な bfs を書いて近場のブロックを削除しています。両方の空間で隣接するブロックのペアがあればそれが最高ですが、なかなかそのケースは無い為ランダムでどちらかの空間を選んで隣接ブロックを破壊しました。

![ahc_img3](ahc3_rxct2a)
_Seed = 19 の状態遷移の一部_

コンテスト序盤は、ブロックが入り組んでいる場合は多くのブロックを破壊する必要があると思てそのような遷移も含ませていました。しかし、乱択性が強すぎてスコア上昇が局所的(上がる時は急上昇するが改善頻度が低い)だったり、シンプルに 1 回当たりの計算が重かったりしてスコアが良くなかったので却下しました。

### 更新が全然来なかったらブロック移動

一定回数以上スコア更新が見込めない場合に、ブロックを若干ずらす処理を加えました。
具体的には、ブロックのペアを 1×1×1 の状態にまで戻して一方のブロックを数ブロック分ずらした後に再度拡張する操作を複数回行う処理を入れました。

スコアをある程度保ちつつ新たな隙間を生成して次につなげたいという発想から実装に至りましたが、思ったよりスコアは上昇しませんでした。

### その他の細々とした調整

- 提出前に拡張出来るか再確認。
- 行・列のブロックの有無を bit で管理して高速化。
- シルエットのブロック数の差が超大きくて解構築が出来なかった激辛ケース用貪欲を用意。

## 提出の変遷

### 必要最低限の 1×1×1 ブロックのみで構成

まず、問題文を見て試してみたくなったことが、「最高効率で 1×1×1 ブロックを敷き詰める」。
ということで、1 つ 1 つのブロックが最小である為スコアは振るわないと思うが、お試しとして提出。他の方々もやりたくなったようで、自分が提出した時は同じ点数が 10 人程いて面白かった。

**暫定テスト：2,699,000,000,000 点**
![ahc_img4](ahc4_w8ufts)
_Seed = 0 の visualizer_
※Seed = 0 : 19,000,000,000 点 , Seed = 19 : 110,000,000,000 点

### 共通部分に着目

1 つ目の提出の visualizer を見ると、自分の実装上斜めに点々に配置された形が多くある。ならばシルエットの組両方に出てくる、斜めの共通部分を繋げていけばコスト削減に繋がりそう。ということで実装。棒状に伸ばして管理するのも思いついたが、殆どスコア上昇が期待出来なかった為断念。
AHC 開始初日はここで幕を閉じる。。

**暫定テスト：1,711,913,901,787 点**
![ahc_img5](ahc5_umskkc)
_Seed = 0 (上), Seed = 19 (下) の visualizer_
※Seed = 0 : 17,666,666,667 点 , Seed = 19 : 53,421,800,422 点

### Block インスタンス作成 &amp; ブロックを最大限拡張

今回は最初の入力で全ての情報が揃う系の問題の為、山登り法や焼きなまし方が適用出来ないかを考える。山登りをするとしたら近傍が探索出来るようにしたい為、Block の構造体を作成して Block 拡張メソッド、Block 縮小メソッドを作りたくなる。
これが実装出来れば、自在にブロックの伸び縮みが操れて近傍が探索出来る為、山登り法や焼きなまし法に繋げていけそう。ということで実装。
この方針は当たりらしく、一気に点数上昇！

**暫定テスト：351,312,313,381 点**
![ahc_img6](ahc6_ppwx4q)
_Seed = 0 (上), Seed = 19 (下) の visualizer_
※Seed = 0 : 2,566,666,667 点 , Seed = 19 : 3,611,258,097 点

### 部分破壊 &amp; 再構築をする山登り

3 つ目の提出の visualizer を見て第一声は『青ブロック巨大過ぎる』。
巨大なブロック自体が良いのか悪いのかは、おそらく今後の方針の判断材料になりそう。巨大ブロック自体は多くの空間を超低コストで埋めてくれるというのは良い点だが、巨大ブロックを作ることに固執しすぎると、他のブロックがうまく拡張出来なくなることも多そうだなと感じた。
ここで、実際にブロックサイズが特定の大きさ以上になったら強制で打ち切る処理を入れたところ、スコアは落ちた。(サイズが大きくなる遷移を妨げてしまったっぽい。)

次に、3 は無の状態から作成した解である為、無難に山登りをしたくなる。
完全ランダムの 1 回きりであそこまで伸びるのだから、数ブロック破壊して出来た空間に対して、再度ブロックを広げていくような処理を時間一杯すれば勿論上がるでしょう。
実装してみると案の定スコアは急上昇！さっきの 5 倍ほど良くなってる！

**暫定テスト：72,975,925,496 点**
![ahc_img7](ahc7_gj90ek)
_Seed = 0 (上), Seed = 19 (下) の visualizer_
※Seed = 0 : 985,714,286 点 , Seed = 19 : 749,633,211 点

### 高速化 &amp; archive 作成

↑ の後、無駄部分を排除したり高速化したりして、山登りのループ回数が 1.5 倍ほど上昇して、暫定テストが、59,087,373,731 点まで上昇。

この後何をするか見通しが立っていなかった為、とりあえず時間を伸ばして様子見。
すると、確かに実行時間をのばすとスコアも伸びるが、その伸びがかなり小さくなってきている。(正確には伸びる時は一気に伸びるけど、伸びるタイミングが減っている) なので、スコア上昇時に archive を取っておいて、山登りで 1000 回以上連続でスコア更新が起きなかったら 1 つ前のベストスコア状態に戻す処理を書いた。

結果絶対スコアは先ほどの高速化後の点数より微増だったが、相対スコアは 17B → 19.9B に上昇。そしてなんと暫定 1 ページ目に入る快挙！マジか！
![ahc_img8](ahc8_dq9xcq)
_当時(開始 5 日目)の順位表_

**暫定テスト：59,475,513,479 点**
![ahc_img9](ahc9_y9yuak)
_Seed = 0 (上), Seed = 19 (下) の visualizer_
※Seed = 0 : 670,634,921 点 , Seed = 19 : 461,659,001 点

### 焼きなまし法に移行

その後、またまた高速化をして、D = 5 で 120,000 回、D = 14 で 10,000 回ほど回るようになった。ここまでくると、D = 5 ではかなり良いスコアを取れるようになってきた。(時間を長くしてもほとんど更新されない状態まで来た。)
となると、ここから先は D が大きいケースとの闘いになる。

多様性確保を目的として archive を作成して遡る処理を書いたが、温度を高めにした焼きなましでも同じく多様性が確保出来ると思った為実装。visualixer を見てみると、D が大きいケースでの改善が多くみられたので提出したところスコアが上昇。
おそらく archive よりこまめに遷移が移ってより多様性が確保されたのだと思う。

**暫定テスト：44,785,122,602 点**
![ahc_img10](ahc10_xo5awe)
_Seed = 0 (上), Seed = 19 (下) の visualizer_
※Seed = 0 : 500,000,000 点 , Seed = 19 : 251,669,372 点

### 近傍を 1 ~ 3 個に制限 &amp; 隣接ブロックを削除 (最終提出)

今までは 1 ~ Block 総数-1 個をランダムに破壊するという処理を書いていた。というのもブロックの位置はかなり密接で数個程度の破壊で更新出来るケースはあまりないと思っていた為。ただ数個破壊でも多少は更新されることから、数個破壊を沢山行えばそこから生まれる小さなブロックのずれが積もって、いつかは良い状態になるのではと思って実装したところスコアは大幅 up。

またブロックを複数個破壊する時は少なくともどちらかの空間で隣接しているブロックを選んで破壊することで、よりまとまった空間を確保することが出来てそこでもスコア up。

これを実装した後に、ちょっとした高速化やハイパーパラメータの微調整を行って最終提出！

**暫定テスト：24,052,095,102 点**
![ahc_img11](ahc11_vdgda5)
_Seed = 0 (上), Seed = 19 (下) の visualizer_
※Seed = 0 : 478,968,254 点 , Seed = 19 : 115,788,663 点

### 終了後

TL での感想戦。上位の方の解法を見ていると、色々な場所で工夫が見受けられてまだまだ甘さを感じた。ざっと見て一番目についたのは、

&gt; ブロックを採用する際の評価値を大きさだけでなく、カバーするのが難しい場所(シルエット上で連結部分が少ない・繋がっている空間が少ない等)をカバーしていた場合に評価値を上げる。

…頭良すぎませんか。

今回は評価値をアレンジすることが全く出来なかった為、次回以降は現象の核を捉えた評価値を生成してみたいなと思った。

また今回の 1 位の方はビームサーチだとか。。異次元過ぎる堂々の 1 位で凄いと思った(小並感)。次回の長期コンに参加する時は、ハイパーパラメータも最適化したりクラウド上でテストが回したり出来るようにしたいと思った。

## 感想

今回は春休み期間ということでいつもより時間があった為、思いついた事は全てやりつくそうという意気でコンテストに参加しました。結果、終盤は失速してしまいましたが、自分の頭で描いていたものは全て実装して過去最高順位を取れたので非常に嬉しいです。

今回の問題自体かなり好きな部類だったのでとても楽しめました。
また今回人生初記事となりましたが、記事を書くことも思ったより楽しかったので、また良い順位が取れたり色変したりしたら記事を書いてみようと思います。

writer の wata さん、スポンサーの MC Digital さん、参加者の皆さん、ありがとうございました。
そして最後まで読んで頂きありがとうございました！


AHC019参加記

## はじめに
through です。
この度自作のwebsiteを作成致しました！最低限実装してみたいと思っていた機能が実装し終わったので、最初のblogとしてこのサイトについて綴っていこうと思います！

## website概要
### 内容
#### Home
・自己紹介
自分の軽い自己紹介ページです。

#### Work
・自分の競技プログラミングのlibrary
今まで作成してきた自分のライブラリの溜まり場を作りたいというのが、このサイトのサブの目的の1つだった為作成しました。随時新しいアルゴリズムを学習したら更新していくつもりです！

#### Blog
・技術系記事・参加記などを綴るblogページ
これが今回のメインの目的。自分のことを綴れるサイトを作りたいという願望が叶いました！

#### Admin
・library・blog の追加・削除・編集
どうせblogやその他の情報を更新していくなら、本番環境で直に編集できるようにしたかった為導入。セキュリティ系の勉強にもなったので一石二鳥。

### 用いた技術スタック
#### Frontend
- Framework: Next.js (TypeScript)
- Styling: Tailwind CSS
- Deployment: Vercel

#### Backend
- Language: Go
- Frameworks: Gin and Gorm
- Deployment: Fly.io
- Database: PostgreSQL

#### Else
- Docker

### 勉強になったこと
- クロスオリジン系の問題の理解

個人的にwebサーバーとAPIサーバーを分けて実装してみたいという気持ちが合った為別々で実装。そこでは docker を用いた local での開発環境と、deployする本番環境では挙動が違い、CORS や JWTを用いたlogin認証のCookieの部分の挙動に関する理解が増えた。

- dockerの内部仕様

これを作る前は、『何かコンテナっていう単位で仮想的に隔離してごちゃごちゃしてるんだな』という理解しかなかったが、コンテナの設定・docker image・コンテナ間通信、等を理解して実装出来る程になった。DBのボリュームを永続化・削除して簡単に環境を一新出来たり、外部サービスにimageをpushしてサーバーを立てたり... と出来る幅が広がったと思う。まだまだ未熟な点が多いので、今後も使って慣れていきたい。

- frontend のパフォーマンス改善 ( SSG, SSR )

以前から友人に、SSGの凄さを教えてもらっていたのを実際に実装して、静的サイトとしてweb
の情報をキャッシュしておくことがいかに爆速になるかを体感した。リアルタイム性を持たせたいページでは SSR を用いることで、SEO的にも良いサイトを作成することが出来た。( SSG → Ondemand-ISR にすると、内容変更があった時にそれを検知して静的情報をrebuildして更新してくれる機能があるらしいので、あとでやる。 )


## 今後実装予定の機能
・Ondemand-ISR に変更  
・codeを載せる時の syntax highlight & 行番号生成  

## 最後に
 技術力的にはまだまだだが、今回のwebサイト制作でfront~backまでの理解が深まったので良し！


このサイトに関すること（技術とか）