## はじめに

※ ↓ 元の記事 ↓

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

大学のプログラミング演習の講義で、GitHub Classroom を活用した課題の自動採点システムを導入しました。この記事では、その経緯、目的、そして実際の運用について紹介します。

昨年、私が所属する大学でプログラミング演習の SA (Student Assistant) を担当することになりました。その業務の一つに、学生が提出したプログラムの採点がありました。従来は、大学提供の授業管理支援システムに学生がプログラムを提出し、それを教員側で一括ダウンロードした後、手動で採点スクリプトを実行するという流れでした。

しかし、この方法にはいくつかの課題がありました。

*   **採点結果のフィードバック遅延:** 教員がスクリプトを実行しない限り採点が行われず、学生が授業時間外に課題を提出した場合、結果を知ることができるのは次の授業以降になっていた。
*   **教員の採点負担:** 採点作業には多くの時間と労力が割かれていた。

これらの課題を解決するために、GitHub Classroom を用いた自動採点システムの導入を目指しました。このシステムは 2024 年度の講義で実際に導入・運用したところ導入までは時間がかかりましたが、一度導入できると凄く楽になったので、2025 年度も継続して利用することが決定しました。

GitHub Classroom を活用した自動採点の記事やノウハウはまだ少ないように感じたので、2024 年度に私たちが試行錯誤した経験を、この記事で共有していきます！

![](aibd4u0yqezmoakioluc)
*GitHub Classroom 上の課題の進捗状況*



## 自動採点の仕組み

今回構築した自動採点システムは、GitHub Classroom を中心的な役割として利用しています。GitHub Classroom は、教師や教育機関がオンライン上で課題の作成、配布、管理を行うことを支援するツールです。GitHub Classroom についての詳細は、以下の公式ドキュメントやサイトをご参照ください。

[](https://docs.github.com/ja/education/manage-coursework-with-github-classroom/get-started-with-github-classroom/about-github-classroom)

[](https://classroom.github.com/)

自動採点の全体的な流れは、以下の図に示す通りです。

![](pxqyndkngji7uftxby47)
*自動採点までの大体の流れ*

この図の流れを、各ステップに分けてもう少し詳しく見ていきましょう。

### 1. 課題用のTemplateリポジトリを作成する

まず、各課題の雛形となる「Template リポジトリ」を GitHub 上に作成します。このリポジトリには、課題の初期コード、採点用のスクリプト、テストケースなど、課題に必要な全ての要素を含めておきます。自動採点を実行するための GitHub Actions のワークフローファイルは、Template ファイルに予め含める必要はなく、この後の課題作成ステップをすると自動的に設定ファイルが作成されます。この Template リポジトリを用意することで、学生全員に同じ環境と課題設定を配布することが可能になります。

### 2. Templateリポジトリを用いてAssignment（課題）を作成する

次に、GitHub Classroom の機能を使って「Assignment（課題）」を作成します。このステップで、ステップ1で作成した Template リポジトリを Classroom 内の課題と紐づけ、学生がアクセスできる招待URLを発行します。

Assignment を作成する際には、GUI または YAML ファイルを用いて、以下のような詳細な設定を行うことができます。

*   **課題名:** 学生に表示される課題の名称。
*   **締切日:** 課題の提出期限。締切時刻を過ぎると、学生のリポジトリへの書き込みアクセスを自動的に制限することも可能（後からの変更も可能）。
*   **Template リポジトリ:** この課題のベースとなる Template リポジトリ。
*   **リポジトリの可視性:** `Private` または `Public` を選択。他の学生の解答が見えてしまうと問題があるため、ここは `Private` を選択。
*   **自動採点設定:** GitHub Actions を用いた自動採点に関する設定。
    *   **ビルドコマンド:** (必要な場合) 採点前に実行するコンパイルなどのビルドコマンド。
    *   **テストコマンド:** 採点を実行するためのコマンド。
    *   **点数:** 設定したテストがすべて成功した場合に与えられる点数。
    *   **タイムアウト時間:** テスト実行の最大許容時間。無限ループなどで採点が停止しないように設定。
*   **保護されたファイル:** 学生に編集されると困るファイル（例: `.github/workflows/classroom.yml` や採点用スクリプトなど）を指定できます。学生がこれらのファイルを変更しようとすると、教員側に通知が届くように設定でき、不正な変更を防ぐ助けになる。

これらの設定を課題ごとに適切に行うことで、柔軟な自動採点環境を構築できます。

### 3. 学生の利用フローと成績管理

Assignment（課題）を作成すると、学生を招待するための専用URLが生成されます。学生がURLにアクセスして自身の GitHub アカウントで認証すると、課題用の Template リポジトリがコピーされ、学生専用の Private なリポジトリが自動的に作成されます。

学生はこの自分専用のリポジトリ上で課題に取り組み、プログラムを作成・編集してリモートリポジトリにプッシュすると、この **`push` 操作がトリガー**となり、予め `.github/workflows/classroom.yml` に定義された GitHub Actions のワークフローが自動実行されます。

ワークフロー内では、コードのビルド、テスト、採点が行われ、その結果（成功/失敗、点数など）はリポジトリの Actions タブやコミット履歴から学生自身が**リアルタイムで確認**できます。これにより、学生は競技プログラミングのように、提出後後すぐにフィードバックを得て、試行錯誤しながら学習を進めることが可能です。

![](du7jbj2spyxipeqcrtnc)
*Actions の log を見ると採点状況が丸分かり*

一方、教員側は生徒のプログラムが自動で採点がされ、採点に関する業務が楽になります。GitHub Classroom を用いると、各 Assignment における学生ごとの最終的な成績（自動採点結果）を **CSV ファイルとして一括ダウンロード**でき、成績管理に非常に便利です。
ただし、単純な配点（例：満点100点）では、CSV だけではどの課題で得点・失点したのか分かりにくいという問題があったため、成績が一目で分かりやすくなるよう、1つの Assignment 内に $N$ 個の小課題がある場合、$i$ 番目の小課題の配点を $i \times 10^{N-i}$ 点としました。

例えば $N=4$ なら、満点は $1 \times 10^3 + 2 \times 10^2 + 3 \times 10^1 + 4 \times 10^0 = 1234$ 点となります。これにより、CSV 上の総合点を見るだけで、`123...N` のような桁の並びから、**各学生の達成状況が一目瞭然**となり、成績の集計や分析が格段に容易になりました。ちなみに、この配点方法だと小課題数 $N$ が増えると合計点数もかなり大きくなります。私の講義では $N$ は最大9程度でしたが、その範囲では特に問題なく機能しました。

このように、学生側の提出フローから教員側の成績管理まで、GitHub Classroom と Actions を中心に一連の流れを構築し、運用上の工夫を加えることで、効率的な授業運営を実現しました。



## 問題点・解決策

ここでは、自動採点環境の構築・運用を進める中で直面したいくつかの問題点と、それらに対する我々の解決策について書いていきます。

### Template リポジトリ作成の手間

GitHub Classroom を利用した自動採点では、課題ごとに「Template リポジトリ」を用意する必要があります。しかし、そもそも今回の自動化導入の大きな目的の一つが「教員側の負担軽減」であったにも関わらず、この Template リポジトリの準備作業自体が煩雑で時間がかかるようでは、本末転倒になってしまいます。特に、採点スクリプト、GitHub Actions のワークフロー、課題の初期コード、説明ファイルなどを毎回ゼロから作成したり、コピーして修正したりするのは非効率です。

そこで、**「Template リポジトリを作るための Template」**、いわば Meta-Template とも呼べるリポジトリを作成することで、この準備作業の効率化を図りました。

[](https://github.com/azu-lab/AutoGrader-Template)

この Meta-Template リポジトリには、以下のような汎用的な要素をあらかじめ含めています。

*   **ローカル採点スクリプト:** 学生が自分のPC上で、提出前と同じ採点基準で動作確認を行えるようにするためのスクリプト。
*   **提出補助スクリプト:** Git の操作に不慣れな学生でも、簡単なコマンドで課題を提出（commit & push）できるようにするためのスクリプト。
*   **基本的なファイル構造:** 課題ファイルやテストケースを配置するためのディレクトリ構造。

Meta-Template 内には Makefile を用意し、いくつかの定型的な準備作業を自動化するコマンドを定義しました。これにより、いくつかの簡単な設定値（例えば課題数など）を与えるだけで、必要なファイル生成や設定がよりスムーズに行えるようになりました。

具体的には、以下のような作業を `make` コマンドで実行できるようにしています。

*   課題数を指定すると、その課題に応じた採点スクリプトを生成する。
*   模範解答のプログラムとテストケースの入力を用意しておくと、期待出力 (答え) を作成する。

### 学生に課題の答えを見られてしまう

自動採点を導入する上で、教員側が最も頭を悩ませたのが「テストケースの期待出力（答え）をどのように管理し、学生のカンニングを防ぐか」という問題でした。単純に Template リポジトリ内に答えのファイルをそのまま含めると、学生が容易にアクセスできてしまいます。

この問題に対して、私たちはいくつかの対策案を検討しました。

*   **解答とテストケースを別プライベートリポジトリに分離する**
    *   **方法:** 解答ファイルや詳細なテストケース、採点スクリプト本体などを、教員のみがアクセス可能な別のプライベートリポジトリに格納し、採点ワークフロー内で、Personal Access Token (PAT) や Deploy Key を用いて解答リポジトリから必要なファイルを取得して採点する。
    *   **メリット:** 学生は自分のリポジトリを見ただけでは解答が分からない。
    *   **デメリット:** PAT 等のトークン管理が必要。また、ワークフローファイルを見れば、どのリポジトリからファイルを取得しているかが分かってしまう。

*   **採点ロジックと解答をコンテナイメージに含める**
    *   **方法:** 解答、テストスイート、採点スクリプト、必要なライブラリ等を全て含んだ Docker イメージを作成・レジストリにプッシュしておき、Actions ワークフローでは、認証情報を使ってこのプライベートイメージをプルしてコンテナ内で学生のコードを採点する。
    *   **メリット:** 実行環境の依存関係をまとめられ、解答がファイルとして直接 Actions 環境に展開されにくい。
    *   **デメリット:** Docker イメージのビルド・管理やレジストリの設定が必要。

*   **外部の採点APIサーバーを利用する**
    *   **方法:** 解答、テストケース、採点ロジックを外部サーバー（AWS Lambda, Cloud Functions, 自前サーバー等）に API として構築する。Actions ワークフローは学生のコードをこの API に送信し、採点結果を受け取る。
    *   **メリット:** 解答が学生の環境から完全に隔離され、安全性が高い。
    *   **デメリット:** 外部サーバーの構築・運用・保守の手間とコストが大きい。API キー等の管理も必要。

これらの方法はいずれも有効ですが、**設定・運用の複雑さ**が伴います。私たちの目的は、できるだけシンプルに、かつ教員側の負担を増やさずに自動採点を実現することだったので、「**学生に見られても問題ない形式で答えをリポジトリ内に含める**」という、よりシンプルなアプローチを採用することにしました。それが**答えのハッシュ化**です。

具体的には、各テストケースの期待出力を事前に計算し、その出力文字列に対して SHA-256 などのハッシュ関数を適用した結果（ハッシュ値）を Template リポジトリに含めておきます。そして、GitHub Actions での採点時には、学生のプログラムの実際の出力に対しても同じハッシュ関数を適用し、事前に計算しておいたハッシュ値と一致するかどうかで正誤を判定します。学生はリポジトリ内にあるハッシュ値を見ても、それが具体的にどのような出力に対応するのか直接知ることはできないため、外部リポジトリ、コンテナ、API サーバーなどの**追加のインフラ管理や複雑な設定を必要とせず**、比較的シンプルにカンニング対策をしました。

ただし、このハッシュ化方式にも限界があり課題の出力が非常に単純な場合（例: "Yes" / "No"、"OK" / "NG"、非常に小さい整数値など）は、考えられる出力候補のハッシュ値を手元で計算し、リポジトリ内のハッシュ値と比較する **総当たり攻撃（ブルートフォース）** によって、元の答えが推測されてしまう可能性があります。~~(ただ、ハッシュ値から元の答えを推測できる学生は、課題自体も余裕で解けそうなので、ある意味合格でも良いのかもしれませんが…)~~

### 自動採点の限界：主観評価と複数正解パターン

GitHub Actions を用いた自動採点は非常に強力ですが、万能ではありません。主に二つの限界がありました。

一つ目は、レポート課題における**考察や自由記述のような、文章の内容を評価する必要がある課題**です。プログラムの出力と異なり、明確な「正解」が一つに定まらず、主観的な評価が必要となるため、自動採点での対応は困難です。現状では教員側が内容を確認して手動で採点するのが現実的と判断しました。

二つ目は、**プログラムの出力として複数の正解パターンが存在しうる場合**の扱いです。例えば、ソートアルゴリズムを実装する課題で、入力データに同じ値を持つ要素が含まれている場合、安定ソートと不安定ソートではそれらの要素の相対的な順序が変わる可能性があります。どちらも仕様を満たしていれば正解とすべきですが、正解パターン数が多いと全てのケースを用意する必要があり、非常に面倒くさいです。実際にこのようなケースがあり、その際は**問題文に制約を追加**することで、期待される出力パターンを一意に定めて (あるいはパターン数を減らして)、単一パターンの照合で自動採点を可能にしました。

### GitHub Actions の無料枠と実行時間

GitHub Actions は非常に便利な機能ですが、特に **Private リポジトリ** で利用する場合、無料枠には実行時間の制限があります。GitHub Free プランの場合、**月あたり 2,000 分** という上限が設けられています（Public リポジトリでの利用は無料です）。GitHub Classroom で作成される学生のリポジトリは通常 Private なので、この制限が適用されます。

[](https://docs.github.com/ja/billing/managing-billing-for-your-products/managing-billing-for-github-actions/about-billing-for-github-actions)

当初、個々の自動採点にはタイムアウトを設定しているため、合計実行時間が上限を超えることはないだろうと楽観視していました。しかし、GitHub Actions の課金仕様として、**ジョブの実行時間が分単位で切り上げられる** という点を見落としていました。つまり、たとえ1回の採点が10秒で終わったとしても、実行時間としては1分としてカウントされてしまいます。学生が頻繁に `push` を繰り返すと、実際の計算時間は短くても、累計の消費時間は思った以上に早く増加する可能性があります。特に学生数が多かったり、課題が頻繁にある・多い講義の場合、全員が何度も提出（push）を繰り返すと、月間の無料枠を使い切ってしまう可能性がありました。

この問題に対して、技術的な解決策をすぐに見つけるのは難しかったため、最初の講義で GitHub Actions の無料枠について簡単に説明し、**可能な限りローカル環境に用意した採点スクリプトで十分にテストしてから提出して、無駄な `push` は控えるように** 学生に協力を依頼しました。これは学生の善意に頼る方法ではありますが、結果的に我々の講義 (受講者 80 人前後、週 1 回の演習) では期間を通して無料枠の上限に達することはありませんでした。

![](ssahsq0rav5zwaf55bcy)
*講義全体の Actions 利用時間。講義は数カ月あるので結構余裕をもって採点できている*

## おわりに

今回、GitHub Classroom と GitHub Actions を活用した自動採点を導入して、競技プログラミングのようにしてみました。教員側は、採点作業の大部分が自動化され、負担が大幅に軽減、結果集計も容易になりました。学生は課題を提出すれば、ほぼリアルタイムで採点結果のフィードバックを受けられるようになり、試行錯誤しながら効率的に学習を進められるようになりました。

教員側も学生も Win-Win になれたので、もし大学などで TA (Teaching Assistant) や SA (Student Assistant) として講義運営のサポートをする機会があり、プログラミング課題の採点業務があるのであれば、GitHub Classroom を活用した自動採点の導入を検討してみることをお勧めします！

大学講義に Github Classroom による自動採点を導入しました！

大学講義の課題を自動採点してみた

## はじめに
この度、データサイエンス系のコンペを主催する Kaggle というプラットフォームで、Kaggle Expert という階級になることができました！

![](usyleautgxyll9ozoh6r)
*Kaggle のプロフィール（Expert ランクに到達）*

アカウント作成時から既に 3 年経ってようやくコンペに参加できるようになりましたが、参加してからはあっという間で、直近に参加した 2 つのコンペでメダルを獲得できました。Kaggle Expert になるだけで既に上位 1 % 付近までいくそうです。

しかし、参加したコンペでは ML (機械学習) はあまり使っていません。その代わりに何を使ったかというと**ヒューリスティクス**です。私は日頃より競技プログラミングを嗜んでおり、日本では有名な競技プログラミングサイトである AtCoder にて AtCoder Heuristic Contest というものに参加しています。ここで得られた知見だけで Kaggle Expert になることができました。



## Kaggle Expert になる最大の壁は参加すること

冒頭にもありますが、私は Kaggle に参加しようと思ったのは 3 年も前であるにもかかわらず、ようやくきちんと参加できた身になります。なぜここまで時間がかかったのかというと、これは技術的な知識不足というより、**コンペの進行ペースや参加者同士の情報共有の仕組みに慣れていなかったこと**が大きかったと感じています。日頃から Atcoder Heuristic Contest に参加している方であれば、あとはヒューリスティクスが通用する Kaggle のコンペに登録をし、適度に参加できれば勝てます。

私はこの**適度に参加する**ことが今までできませんでしたが、下記の 2 つを行うだけでコンペに適度に参加できるようになりました。

### 1. コンペ終了二週間前後から積極的に参加する

1 つ目はコンペ終盤の二週間前から積極的に参加し始めることです。
まず前提として、Kaggle で開催されるコンペは数カ月といった長期間にわたって開催されており、これに最初からコミットすることは一般的な生活をしている人間にとっては不可能に近いと思います。

また、Kaggle には Discussion というコンペのルールの解釈やデータ不整合、一般的な手法について参加者同士が情報を共有できます。しかし、これにより序盤に自分なりの解法を作っても、他の人 (チーム) が強力な解法を共有すると自身の順位が下がり、やる気を無くすという現象が多々起こりました。
（個人的にはコンペ中に他者の考察や解法が見れるのは、競技としてあまり好みではなく、これが Kaggle への参加が遅れてしまった一つの要因だと感じています。）

しかし、Kaggle には **「ルール的には可能だが、コンペ終盤で今までに公開された解法よりも良いスコアが得られる解法を共有することは NG」** という暗黙の了解があるようです。
（下記はサンタコンペ終盤に公開ノートブックで取得できるスコアが更新された時の Discussion）

[](https://www.kaggle.com/competitions/santa-2024/discussion/559694)

これらを考えると、コンペ終盤（終了 2 週間前程度）から積極的に参加し始めることで、比較的参加しやすい期間で、新たに解法が共有されて抜かされる心配が殆ど無い競技性の高いデータサイエンス系コンペとして参加することができます。

### 2. 身近な人とチームを組む

Kaggle に参加する際、**チームを組むこと**は非常に有効な戦略です。特に初心者の方にとっては、一人で挑戦するよりもチームで協力することで、多くのメリットが得られます。私自身は大学のプログラミングサークルの仲間とチームを組んで参加しました。

ソロで参加していると、どうしてもやる気が続かなくなってしまうことがあります。しかし、チームメイトがコンペに参加している姿を見ると、自分も参加しようという気持ちが自然と湧き、特にコンペが長期化する場合や、スコアが伸び悩む時期には、チームの存在が大きくなります。また、一人で考えるとどうしても視点が限られてしまい、考察が局所解に陥りがちです。しかし、チーム内で議論することで、さまざまなアイデアが生まれ、より良い解法を見つけることができます。

初心者にとってチームを組むことは、モチベーションの維持や考察の幅の広がりが、チームを組む最大のメリットだと思います。

---

## 参加したコンペ

ここでは私が参加した二つのコンペについて紹介します。
どちらも **ML をほぼ使わないコンペ**になるので、比較的参加しやすいコンペだと思います。

### 1. Santa 2024 - The Perplexity Permutation Puzzle

()[https://www.kaggle.com/competitions/santa-2024/overview]

これは毎年 11, 12 月付近から 2 カ月ほどの期間で開催されるクリスマスを題材にした最適化問題のコンペです。競技プログラミング経験者向けに言うと Heuristic コンペです。私は AtCoder で開催される AtCoder Heuristic Contest（AHC）というものに今まで参加しており、AHC に参加している有名な方に毎年サンタコンペに参加されている方を見て、自分も挑戦してみようと思いました。

実際に参加してみると、内容は AHC に非常に近いものでした。大きな違いは、コンペ期間が長いことと、コンペ期間内であればいくらでも計算が回せるので Time Limit が無いことくらいに感じました。

結果として 32nd / 1514 で上位 2 % ほどになり、銀メダルを獲得しました。


### 2. FIDE & Google Efficient Chess AI Challenge

[](https://www.kaggle.com/competitions/fide-google-efficiency-chess-ai-challenge/overview)

これは提出プログラムのサイズが 64 KiB 以内、実行時の RAM 使用量が 5 MiB 以内という厳しい制約の中で動作するチェスの AI を作成するコンペです。

私たちのチームは、最初は自作でゲーム木探索を試みました。しかし、長年の歴史が蓄積されたチェス AI にたった 3 カ月のコンペで素人が対抗できるわけもなく、最終的には既存の優れたチェス AI をいかに強さを維持しながら厳しい制約内に収めることができるかというのがコンペの本筋でした。

結果として 108th / 1127 でギリギリ上位 10 % に入ることができ、銅メダルを獲得しました。

![](lw7giffmrwe96unmdsaq)
*このコンペはそれぞれのチームの対戦履歴の visualizer が閲覧可能*



## おわりに

昔から参加しようと思いつつ結局やらなくなってしまう、ということを繰り返していましたが、ようやく Kaggle への参加に取り掛かることができました。

私は今年の 4 月から大学院に進学しますが、大学院卒業までに ML を使うコンペにも挑戦し、Kaggle Master になることを目指して、もっと精進していこうと思います！

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

Kaggle Competitions Expert になりました！

Kaggle Expert 到達記

## 2024 年の振り替えり
2024 年も残り 1 時間を切ったということで、今年やったことを去年同様書き連ねていきます。

去年の振り返りはこちら ↓

[2023 振り返り記事](https://thirofoo.com/blog/2023-reflection)

 

### 1. ICPC Yokohama Regional 2024 進出

去年はボーダー + 3 位で惜しくも Regional に進出できずに悔しい思いをしたが、今年は余裕をもって Regional に進出することができました！

去年の屈辱を晴らせてとても嬉しかった、という反面、ICPC Yokohama Regional で 47 / 55 位で悔しい結果に終わってしまいました。

今年の ICPC は嬉しさと悔しさの両方を感じる年でした。自分は来年が人生ラストの ICPC になるため、来年は嬉しさのみを感じる 1 年にするのが目標。

![ICPC Regional 順位](qlevvafdfme97mlbpnfp)
*ICPC Yokohama Regional 2024 順位 (executive is deprived)*

ICPC 終了後の懇親会にて AtCoder の社長の chokudai さんとツーショットができたのは思い出の一つ。

[chokudai](https://x.com/through__TH__/status/1870767234416877786)

 

### 2. Preffered Networks 夏季インターン参加

[PFN tech blog](https://tech.preferred.jp/ja/blog/i24-gd02-qpe-result/)

上記にもある通り、最新の天候に関するデータを用いて天候データが存在しない地域の天気を推定するというインターンに 8 月後半 ~ 9 月前半の 1 カ月間参加してきました。

今回参加したインターンは、同じインターンの応募者が計 16 人おり、 3 人 4 チーム + 4 人 1 チーム (自分はこちら) に分かれて Kaggle のようなコンペ形式で行われ、Slack にてファイルを Bot に Submit すると順位表が更新されるという、インターンにしては新鮮なものでした。

実際自分のチームはなぜか人数が他より多いというのはあると思いますが、 2 / 5 位で終えることができました。

![記念写真](ptonogomf0ldyl525bhk)
*インターン記念写真*

 

### 3. 卒業研究に着手

今年は結構卒業研究に時間を割いていたと思います。2024 序盤は自分のやりたい研究テーマが決まらず大変だったが、紆余曲折あり良い感じのテーマにたどり着き、現時点で卒業論文は 8 割ほど完了したのでとても良し。

研究室が論文執筆や研究に協力的な研究室なので、進捗を出すのが大変だったりはしましたが、最終的には個人的には面白い研究になったと思います。

今の予定だとおそらく 3 月に学会に応募する可能性があるので、来年も研究を進めていく所存。

 

### 4. Maximum-Cup 2024 開催

[Maximum Cup 2024 開催記](https://thirofoo.com/blog/maximum-cup-2024)

開きました。そして記事も書きました。

今年はさらに作問もしました。記事でも書いてありますが、自分が作った問題の一つが、解説に載せる必要がある証明がとても長くてしんどかったので、もしまた作問する機会があったら難しいけど比較的解説が楽な問題を作ろうと思います()

 

### 5. 松尾研究室主催の強化学習セミナー参加

[Tetris AI](https://zenn.dev/through/articles/ebe77ac5d02f2d)

参加しました。個人的に実際に存在する有名ゲームの AI を作ってみたい欲望は昔からあったのでとても楽しかったです。Zenn で記事を出したところ、現時点で 74 いいねもついてビックリしました。

 

### 6. AtCoder 関連

**今年のレート推移**
- AtCoder Algorithm : 1548 → 1580 (+32)
- AtCoder Heuristic : 2033 → 2135 (+102)

![AtCoder](vdm3y15ilxdvbrwkf3wz)
*レート推移*

今年は成長があまり見られない渋い年でした。精進自体がいつもより全然できていないので当然ではありますが、今年の ICPC で悔しい思いをしたので 2025 年は 2024 年に比べて比重高めで精進していこうと思います。
ちなみに昨年振り返り記事での 2024 の目標では、

> AtCoder A入黄 H入橙

ということで何も叶えられず…。2025 年に奮うご期待。

 

## 来年の抱負

- AtCoder Algorithm 1800
- AtCoder Heuristic 入橙
- ICPC Regional 出場 + Regional で上位半分に入る

## まとめ

今年は「インターン + ICPC + 研究」っていう年でした。The 狭く深く、みたいな年だったので、2025 年はもっと視野を広げて活動すべきかなと思ったりもしました。

また 2025 年からは徐々に就活も始まってくると思うので、そこらへんも視野に入れつつ様々なことをこなしていく！

2024 年総決算

## はじめに
2024/08/31 に自分の所属する埼玉大学にて、Maximum-Cup 2024 という競技プログラミングのオンサイトのコンテストを開きました！個人的な作問に関する感想を述べていきます。

[Maximum-Cup 2024 コンテストページ](https://saitama-maximum.connpass.com/event/325174/)

[Maximum-Cup 2024 リポジトリ](https://github.com/saitamau-maximum/maximum-cup-2024)

※ 以下コンテストのネタバレを含みます

## 作問した問題

自分が今回の Maximum-Cup 2024 で作問した問題は下記の 3 問です。

### Maximum-Cup 2024-B : Saitamaze

**概要**

- $H \times W$ のグリッドがあり、それぞれのマスに高さ $h_{i,j}$ が定義される。
- 任意のマスの高さをコスト $1$ で変えることができる。
    - 移動途中に自身がいるマスの高さも変更可能
- 同じ高さのマスをたどって $(0, 0) \rightarrow (H - 1, W - 1)$ に行く時の最小コストを求めよ。

**感想**

これは、入力でグラフが与えられるわけではないが、 **問題に沿ったグラフを構築することで解ける問題** を作成したくてこれを作りました。
マンハッタン距離的に遠ざかる遷移でも、同じ高さを進む場合はコストが 0 で移動できるのでそういうパターンもあり得るため、普通の探索では解けない少し捻りのある問題になったのかなと思います。

個人的に作成した 3 問の中で一番好きです。

### Maximum-Cup 2024-G : Loneliness

**概要**

- 数直線上に人が直立しており、各人には $1 \sim 60$ の番号が割り当てられる
- 同じ番号の人同士でペアを組むことができる
- クエリが $Q$ 個与えられるので順に処理をせよ
    - クエリ 1 : 区間 $[L, R)$ には番号 $l, l+1, \dots, r$ の人が奇数人、それ以外の番号の人は偶数人存在するという情報が与えられる。
    - クエリ 2 : 区間 $[L, R)$ にいる人を集めた時にペアが組めない人の人数を出力。ただし、答えが一意に定まらない場合は "Ambiguous" を出力

**感想**

これは **ポテンシャル** が関連した問題を作りたくて考えていたらできました。

問題作成をする際は、自分は問題に使いたいアルゴリズムから問題を作るのは個人的におススメです。
今回はポテンシャル使いたいな → 重み付き Union Find 使いたいな → 単純なポテンシャルじゃつまらないから XOR 乗せてしまおう → 今の問題設定に至るという感じでした。

ただ、作成した後に、Union Find を 60 個持てば解けるのでは ? とか、クエリ先読みして Ambiguous さえ判定すれば、それ以外は Euler Tour や Heavy Light Decomposion で解けるのでは ? と色々な解き方が出てきたので、競プロの面白さを実感した 1 問でした。

(色々な解き方があるので想像したよりは多くの方に解かれていてビックリしました。)

### Maximum-Cup 2024-H : Maximum vs Merin

**概要**

- $N$ 種類のスライムがいて、$i$ 種類目は体力 $h_i$ で $c_i$ 体いる
- Maximum 君と Merin ちゃんは下記の二つの操作を、Maximum 君が先行として繰り返す
    - 操作 1 : スライム 1 体の体力を $d (1 \leq d \leq D)$ 削る
    - 操作 2 : スライム 1 体を体力の和が元と同じように 2 体に分裂させる
- スライムの波が $Q$ 回押し寄せてくるので、それぞれにおいて両者が最適に行動した時に最後の 1 体をどちらが倒すかを出力せよ

**感想**

これは前二つと少し違って、最初は後退解析の問題を出したいと思って作ったが、結果的に Grundy 数で解けることを内部テスターとしてお手伝いをしていただいた m_99 さんに指摘されて進化した問題でした。

これは解説に添付する証明を作成するのが地獄でした…。Markdonw にして 930 行…。作問をするうえでは、面白い問題作りも大事ですが、できるだけ解説が書きやすい問題にしないと作問が大変すぎるという知見を得ました (当たりまえ)。

## 全体としての感想

### 楽しい

普段インターネット上で解く速度を競っている参加者の人々と実際に対面で会って交流をするのはとても楽しいです。

自分は幸い周りに競技プログラミングをやっている人がいるものの、普通はなかなか実際に競技プログラミングをやっている人と出会う機会は無いと思うので、競プロの話で盛り上がれる数少ない機会でした。

参加してくださった方々が競技をしている最中は運営者陣で順位表を見ながら全完してくれる方いるかなーと談笑しながら見ていたのですが、結果全完者が出てきちんと解けることが証明された時はホッとしました。

[writer post](https://x.com/through__TH__/status/1829772664849715391)

[writer post](https://x.com/a01sa01to/status/1829772510570954813)

### 作問の大変さ

今回が初の作問 + Writer が二人で AtCoder の黄色以下の人が時間内全完できない程度に楽しめる難易度間を目指していたので、結構大変でした。

特に Maximum vs Merin の証明が地獄だった (というかこいつが大変だった元凶) ので、本当に作問する時は解説しやすい問題作りを意識すべきだなと感じました…。

また、今回は Rime を利用して Github 上で問題作成を行いましたが。普通に Github Actions でテストケースをチェックしてくれるのでとても安心して問題作成ができたので、オンサイトを開催したいと思われている方は Rime を使うといいと思います。

### 問題の言い回し

今回は AtCoder で作問をしている m_99 さんが内部 Tester として参加してくださったのですが、問題の言い回しにおけるアドバイスを沢山いただきました。

例えば Maximum vs Merin で言うと、初め自分が作問して PR を上げた時に **「『ダメージを与える』とかの表現は RPG 要素が強すぎるので、RPG を知らない人でもわかるようにもっと厳密に書いた方が良い」** とアドバイスをいただきました。

また SaitaMaze の方では、最初は隣接マスという表現をしていたんですが、**「隣接マスだと 8 近傍 (斜め含む) とも解釈できるので、上下左右のマスという表現にした方が良い」** ともアドバイスいただきました。

他にも沢山アドバイスを頂きましたが、どれも様々な人が問題を読んだ時に齟齬が出ないように考えられていて、なるほどなーと思うことばかりでした。

普段の AtCoder のコンテストでは参加者から可能な限り疑問が出ないように考えられてると思うと、毎週これを開催してることに非常に驚きです。凄すぎです。

### オンサイトコンテストの参加者の低迷

これは運営陣で話していたことですが、最近の競プロオンサイトの参加者が全体的に減ってるよねーという話をしていました。

これは Maximum Cup だけでなく、他の大学主催のコンテストも以前より参加者が全体的に減ってるのが Conpass の参加登録数を見て明らかなので、もっとオンサイトコンテストが人気になってくれるといいなーと思ったりしていました。

## 終わりに

昨年に引き続き今年も Maximum Cup を開けてとても楽しかったです！(もしかしたら来年も開くかも…?)

ということで、運営・Tester として関わった方々、並びに参加してくださった方々、ありがとうございました！

[writer post](https://x.com/through__TH__/status/1829819482577240238)

2024 年も Maximum-Cup を開催し、運営と作問をしました！

Maximum Cup 2024 開催記

## はじめに

※ ↓ 元の記事 ↓

[元の記事](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 を自作しました！

強化学習でテトリス 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年度総決算

## はじめに
こんにちは、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 は単調非現象型のレートシステムなので、少しづつ上げていつかは橙に届くように精進していこうと思います！

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

AtCoder Heuristic で黄色になりました！

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ヵ月 と想像以上に時間がかかってしまいましたが、この目標を達成出来るようにこれからも自分のペースで精進を続けていきたいと思います！

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

AtCoder Algorithm 分野で青色になりました！

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 にて 789 人の参加者の中で 41 位になりました！

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 にて 787 人の参加者の中で 36 位になりました！

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までの理解が深まったので良し！


この度自分の website を作成しました！

大学講義の課題を自動採点してみた github classroom 2025-04-13 大学講義に Github Classroom による自動採点を導入しました！	Kaggle Expert 到達記 kaggle 2025-04-13 Kaggle Competitions Expert になりました！
2024 年総決算 2024 2024-12-31 2024 年の振り返り記事です。	Maximum Cup 2024 開催記競プロ 2024-11-26 2024 年も Maximum-Cup を開催し、運営と作問をしました！
強化学習でテトリス AI 作成 rltetris 2024-05-02 Neural Network を用いた深層強化学習でテトリスの AI を自作しました！	2023年度総決算 2023 2023-12-31 2023 年の振り返り記事です。
AHC入黄色変記事競プロHeuristic 2023-12-30 AtCoder Heuristic で黄色になりました！	2年かけてAtCoder青色になった話競プロ 2023-12-02 AtCoder Algorithm 分野で青色になりました！
AHC026参加記競プロHeuristic 2023-11-11 AHC026 にて 789 人の参加者の中で 41 位になりました！	AHC019参加記競プロHeuristic 2023-05-10 AHC019 にて 787 人の参加者の中で 36 位になりました！
自分の website 誕生 web 2023-05-10 この度自分の website を作成しました！

Blog