簡単＆便利！ C# × .NET Blazor で AHC ビジュアライザ作り

この記事は、競技プログラミングのヒューリスティックコンテスト*1で用いられるビジュアライザを C# と ASP.NET Core Blazor*2 で自作しよう！ というものです。

C# が分からない方でもできるよう、全手順を解説しています。また Visual Studio というエディタを使いますが、その使い方も全手順を解説していますので、安心して挑戦してみてください！

今回の記事で制作できるビジュアライザ

対象読者

• 自作ビジュアライザに興味のある方
• C# や .NET 開発をしていて Blazor にも興味のある方
• React や Angular などのSPA*3 技術は知っているが、他の選択肢も気になる方
• Web アプリ制作に興味があるが、サーバサイドとクライアントサイドで別の言語を使うのが億劫だと思っている方

ちなみに「まえがき」と「C# や Blazor とは？」は導入や基本説明なので、読み飛ばして「実際に作ってみる」から始めても構いません。

まえがき

競プロ er の皆さん、ヒューリスティックコンテスト楽しんでますか？
私はヒューリスティック初心者ですが、アルゴ*4とは違う魅力を感じながら、マイペースに参加しています。
得点を伸ばすためのアプローチが多様に存在することや、アルゴに比べれば設計能力などを問われる点がチャレンジングで面白いです。

ビジュアライザ

さて、そんなヒューリスティックコンテスト（特に AHC）では、ビジュアライザが公開され、誰もが利用することができます。
例えば、つい先日開催された AtCoder Heuristic Contest 011 - AtCoder でも公式ビジュアライザが配布され、それによって生成された画像は twitter ハッシュタグで共有され*5、誰もが閲覧することができるようになっていました。
twitter.com

ヒューリスティックコンテスト参加者は、ビジュアライザによって自分のコードの動作を可視化することで、以下のような効果を期待できます。

• 書いたコードが想定通りに動いていることを確認できる
• 試しに色々と動かしてみることで考察の参考になる
• やったー動いた！ 楽しい！ という気持ちが生まれる

コンテスト中は、得点を伸ばすためのアプローチが全く浮かばず、何をどうしていいのやら途方に暮れる、そんな苦悩の時間も長いです。そんな時、ビジュアライザから得られる情報が大きなインスピレーションをくれることがあります。逆に「あんな動作や、こんな動作も可視化できたら手掛かりがつかめるのに！」とフラストレーションを感じたりもします。

自作ビジュアライザ

さて、そんな大事なビジュアライザですが、中にはコンテスト中に自作するという人がいます。

公式ビジュアライザが提供されているのに、なぜ自分で作るんでしょうか？

ビジュアライザを自作するメリットは、大別すれば以下の 2 つだと思います。

• 自己満足（単純に作るのが楽しい、自作に憧れていたなど）
• 得点を伸ばすのに役立つ（公式ビジュアライザでは手に入らない情報を得たり、表示法を変えて分かりやすくするなど）

逆にデメリットとなり得るのは以下の点です。

• ビジュアライザ制作に時間を取られる

これらのメリットとデメリットを踏まえて、今回は

• Blazor は欲しい情報を柔軟に、時間をかけずに可視化できる

というところを見せて、C# や Blazor を布教していきたいと思います！

GitHub リポジトリ

今回の記事で作成するビジュアライザの完成品は GitHub リポジトリとしてアップロードしてあります。途中で詰まった際など、適宜参考にしてください。
github.com

C# や Blazor とは？

今回のメインテーマは Blazor ですが、関連性の深い C# 及び .NET についても簡単に説明します。

C#

C# とは、Microsoft が開発しているプログラミング言語です。
Python や JavaScript などのインタプリタ言語ではなくコンパイラ言語ですが、Microsoft の Visual Studio というソフトを利用することで Windows でも簡単に環境構築できます。
わりと新しめの言語であり、汎用性も高い*6ため、「競プロだけでなく色々開発してみたいけど、いくつも言語を学ぶのは時間がかかって大変そう」という方におすすめできます。
かく言う私も IT と全然関係の無い仕事をしている社会人（労働行政分野の公務員）で、日曜プログラマなので、1 つの言語で何でも作れる C# には非常に助けられています。

.NET

詳しくは説明しませんが、.NET とは Microsoft が主導しているクロスプラットフォームな開発者用プラットフォームです。つまりは .NET に基づいてアプリケーションやゲームを作れば Windows でも Linux でも Mac でも Android でも簡単に動かせるよ、的なことです。そして C# や Blazor は .NET の上に乗っかっています。
まあ、Microsoft は .NET という大きな世界を作っていて、その中に C# や 後述の Blazor も入ってるんだなと思ってもらえれば十分です。

Blazor

Blazor もしくは ASP.NET Core Blazor とは、Web アプリケーション*7を作る・動かすためのフレームワークの一つです。ついでに言うと SPA（シングルページアプリケーション） を開発できるフレームワークでもあります。
Web アプリケーションフレームワークには React, Django, Ruby on Rails など色々ありますが、Blazor には非常に珍しい特徴があります。

• サーバサイドのロジックもクライアントサイドのロジックも同じ言語（C#）で書ける*8

Web アプリ（特に SPA）を制作していない方は「同じ言語で書けるから何？ 普通じゃないの？」と思ったかもしれませんが、これはなかなかすごいんです。
というのも、通常クライアントサイドのロジック、つまりブラウザ上に表示される要素の動作やユーザの対話（例えば「↑」ボタンをクリックしたらリアルタイムで画像が動くとか）は、通常サーバサイドのロジックとは別の言語（具体的には JavaScript）で書かれるものだからです。

Blazor ではどちらも C# を使って書くので、両方で同じクラスやメソッドを使い回すことができます。
また、JavaScript などをわざわざ新しく勉強する必要もありません。
私の場合、Unity で制作しているタイピングゲームの C# クラスをランキング Web アプリにそのまま利用したりしています。なんて便利！

ビジュアライザ向きな Blazor

C# 競プロ er にとって、Blazor でビジュアライザを作るのは非常に簡単でメリットが大きいです。

• 提出用に書いたクラスやメソッドをそのままビジュアライザに流用できる！

とにかくこれが最高！ 提出用コード内の C# メソッドを HTML ファイル*9から呼び出せてしまいます。例えとして、以下の HTML コードを見てください。

<table>
    <tbody>
        @foreach (var cc in solver.GetCCS(N, state))
        {
            <tr>
                @foreach (var idx in cc)
                {
                    <td>@idx</td>
                }
            </tr>
        }
    </tbody>
</table>

このコードは、自作 Solver クラスを HTML ファイル内でインスタンス化し、Solver.GetCCS() という自作メソッド（グラフ内の連結成分の配列を得る）を呼び出し、foreach 文を用いて一覧表示しています。コンテスト中、自作の点数評価メソッドのデバッグするために表示しました。

この例だけでも、かなり柔軟かつ手間無く書けることが分かってもらえるのではないでしょうか？

• SPA なのでリアルタイム表示・対話的表示が簡単

またビジュアライザではリアルタイム的な表示や対話的な表示の実装が必要になります。
例えば 50ms おきにターンを進めて描画するとか、スクロールバーを動かす毎に表示を切り替えるといったことですね。
これらの動作を JavaScript で書くとなると慣れない人間にはハードルが高いですが、Blazor なら C# で簡単に書くことができます。

• ホットリロードで効率的に開発できる！

多少の変更であれば、再度コンパイルせずとも即座に表示が更新されます。
表示の仕方を色々と試行錯誤することになるビジュアライザ制作にはとても便利です。

実際に作ってみる

前置きはこのぐらいにして、作り方の概略を紹介していきます。
C# のコードが随所に出てきますが、C# を書いたことがない方も「こんな風に作れるんだな～」と思いながらユルく読んでいただければ幸いです。

手順の概略

1. 環境構築（Visual Studio のインストール）
2. ソリューションと本体プロジェクトの作成
3. Blazor プロジェクトの追加
4. 試しに実行してみる
5. Blazor の基本と「コンポーネント」
6. 盤面表示＆移動ボタンの実装
7. できあがり！

環境構築（Visual Studio のインストール）

Microsoft 公式サイトから Visual Studio 2022 をインストールしてください。（Visual Studio 2019 でも恐らく大丈夫です。）
以下のような追加の機能（ワークロード）のインストール画面が出てきたら、下記の 2 機能にチェックを入れてインストールしてください。

• ASP.NET と Web 開発
• .NET デスクトップ開発

ちなみに Visual Studio Code でも開発できなくはないですが、Visual Studio を使っておくのが最も楽だと思います。私も元々 VS Code ユーザでしたが、C# や Blazor 開発は Visual Studio を使っています。

ソリューションと本体プロジェクトの作成

次は、ソリューション*10と、提出の本体となるプロジェクトを作成しましょう。
ソリューションの中には複数のプロジェクトを入れることができ、プロジェクト間は（適切に設定すれば）相互に参照し合うことができます。

起動後の画面で「新しいプロジェクトの作成」を選びます。

その後は、「コンソールアプリ」を選び、適当なプロジェクト名（例えば AHC011 など*11）を設定して、表示通りに進めてください。
（重要！）下の選択肢では .NET 6.0 ではなく .NET Core 3.1 を選んでください。AtCoder のジャッジ環境は .NET Core 3.1 なので .NET 6.0 の機能を用いてしまうとジャッジに通りません。

プロジェクトが無事作成されると、ソリューションエクスプローラーという部分にこのような画面が表示されます。これが先ほど作成したプロジェクトです。

通常はこの後 Program.cs に提出コードを書いていくわけですが、今回は出来上がった提出コードを用意しました。

こちらのファイルの内容（GitHub リポジトリへのリンク）を Program.cs にそのまま貼り付けて上書き保存（Ctrl+S）してください。

「せっかくだから実際に自分で書きながら進めてみたいな」という方は、以下の記事（最低限の書き方が分かります）などをどうぞ。

C#でAtCoderデビューのための準備 - Qiita

Blazor プロジェクトの追加

今度は本題の Blazor プロジェクトを作成します。

先ほど作成したソリューションを開いたままで、ファイル→新規作成→プロジェクト（Ctrl+Shift+N）を実行し、

プロジェクトテンプレート選択画面で Blazor と入力して検索し、Blazor Server アプリを選択して「次へ」を押します。
（ちなみに Blazor には Blazor WebAssembly と Blazor Server という 2 種類あります。両者の違いは C# で書かれたクライアントサイドのコードをブラウザ上で実行する（WebAssembly）かサーバ上で実行する（Server）かという点ですが、パフォーマンスを真剣に考える場合でない限りどちらでも大して変わりません。ただ、両者でファイル構成やコードに差異が出てくる部分があるため、今回は Blazor Server を使用して頂ければと思います。）

新規プロジェクトの基本設定をします。プロジェクト名は何でもいいですが、今回は分かりやすく "AHC011Visualiser" とでもしておきましょう。
ソリューション(S) の欄は「新しいソリューションを作成する」から「ソリューションに追加」に変えてください。こうすることで、先ほど作成したの中に Blazor プロジェクトが配置され、本体プロジェクトから Blazor プロジェクトへを参照しやすくなります。場所(L) の欄は変更する必要はありません。

追加情報を設定します。フレームワークはどれでもいいのですが、最新の .NET 6.0 を選択するのが良いでしょう。

最初の本体プロジェクト作成では .NET Core 3.1 を選びましたが、今回は .NET 6.0 を選びました。今回の選択は Blazor プロジェクトを動作させるための .NET（Blazor や C# を動かす土台）のバージョンを指定するものです。.NET Core 3.1 はホットリロード*12に対応していないため .NET 6.0 の方が便利です。「本体プロジェクトと .NET のバージョンが食い違うけどいいの？」と心配になるかもしれませんが、問題ありません。プロジェクト毎にバージョンが異なっても構わないですし、.NET 6.0 非対応の AtCoder にビジュアライザを提出するわけではないことが理由です。なお注意点として、例えば .NET Core 3.1 で作成したのに .NET 6.0 以降にしかない機能を使おうとしても動かないので、メソッドや機能を検索する際には「今回使っている .NET バージョンの情報」を探すよう意識しておく必要があります。

試しに実行してみる

Blazor プロジェクトが作成できました。この時点で Web アプリとして表示できるテンプレートが備わっているので、試しにデバッグ実行をしてみましょう。

Visual Studio の画面上部に、下の画像のような部分を探してください。黄色線の部分を参考に Debug, AHC011Visualiser（あなたが設定した Blazor プロジェクト名）に切り替え*13。そしてすぐ右側にある緑三角（赤線部分）をクリックします。
（設定により、一部のボタンが消えている場合があります。その場合は、これらのボタンが表示されている行の一番右側にある下向きの矢印ボタンから、ツールバーの表示/非表示を切り替えることで表示できます。）

実行すると自動的にブラウザが立ち上がり、このように Blazor プロジェクトのテンプレートページが表示されます。

簡単にページテンプレートを生成することができました。このページを改造してビジュアライザを作っていきます。

Blazor の基本と「コンポーネント」

次は Blazor を使うためのポイントとテンプレートの構成を説明しつつ、制作の下準備を進めていきます。

ソリューションエクスプローラー（右側に表示されています。無ければ「表示(V)」から切り替え可能）で Blazor プロジェクトを開き、Pages ディレクトリ内の Index.razor をダブルクリックして開いてください。
（このような *.razor 拡張子*14のファイルは Razor ファイルと呼ばれます。
Razor ファイルは「C# や Razor 構文と呼ばれる独自の記法を用いて色んなことができる、拡張版の HTML ファイル」と思ってもらえれば良いです。）

Index.razor の中身は以下のとおりですが、内容の簡素さに驚くのではないでしょうか。

Blazor では拡張性を高めるために 1 つのページをいくつかの部品に分けて管理しています。例えば head タグや body タグ、他にもページのデザインを記述する CSS などは Pages/_Layout.cshtml などに分割して記述されています。それらのファイル構成の詳細説明は割愛します。

---

さて、Index.razor の中で気になるのは SurveyPrompt という見慣れないタグです。こんな HTML タグは通常ありません。これは Blazor が用意している（もしくは自分で用意する）特殊なタグで、「コンポーネント」と呼ばれています。

コンポーネントの正体を知るために、SurveyPrompt の本体を探してみましょう。ソリューションエクスプローラーから Shared/SurveyPrompt.razor というファイルを見つけ、表示してください。

SurveyPrompt.razor

これが SurveyPrompt コンポーネントの本体です。内容を読むと、先ほどのデバッグ実行で表示された以下の部分であることが分かります。

このように *.razor ファイルは HTML を構成するための部品（コンポーネント）として使うことができます。コンポーネントの使い方はページ本体となる *.razor ファイル内で HTML タグのように記述するだけです。*15

---

この SurveyPrompt.razor コンポーネントを修正しながら、Blazor の仕組みに慣れていきましょう。

まずはコード内の @code{ ... } という部分に注目してください。@code ブロック内には C# のコードを記述できるようになっています。

@code ブロック内を以下のように書き換えてください。*16
SurveyPrompt.razor 変更前

[Parameter]
public string? Title { get; set; }

SurveyPrompt.razor 変更後（[Parameter] 属性を消し、変数 Title に初期値を設定する）

public string Title = "AHC011 Visualiser with Blazor";

ついでに、下の画像で選択している部分は要らないので消してしまいましょう。

次に Index.razor を以下のように書き換えます。
Index.razor 変更前

<SurveyPrompt Title="How is Blazor working for you?" />

Index.razor 変更後

＜SurveyPrompt />

書き換えたら Ctrl+S で上書き保存（Index.razor と SurveyPrompt.razor 両方を上書き保存）し、再度デバッグ実行を行ってください。（実行中のまま閉じていなければ、上書き保存後にホットリロードで自動的に書き換わるはずですが、うまく書き換わらなければ一度テンプレートページを閉じて再度デバッグ実行を行ってください。）

実行すると、以下のように表示が変更されているはずです。

このように、以下の手順で簡単に C# と HTML を結びつけられます。

1. @code ブロック内で変数やクラスなどを定義
2. HTML 内に @変数名 や @クラス名.メンバ名 などと記述

---

ちなみにコンポーネント名はソリューションエクスプローラーから自由に変更できます（ファイル名が自動的にコンポーネント名として解釈されます）。今回は適当に Visualiser01.razor としてみました。コンポーネント名を変更した場合は、もちろん Index.razor 内のコンポーネント呼び出し部分も SurveyPrompt → Visualiser01 に書き換えておいて下さい。

---

次に、ビジュアライザ制作の下準備を兼ねて、以下のようなボタンを配置してみることにしましょう。

Visualiser01.razor の div タグ内に下のような table タグを配置してください。ここでポイントは @onclick="Hoge" の部分です。この記述は「@code 内のボタンがクリックされたら Hoge() メソッドを呼び出す」という意味です。@bind については後ほど説明します。
Visualiser01.razor の div タグ内

    <table>
        <tbody>
            <tr>
                <td></td>
                <td><input type="button" value="U" @onclick="MoveUp" /></td>
                <td></td>
            </tr>
            <tr>
                <td><input type="button" value="L" @onclick="MoveLeft" /></td>
                <td></td>
                <td><input type="button" value="R" @onclick="MoveRight" /></td>
            </tr>
            <tr>
                <td></td>
                <td><input type="button" value="D" @onclick="MoveDown" /></td>
                <td></td>
            </tr>
        </tbody>
    </table>
    <input type="text" @bind="UserName" />
    <p>@ControllerMessage</p>

これでボタンを配置できました。このボタンは後々パズル操作用のコントローラにしますが、とりあえずメソッドの呼び出しや変数の操作を試してみましょう。@code 内に以下の記述を追加してください。（null 参照に関する警告が表示されると思いますが、今回は無視してください。）

    public string? UserName = "Your Name";
    public string? ControllerMessage;

    public void MoveUp()
    {
        ControllerMessage = UserName.ToString() + " pushed U button.";
    }
    public void MoveLeft()
    {
        ControllerMessage = UserName.ToString() + " pushed L button.";
    }
    public void MoveRight()
    {
        ControllerMessage = UserName.ToString() + " pushed R button.";
    }
    public void MoveDown()
    {
        ControllerMessage = UserName.ToString() + " pushed D button.";
    }

再度デバッグ実行をしてみてください。以下のような画面が表示されるはずです。

次に、テキストボックスにあなたの名前を入れて、適当なボタンをクリックしてみて下さい。入力された内容が反映されたメッセージが表示されるはずです。

これは @bind="UserName" によって @code 内の UserName 変数の値がテキストボックスの値と結びつけ（bind）られ、結果として MoveHoge() メソッドの実行結果が変わったことを示しています。

// この @bind によってテキストボックスと C# の変数が結びついた
<input type="text" @bind="UserName" />

……どうでしょう？ とても簡単に HTML と C# が結びつきました。以下のような関係になっているわけですね。
@bind による HTML と C# の結びつき

このように Blazor では、入力可能な HTML コンポーネント（テキストボックスやテキストエリア、レンジスライダーなど）に @bind="変数名" を加えるだけで、対話的な動作が実現できてしまうのです*17。とても便利ですし、記法がこの上なく直感的なところも好印象です。

これで Blazor の基本のキは終わりです。次からが本番です！

盤面表示＆移動ボタンの実装

それでは、ビジュアライザを本格的に作成していきましょう。

• 本体プロジェクトへの参照を追加

まずは、Blazor プロジェクトから本体プロジェクトへの参照を追加します。「参照を追加する」とは、大雑把に言えば、「あるプロジェクトから別のプロジェクトのクラスやメソッドを呼び出せるようにする」ことを指します。

ソリューションエクスプローラー上で Blazor プロジェクトを右クリックして「追加」→「プロジェクト参照」と進み……

本体プロジェクトの名称にチェックを入れて OK をクリックします。

これで Blazor プロジェクトから本体プロジェクトを参照できるようになりました。ここで注意してほしいのは、まだ参照できるようになっただけで、実際に参照してはいないということです。この状態でクラスにアクセスしようとしても、エラーが発生します。イメージとしては「国境が開放されただけで、道路が開通していない」といったところでしょうか？

ということで、Blazor プロジェクト内の Visualiser01.razor の先頭行に以下のコードを追加します。AHC011WithB の部分は本体プロジェクトの名前です。違う名前を設定した方はその名前に変更してください。

@using AHC011WithB

これで Visualiser01.razor から本体プロジェクト AHC011WithB 内の public なクラスや変数にアクセスする準備が整いました。

---

一応、本体プロジェクト Program.cs 内の構成を簡単に説明しておきます。

• Solver クラス

私の場合、AtCoder で問題を解く場合はいつも Solver という名前のクラスを作成して利用しています。このようなクラスを作ることは必須ではないですが、色々カスタマイズしやすくなるため利用しています。

• Solver.BoardState クラス

盤面の状態を管理するためのクラス。インスタンス名[i, j] で盤面の i 行 j 列にアクセスできます。*18

• Solver.CanMoveHoge(N, state) 及び .MoveHoge(N, state)

盤面サイズと盤面状態を引数として渡し、移動可能か否かを返すメソッドと、移動を実行する（state の状態を変化させる）メソッドです。（C++ ユーザーの方などは「この渡し方では state の deepcopy が変更されるだけで、state 自体は変更されないのでは？」と思うかもしれませんが、C# ではこの渡し方で state が保持する値を変更することができます。）

---

ページに HTML オブジェクトを配置し、動作を実装していきましょう。

• 盤面用アイコンをプロジェクトに追加

公式ビジュアライザのアイコンを掲載するのは著作権法上の問題があるので、ここでは自作アイコン画像を使います。私の推し動物であるチーターのアイコンを作成しましたのでご利用ください（個人利用なら公式ビジュアライザの画像を流用してもいいかもしれませんが、自己責任でお願いします。）
1. icons.zip をダウンロードして解凍

2. wwwroot ディレクトリを右クリックして新しいフォルダを追加（フォルダ名は icons としてください）

3. ソリューションエクスプローラーに icons フォルダが表示されるので、そこへ先ほど解凍した画像 16 枚をドラッグ＆ドロップ

これで、先ほどの画像が Blazor プロジェクトに含まれました。このように wwwroot 内に格納したファイルは静的ファイルとして配信されます。例えば wwwroot/icons/0.png なら http(s)://デプロイしたアプリのURL/icons/0.png でアクセスできるようになります。

• （C# 側）盤面を管理するための変数等を定義

以下のコードを Visualiser01.razor の @code ブロック内に記述してください。
Visualiser01.razor の @code ブロック

Solver? solver;
Solver.BoardState? state;

public int N = 6;
string inputString = "62ce43\na068f9\na89da9\n5d93cb\n276253\n424ba8";

• （HTML 側）盤面を表示するためのテーブル

以下のコードを Visualiser01.razor の div タグ内に記述してください。このように、for 文や foreach 文を用いて反復的に HTML オブジェクトを描画できます。便利なのでよく使います。ちなみに if (state != null) としているのは、null 参照エラー（ページ初回表示の際に state == null なのに state[i, j] を参照してしまうこと）を避けるためです。
Visualiser01.razor の div タグ内

@* Visualized table *@
@if (state != null)
{
    <table>
        <tbody>
            @for (int i = 0; i < N; i++)
            {
                <tr>
                    @for (int j = 0; j < N; j++)
                    {
                        @* @(state[i, j]) は 0 ~ 15 （盤面の状態）に変換される *@
                        <td><img src="icons/@(state[i, j]).png" width="64" height="64" /></td>
                    }
                </tr>
                    
            }
        </tbody>
    </table>
}

• （HTML 側）入力受け取りなどの UI 作成

@bind や @onclick を使って @code ブロック内の変数やメソッドと結び付けます。先ほどと同様 div タグ内に記述してください。ちなみに N を入力するためのテキストボックスを追加したのは、入力文字列の処理を簡単にするためです。

N: <input type="text" @bind="@N" size="2" /><br />
<textarea @bind="@inputString" style="width: 200px; height: 250px;" /><br />
<input type="button" @onclick="Visualise" value="Visualise!" /><br />

• （C# 側）入力を受け取って盤面を生成するメソッド

以下 2 種類のコードを Visualiser01.razor に記述してください。2 個目のコードは少し長いですが、テキストエリアの入力を受け取って、盤面（state）を生成しているだけです。
Visualiser01.razor 先頭行（16 進数 -> 10 進数変換メソッドを呼び出すために必要）

@using System.Globalization

Visualiser01.razor @code ブロック内

/// <summary>
/// inputString を入力として受け取り、Solver.BoardState state（盤面状態）を生成する
/// </summary>
void Visualise()
{
    if (inputString != null)
    {
        solver = new Solver();
        state = new Solver.BoardState(N);
        // 入力受け取り
        string[] lines = inputString.Replace("\r\n", "\n").Split('\n');
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                state[i, j] = int.Parse(lines[i][j].ToString(), NumberStyles.HexNumber);
            }
        }
    }
}

• （C# 側）上下左右への移動を行うメソッド

Visualiser01.razor @code ブロック内の 4 つの移動メソッド（MoveUp|Right|Left|Down）を以下のように変更してください。Up の部分は Right|Left|Down にそれぞれ修正してください。
Visualiser01.razor @code ブロック内

public void MoveUp()
{
    if (solver.CanMoveUp(N, state))
    {
        solver.MoveUp(N, state);
        ControllerMessage = "";
    }
    else
    {
        ControllerMessage = "can't move";
    }
}
以下 MoveLeft(), MoveRight(), MoveDown() は略

• 前の章で使ったテスト部分の削除

余計なもの（以下の 2 行）を削除しておきましょう。面倒なら放っておいても構いません。

<input type="text" @bind="UserName" />

public string? UserName = "Your Name";

できあがり！

これでビジュアライザの基本的な機能が完成しました！ デバッグ実行（F5）してみてください。

このように、Visualise! ボタンを押すと盤面が表示され URLD ボタンで動かせるようになったはずです*19。

また、画面の端で外側に移動しようとすると "can't move" が表示されるようになっています。試してみましょう。

うまく動作しなかった場合は、今までの記事をもう一度読み直して、どこかに間違いがないか確認してください。それでも動作しない場合、この記事へのコメントや twitter などで私までご連絡ください。

おわりに

お疲れ様でした！ Blazor 体験はいかがでしたか？

• 提出コードの C# メソッド・クラスをそのまま参照して、同じソリューション内で利用できる

という Blazor のメリットを活かして、本体プロジェクト以外には大したコードを書かずにビジュアライザを作成することができました。

Blazor に慣れた C# プログラマにとっては、これらの手順は（アイコン作成は別として）10 分ほどで終わります。つまり、僅かな時間と手間をかけるだけで、以下の 3 つをビジュアルで分かりやすくデバッグできるということです！
・盤面を管理する BoardState クラス
・ある盤面状態から移動処理を行うメソッド
・移動が可能かどうか判別するメソッド

テストプロジェクトの作成や printf デバッグの手間が減り、より設計やコーディング、問題考察に集中できますね！ また、変数と表示が直接結びついており処理過程を段階的に表示することが容易なので、バグ箇所の特定にかなり効果的だと思います。

---

今回の記事をきっかけに、競プロ er の皆さんにゲーム、デスクトップ・スマホアプリ、Web アプリ、競プロと何でもできる C# と .NET の世界に興味を持っていただければ幸いです！

（付録）この後のカスタマイズ例

今回は入門記事ということで、ごく基本的な機能だけを持つビジュアライザを作成しましたが、実際のコンテスト中にはもう少し本格的なビジュアライザを制作していました。
コードが汚かったり色々とマズいところがあるので、それらを整理してから、カスタマイズ例として掲載する予定です。

こんな感じで、コンテスト中に欲しい情報を雑に追加していったため、とてもじゃないけどぱぱっとアップロードできるコードではないのです

（付録）実装 Tips

余裕があったら追加します

追加したいもの

• 非同期処理（メソッドの途中での HTML 再描画）

（付録）参考リンク集

余裕があったら追加していきます

---

*1:ヒューリスティックコンテストって何？ と思った方へは、入門記事として 競プロ〜ヒューリスティック/マラソン事始め〜 - Qiita をおすすめします。

*2:後述しますが、サーバサイドだけでなくクライアントサイドのロジックまで C# で記述することができる Web アプリケーションフレームワークです。

*3:シングルページアプリケーション。単一のページで構成され、ページ遷移やページ更新を挟まず対話的に動作する。

*4:いわゆる一般的な競プロ問題のこと。ABC や AGC など、AC さえすれば回答時間以外に得点差がつかないのが一般的。

*5:コンテスト中はアップロードできる画像の種類に制限があるので注意

*6:Microsoft が強力に後押ししているため、コンソールアプリ、ゲーム、Windows アプリ、Web アプリケーションなど様々な場面で使われており、Unity という超有名ゲーム開発プラットフォームでも採用されています。C# で作れないものは少ないです。

*7:Web アプリケーションとは、Web 上で動き、ブラウザを通して利用できるアプリケーションのことと思ってもらえばいいです。AtCoder や AtCoder Problems、他にも銀行のアプリなどなど。

*8:過去の私と同様「コンパイラ言語の C# でクライアントサイドを書けるわけが無いでしょ！」と思うかもしれません。大丈夫です。Blazor には Blazor Server と Blazor WebAssembly という 2 つの種類があり、それぞれ違うやり方でクライアントサイドでの C# 実行（のような挙動）を実現しています。

*9:正確には Razor ファイルです。後述します。

*10:私も正確に理解できていない気がしますが、まあ 1 つの大きなアプリケーションを指していると捉えればいいはずです。

*11:今回の記事に掲載する手順のスクリーンショットでは、プロジェクト名が AHC011 になっているものと AHC011WithB になっているものが混在しています。これは元々 AHC011 で作成していたものをブログ執筆用に AHC011WithB で作り直したためです。表示名は違いますが、同じものだと思ってお読み下さい。

*12:デバッグ実行中にコードを上書き保存すると、軽微な変更ならリアルタイムに適応してくれる機能です。つまりデバッグ実行を再起動する手間が減ります。

*13:この設定の意味は、文字通り「Debug モードで AHC011Visualiser プロジェクトを起動する」という意味の設定です。右側の選択部分を AHC011 などの本体プロジェクト名に切り替えれば、本体プロジェクトの方をデバッグ実行することができます。

*14:他にも *.cshtml という拡張子もほぼ同じもので、これも Razor ファイルと呼ばれます。

*15:フォルダを整理するため、コンポーネントな各ページで共有する部品は Shared フォルダに、ページ本体は Pages フォルダに保存するのが良いと思います。

*16:テンプレートではIndex.razor からページタイトルをプロパティとして受け取るようになっていましたが、その仕様は必要無いので削除します。

*17:ちなみに今回はボタンクリックを契機として自動でページが描画された（メッセージが表示された）わけですが、これは Blazor 側が「あ、ボタンが押されたな。値が変更されたかも」と分かって気を利かせて更新してくれたからです。Blazor 側が値の変更に気付かない場合（例えばボタンなどユーザの操作は無く、単にメソッド内で値が変更されただけなど）は StateHasChanged() というメソッドを呼び出して Blazor に変更を伝える必要があります。またメソッドの途中で描画を変更させたい場合は非同期処理（async, await など）を入れる必要が出てくることもあります。その辺りは今回割愛させてください。

*18:C# のインデックスプロパティという機能を利用して、N*N サイズの 1 次元配列である Placement に "インスタンス名[i, j]" でアクセスできるようになっています。

*19:上の画像では見栄えを良くするために Table タグを追加しています。気になる方はこの Visualiser01.razor を参考に HTML を整えてみてください。

ありがとう、競プロはタイピングの役に立つ ～「プログラミングの目的化」のおかげで人生がより楽しくなった話～

まえがき

最初に謝っておきます。

この記事、目的はほぼ自作ゲームの宣伝です……

ただ競プロに感謝してることも事実。

ちょくだいさんがよく言及している「プログラミングの目的化」が良い意味で刺さって、人生がより楽しくなっている話をさせてもらおうと思います。

（「目的化」の是非について自分の立場から言いたいことを言っておきたい、という思いもあります。）

競プロ er としての自己紹介

まず、自分について書いておきます。

テルという名前で AtCoder などのコンテストに参加しています。

ギリギリ水コーダー（今やったら落ちそうですが……）で、自分としては結構、いやかなり頑張ってこの位置まで来ました。

最近はご無沙汰してますが、たまーに Project Euler を解いたり、後述するゲーム製作などの目的のためにも C# で AtCoder の簡単な問題を解いたりして、ゆるっと競プロを楽しんでいます。

文系出身で数学が苦手（競プロ er 間での比較であって、一般から見ればマシな方ではありますが）な中、持ち前の粘り腰で整数や離散数学など分からない範囲を勉強し続け、なんとか水色までこぎつけました。

（苦労したみたいな書き方してますけど、とても楽しい苦労でした。これからも少しずつ離散数学を勉強していくつもりです。）

タイパーとしての自己紹介

プログラミング・競プロも今やかなり自分の中で「好き度」の高い趣味ですが、メインの趣味は、小学生から現在（33 歳）までちょくちょく飽きながらもずっと続けているタイピング（ご存知キーボード早打ち競技）です。

既に終了したタイプウェルというゲームのランキングでは、閉鎖時で ローマ字入力 総合 1 位 / 10,695人、かな入力 総合 2 位 / 1,196 人、英単語入力 総合 1 位 / 2,151 人でした（ちなみに、ちょくだいさんがタイピングめちゃくちゃ速いって知ってます？ ちょくだいさんもこのランキングに登録されていて、ローマ字入力 775 位です。……実際のちょくだいさんの速さからすると、多分ガチではやり込んでないので、簡単にもう少し上にいけたと思いますが）

他には、 Realforce Typing Championship 2017 4 位 ( 2018 は 5 位 )、寿司打高級一発（ノーミス縛り）40,860 円得 などの実績があります。

www.youtube.com

寿司打高級一発、ノーミス打ち切り4万円得超え！！！！ 寿司打高級一発、ありがとう。一つ高みに昇れたぜ！！！！！
高級10,000円コース【一発勝負】で、
★40,860円分 お得でした！（速度：9.9key/秒、ミス：0key）
https://t.co/OQDLssMTiw #寿司打 pic.twitter.com/7mJDbbXSBl

— テル (@vuttar) 2020年6月27日

「ありがとう」って何？

さて、自己紹介はこのくらいにして、タイトルの「ありがとう、競プロはタイピングの役に立つ」に繋がるよう話していきたいと思います。思い出話なので、ちょっと長くなります。

人生をかけたランキングの閉鎖

先ほどの自己紹介で挙げたタイプウェルというゲームは、僕が誇張抜きで人生を捧げたゲームでした。2019 年 6 月に惜しまれながら公式サイト及びランキングの更新が終了し、翌年春には公式サイトが閉鎖しました（先ほどのリンクは有志によるミラーサイト。）

この喪失感、分かりますか？

競プロ er のうち、特に AtCoder や Codeforces や 情オリに人生を捧げてるガチ勢の方々は、想像がつきやすいかもしれません。例えば、10 年・20 年後にもしかしたら AtCoder や情オリが閉鎖・終了するとなったらどうです？

まあサイトや大会が無くなっても、色変した時にレーティンググラフを何度も眺めてニヤニヤしたり、コンテストで 30 秒差でギリギリ E 問題が解けなくて悔しかったり、チームメイトと切磋琢磨してメダルを獲得したりした、その思い出は消えないです。消えないですけど、思い出が消えないから何なんだよ。なんでなくなっちゃうんだよ。喪失感ヤバいって。閉鎖時も三十路でしたけど、正直、布団の中でボロボロ泣きました。

喪失からの競プロガチり

喪失と多少前後して、競プロを始めました。

タイパーに競プロ er が多かったため、競プロの話題はよく目にしていて興味があったし、「タイプウェルが無くなるとなると、俺の『技能を競いたい』という本能を満たす場所が無くなる……」と思っていたこともあり、競プロを始めました。

プログラミングは中学生の頃に、遊び程度に JavaScript や Perl CGI を触っていた（当時ブラウザゲームが流行っており、それの真似事をしたり、掲示板をいじったりしていた）くらいで、「言語仕様を学べば Fizz Buzz は書ける」「オブジェクト指向？ えーと、動物クラスから人間クラスを作る的な、アレだよね？」くらいの感じでした。つまりは「プログラミングをちょっとかじっただけの人」でした。

それが、競プロをガチる中で、プログラミングを学び、苦手だった「パソコンについて」を学び…… と、どんどんパソコン・プログラミングとの向き合い方が変わっていきました。

パソコンとの向き合い方の変化

競プロをガチるに当たり、最初は Atom というエディタで Python を書いていました。もちろん、Python ならコンパイルが要らず、Linux も要らないからです。それしかできなかったんです。

しかし、ガチっていく中で、Python では今の自分が上に行くのは難しいことに気付きました。それは「つい計算速度が遅いことを気にしてしまう（もしくは言い訳にしてしまう）あまり、本質的な部分に目が行かない」ことに気付いたからです。言うまでもなく　Python ユーザには maspy さんがいますし、競プロタイパーの中にも Python のみで青コーダーになっている方がいて、Python でも十分戦えることは分かっていました。ただ、コンテストや過去問を解く際に「こういう書き方をしたら定数倍改善になって通るかも……」「PyPy だと遅くなる書き方になってるかも……」「これは解法は合ってるのに Python のせいで通らないのかも……」などと、非本質ばかりに目が行き、非効率的でした。

そこで、意を決して Linux を使い、C++ で参戦することに決めました。

昔から「Linux という OS があるらしく、なんかギークな奴は使ってるらしい」と憧れを抱いてはいましたが、難しそうで触っていませんでした。色々と調べて、今は WSL を使って比較的簡単に Linux を使えることが分かり、それを導入しました。

しかし、簡単にはいきませんでした。コマンドラインからパソコンを操作する感覚がそもそも無いし、ファイルの考え方が全然違うように思えました。「exe ファイルじゃないのに実行ファイルになってる！？」とか、「エディタの使い方が分からない！」といったことから始まり、本当に様々な問題点が噴出し、大苦戦しました。

Linux だけでなく、コンパイルを要する C++ を使えるようになることも非常に難しかったです。コンパイラが動かない、デバッガが動かない、昨日動いたはずのコマンドが今日は動かない、VS Code の設定をいじったら何もかも動かなくなった、などなど…… マジでしんどかったです。

競プロのおかげで、なんとか続いた

この時、Linux と C++ を続けられたのは、競プロのおかげです。（競プロのためにやっていたことなので、そう書くのもおかしな話ですが）

これが業務で Linux や C++ を使うなら「すぐに使えるようにならないとヤバい」と悲壮な覚悟が必要ですが、競プロでは（少なくとも自分にとっては）「プログラミングを競うこと」が目的であり、「パソコンやプログラミングが上手に使えること」は手段（普通は逆ですね）なので、上手くいかなくても（それなりにしんどいとはいえ）比較的ラクでした。

この逆転現象があるからこそ、Linux が全然動かせない、C++ が全然動かせないといった間も、「とりあえず Python で参加し続ける」という雑な解決法で済みました。また「いつまでにマスターする必要がある」ということも無いので、「一旦デバッガを使うのは諦めて、とりあえず目でデバッグしていこう」といったゆったりとした取り組み方ができました。

それでも、C++ が少しずつ分かるようになることで解説ブログなどのサンプルコードが読めるようになったり、無駄な定数倍改善を考えなくて済むようになったり、色々とメリットを感じられ、無理なく段階的に、競プロ er として、そしてパソコンユーザーとして（？）成長していくことができました。

今はどうなった？ 目覚ましい進歩

そうして楽しみながらゆっくりとプログラミングやパソコンを上手になっていく内に、だんだん「自分にもできる」「あれも面白そう、これも面白そう」と興味の範囲が広がっていき、気付いたら色んなことができるようになっていました。もちろん、どれも業務でやっている人はおろか、twitter でフォローさせて頂いているつよつよ中高生にも及ばないレベルなんですが、過去の自分と比べたら物凄い進歩です。

例えば、できるようになったことは……

• 家計の計画を立てる際に、MoneyForward から DL した csv を Python で整形して色々と分析
• 応用情報技術者を勉強しているが、競プロのおかげで「あれのことね！」となる部分が結構ある
• VPS を借りて Ubuntu 内に Nginx, uWSGI, Django を設置し、簡単な Web アプリを作ってデプロイできる
• C# を学んで Unity で簡単なゲームを作成できる

などなど。これだけでも「競プロありがとう」と言いたくなってしまいます。ただ、どれも、本当に大したことじゃないと思う人も多いと思います（実際 twitter をしていると、もっと凄いことをしてる人が無限にいると思える。）

でも、自分にとっては、これが大きな意味を持つ展開に繋がりました。

タイプウェルを思い出だけにしない

これらのことができるようになりりつつあった頃、ふと思いました。

「そう言えば、神競技であるところのタイピング、神ゲームであるところのタイプウェルだけど、大きな不満もあったんだよな～」と。

タイプウェルオリジナルの弱点

タイプウェルに対する不満というのは、タイプウェルオリジナルというランダム文字列入力ゲーム（もはやゲームと言えるか怪しい）のことです。

こんなゲームです。ちょっとどうにかしてますね。初めて見た時は「こんなもん打てるやつ人間じゃない」と思いました。

ただ、実はこのゲーム、大きな弱点がありました。古いライブラリを使っていたからか、「乱数が非常に弱い」のです。

一見、完全ランダムに見える文字列ですが、現在時刻を元に乱数が生成されていて、そのパターンも無限に近いほど多いとは言えないため、文字列に偏りがありました。それはそれで、お決まりの文字列を攻略する楽しみがあったり、悪くはなかったですが、「わけの分からない文字列を必死で打つ」というクレイジーな楽しみ方は少しスポイルされていましたし、「現在時刻を任意に調整することで打ちやすい文字列を誘発させる」といった攻略法を取るか取らないかで、タイパー毎にスタンスの違いが生まれたりしてしまっていました。

タイピング自体の弱点

また、少し話が飛びますが、タイピングは「言語」に依存するゲームであり、だからこそ固有の弱点を持っています。それは「日本語タイピングがどれだけ速くても、世界の人と競えない」ということです。

競プロで考えてみてください。tourist がたまに ABC に参加してくると、「うわアッツ！！」と思いませんか？ AGC でランキング一覧を見て、tourist, ksun48, Um_nik, yutaka1999, semiexp, snuke, chokudai, ... といったそうそうたるメンバーを見ると、「到底相手にはならないけど、それでもこいつらと同じコンテストを戦ってるんだ……！」と思いませんか？

タイパー界にも Sean Wrona という tourist みたいなレジェンドがいます。その人と同じ土俵で戦えないの、つまんねーなって思うことがあるんですよね。まあ、もちろん英語タイピングという分野はあって、typeracer というので同じ土俵で競えます。これはこれで素晴らしいサイトですが、結局「英語」なので、中国語のタイピングがめちゃくちゃ速い人とかいても分からないわけですよね。うーん、って感じです。

自分なりの回答

こういったことをグルグルと考え続けた私は、こんな（ヤバい）結論に至ってしまいました。

「特定の『言葉』じゃなくて単なるランダムな文字や記号の羅列を、それも文字種（アルファベットやひらがなや漢字）すら選べるようにして、更にハックしにくい強い乱数で完全ランダム生成で課題文にして競ったら、完全無欠のグローバルタイピング競技ができるじゃん！！」と。

競プロありがとう

これを思いついたとき、私は「あっ！！」と思いました。

「えっ！！ 今の俺ならゲームもランキングも作れるじゃん！！」と。

「競いたい」という単なる「目的」としてプログラミングをやっていた私ですが、いつの間にか「手段」としてのプログラミングも得ていたことに気付いたのです。

それに気付いてから 1 ヶ月（12 月頭くらいに気付きました）。頭がおかしくなるくらい Unity と C# をやりまくって、あ、でも 1 週間くらい将棋に浮気して、とうとうそれなりに形になるものができました。

そこで、競プロありがとうの気持ちを込めて、この場を借りて宣伝させて頂きたいと思います。（やっと本題に入れた……）

この記事が琴線に触れた方がいましたら、是非プレイ＆ランキング登録をしていただけるようお願いします。

自作ゲーム Typing (is) Nonsense

作ったのはこんなゲームです。どんなゲームか？ 動画を見たらすぐに分かると思いますので、ぜひ動画を見てみてください。このランキングサイトから DL できます（キー入力の実装の関係で、今はまだ Windows 限定です。ごめんなさい。）

アルファ版でまだまだ機能が少ないですが、とりあえず本質的なタイピング部分は出来てますので、十分楽しく遊べる（もしくは十分「なんだこのクソゲー！」と怒って放り出せる）と思います。

youtu.be

また、頑張って自分の VPS にランキング サイトも自作して設置しました。

正直、まだ Django は下手くそで、全然満足の行くものが作れていませんが、どんどん成長して、このランキングサイトを世界中の全てのタイピング好きが、言語に関係なく無意味な技能を競い合える素晴らしいサイトに育てていきたいと思っています。

 あとがき : 喪失感は？

こうして、私の喪失感も少し和らぎました。もちろん、まだまだ枕を濡らすことはあるのですが、これから自分の足で、自分の道を歩いて行きたいと思います。

タイプウェルはなくなってなんかいない。タイプウェルの魂は形を変えて、俺のクソゲーの中に生き続ける……！

競技プログラミングに関係する数学の整理 ～文系出身や数学苦手erが、もっと競プロを楽しむために～

まえがき

この記事では、競技プログラミングに関係する数学用語・概念と、それがどんな単元（分野）に属するものかを整理（一覧化）します。
競技プログラミングの問題に出てくる用語・概念をはじめ、競技プログラミングの解説記事などに出てくる用語・概念も、思いつく限り挙げています。

「この記事の数学的な部分、どのぐらい信用できるの？」とか、「数学苦手と言ってもどのくらい苦手なの？」といった疑問への参考としては、筆者のバックグラウンドを記事の最後で紹介したので、気になる方は先にそちらを読んでください。

この記事の目的

文系出身や数学苦手erで、「難しい数学をやらずに」競プロを楽しむ、という取り組み方をしている方もいると思います。
それはアリだと思いますし、それでもやり方や本人の能力次第で水コーダー以上になることはできると思います。

ただ、「数学ができたらもっと楽しいだろうにな……」とか「もっと強くなれるだろうにな……」と思っている方も多いはずです。
そういう方の中には、過去の私と同じように、「競プロをもっと楽しむために、少しずつでも、数学を学んでいきたい！ でも、何を勉強すればいいの？」という方もいるのではないでしょうか。

今回は、そういう方の参考になるように、自分が水コーダーになるまでに出会った（・学んだ・これから学ぶ）数学的知識・考え方を、用語と単元（分野）の観点から自分なりに整理してみます。

意図する対象読者

文系出身だったり、数学が苦手だったりして、競プロでは数学が必要になると聞いて、不安に思っている方。
もしくは、競プロでは数学が必要になると聞いて、「よっしゃ！ そんならバリバリ数学勉強してアド取ったるわ！」と思っている方。

また、「競プロや競プロ記事で知らない数学用語が出てきて、用語名でGoogle検索したもののイマイチ分からず、基礎から学びたいと思っているのに、そもそも何の分野なのかよく分からなくてうまく勉強できない」という方。
（このシチュエーションが今まで何回あったことか……）

今回の整理の仕方（記事の見方）

競プロをやっていく中で「あれっ、これ何だろう？」となった時、必要な知識に辿り着けるように、逆引き形式で整理します。
つまり、「競プロで出会う言葉や、必要になる式変形など」を挙げ、「それがどのような数学の分野に当たるか」を記載します。

注意

一覧を見て、「こんなに勉強しないといけないのか……」と思わないでください。
「あれっ、これ何だろう？」をできる限り解決するため、沢山のことを一覧に載せましたが、どれも「うーん、これは今はいいや！」と飛ばしても、特に問題無いはずです。

また、数学の分野名は基本的にできるだけ新しい教育課程を参考にしましたが、コロコロ変わってるのと、それほど真面目に調べてないので、ちょっとズレてる場合があると思います。
例えば、数学Ⅰと書いてあるけど今は数学Ⅱに移っている、など。
そのため、勉強のために検索する際は、「数学Ⅰ」「数学Ⅱ」といったくくりより、単元名を使うことをおすすめします。

競プロに関係する数学（本題）

「言葉（文系でも多分聞いたことはある）」編、「言葉（文系だと聞いたことないかも）」編、「言葉（離散数学）編」、「式変形」編、「図形っぽいやつ」編に分けます。
前者2つはそのまんまですが、後者2つは、「この式変形何？」と思ったときと、「これ図形関係っぽいけど何？」と思ったとき用です。

「離散数学」とは、文系の方は聞き慣れないかもしれないですが、競プロ及び情報学に最も深く関わる学問分野です。
自分は、この「離散数学」が深く関わっているということに気付くのに1年くらいかかりました……。
それが分かってからはGoogle検索などもしやすくなり、本も探せるようになったので、物凄く勉強が捗るようになりました。

なお、「競プロの問題では出てこないけど、競プロの問題の解説記事で出てくる言葉」もバンバン載せています。
逆に、「アルゴリズム」に属すると思われる言葉は省きました。

言葉（文系でも多分聞いたことはある）編

・素数、素因数、素因数分解、自然数、約数、倍数、公約数、公倍数、ユークリッドの互除法など … 小5～中1あたりの「数と計算」「数と式」、数学A「整数の性質」。難しくなってくると整数論という（？） 競プロでは超メジャー分野なので、基本、とりあえず出てきたワードで検索すれば目的のものに辿り着く
・方程式、方程式の解、連立方程式、不等式など … 中1～3の「数と式」「関数」、数学Ⅰ「数と式」、数学Ⅱ「いろいろな式」など。かなり多岐に渡るので、この辺りを押さえようと思うと、Google検索つまみ食いじゃなくて、入門本を1冊買った方がいいと思う
・関数（y=axみたいな形のやつ）、二次関数、関数の最大値・最小値・極大値・極小値、定義域、値域など … 中1～3の「関数」、数Ⅰ「二次関数」、数学Ⅱ「指数関数・対数関数」「三角関数」、数学Ⅲ「極限」
・累乗、べき乗（冪乗）、階乗 … 似たような言葉ですが、累乗・べき乗は数学Ⅱ「指数関数・対数関数」に関わる言葉で、階乗は数学A「場合の数の確率」で出てくるものです。また、「べき（冪）」はもっと一般化して難しい意味で使うこともある（理解していません）ようなので、「なんか意味が噛み合わないな？」と思ったらそういうことかもしれません。
・数え上げ、順列、重複順列、組み合わせ、独立、条件付き確率、nCk、nPk、n!、玉と仕切り、写像12相などなど … 数学A「場合の数と確率」、難しくなると「組み合わせ論」などと呼ばれるらしい

・平均値、中央値、期待値、分散 … 中1～3「資料の活用」、数学Ⅰ及び数学活用「データの分析」
・期待値の線形性 … 緑Diffくらいから出てきます。これは式変形に関することなので、式変形編に載せます。

言葉（文系だと聞いたことないかも）編

・二項定理、二項係数、パスカルの三角形 … nCkに関する言葉でもあります。数学A「場合の数と確率」、数学Ⅱ「いろいろな式」。これは競プロ頻出で良記事が多いので、Google検索で詳しい記事を探すのが良いです。
・単調増加（減少）関数、凸関数、凹関数など … 二分探索とか三分探索を勉強すると出てきます。これは関数の形に関する言葉ですが、上記の関数関連分野の中の数学Ⅰ～数学Ⅲエリアで出てきます。
・微分、積分、導関数、二階微分など … 数学Ⅱ「微分・積分の考え」、数学Ⅲ「微分法」「積分法」、難しくなると解析学というらしい？
・ベクトル … 数学B「ベクトル」。ただ注意が必要で、大学以上の数学である「行列（線形代数学）」に踏み込んだ意味で使われている場合がある。また、線形代数学に深く踏み込んで、「代数学」を勉強しないと分からない意味で使われている場合もある。
・行列、線形代数、掃き出し法、消去法、拡大係数行列、行列累乗、連立一次方程式の解、ピボット、行基本変形、基底、標準形、ベクトル空間、行列のrankなど … 数学B「ベクトル」の発展型で、大学以降の「線形代数学」分野。また、線形代数学は「○○代数学」とついている通り、離散数学の「代数学」をかじってないと分かりにくい話がたまに出てくる感じがしてます。
・漸化式 … DP（動的計画法）でよく出てきます。数学B「数列」。
・数列、等差数列、等比数列、等差数列の和、一般項など … 数学B「数列」、数学Ⅲ「極限 - 無限等比級数の和」など
・極限、lim、収束、発散など … 数学Ⅲ「極限」「微分法」「積分法」
・有理化 … 中3「平方根」
・log、ln、対数、自然対数、e、ネイピア数、指数、次数など … 数学Ⅱ「指数関数・対数関数」、数学Ⅲ「微分」（※自然対数、e、ネイピア数 及び ln が数Ⅲ範囲。とはいえ、数Ⅱの知識があればGoogle検索で雰囲気は掴めると思います）

言葉（離散数学）編

・逆元（a^(-1)） … 逆元は、「mod P でのあまり」を求める時に出てきて困った人が多いと思います。離散数学の「代数学」分野です。
・単位元（e）、モノイド、半群、群、環、体、類、代数系、多項式、交換律、結合律、二項演算、「閉じている」などなど … 競プロ記事で出てきて「何だこれ」ってなる文系が多いと思います。セグ木の抽象化でも出てきます。これも離散数学の「代数学」分野です。この辺りの「いやなんか全然聞いたことないけど！？」みたいな単語がバシバシ出てくる記事があったら、代数学を前提としてることが多いです。ちょっと大変ですが、これをやると一気に読める記事が増える（特に、青色以上の猛者の記事が読める）のでオススメです！ 競プロの楽しみが広がります！
・フェルマーの小定理、位数、原始根 … これも「代数学（整数論の方でも出てくると思う）」の一分野に属しているようです。代数学の「剰余類」「巡回群」辺りの言葉をやった後なら、なんとか話が追えると思います。
・∀、∃、集合、有限集合、要素、元、部分集合、∈、「N」「Z」「Q」「R」「C」、和集合、積集合、補集合、ド・モルガンの法則など … 数学Ⅰ「数と式 - 数と集合」にもありますが、離散数学の「集合」分野で詳しく出てきます。
・真、偽、命題、述語論理式、論理和、論理積、否定、¬、∧、∨、論理式、同値、⇔、逆、裏、対偶、十分条件、必要条件、必要十分条件、数学的帰納法、背理法など … 数学Ⅰ「数と式 - 数と集合」にもありますが、離散数学の「論理」分野で詳しく出てきます。また、明確には表れてこないものの、この辺りの話を追っていると、「競プロer（というか数学に強い人）の書く日本語」の特徴に少し慣れることができ、問題を読む速度が上がります。
・直積集合、直積、関係、（関係の）合成、同値関係、同値類、代表元、剰余類、写像、関数、定義域、値域、像、単射、全射、全単射、置換、置換の積、濃度、加算濃度、可算集合、無限集合、離散集合などなど … 特に写像や関数、○射あたりは、数学に強い人の記事でよく出てきます。離散数学の「関係と写像」です。
・上界、下界 … 代数学の「順序集合」に出てくるようですが、まだやっていないため不明です。
・グラフ、点、頂点、辺、端点、ノード、多重辺、部分グラフ、次数、隣接行列、経路、パス、道、閉路、サイクル、有限グラフ、連結、非連結、完全グラフ、2部グラフ、完全2部グラフ、マッチング、フロー、木、全域木、根、根付き木、葉、枝、深さ、彩色、頂点彩色、オートマトンなどなど … 離散数学の「グラフ理論」に出てくる言葉です。と言っても、グラフ理論は明らかによく出てくるので、勉強している人が多いと思います。まだ「ちょっと難しそうだしな～」と思って尻込みしている人がいたら、分かりやすい記事がネットに沢山転がってますので、ぜひ勉強してみてください。

「式変形」編

・長い式を（x+1)(x^2+x+1) みたいに分けるやつ … 因数分解（中3 数と式）
・「√」に関わる式変形 … 中3「数と式 - 平方根」、数学Ⅱ「指数関数・対数関数」
・「x^k（xのk乗）」に関わる式変形、特に「x^(a+b) = (x^a)*(x^b)」的なやつ … 緑～水Diff以降でかなり出てくるので、重要な式変形だと思う。中3「数と式 - 平方根」、数学Ⅱ「指数関数・対数関数」
・「Σ」に関わる式変形、特に「○○数列（○○級数）の和なので、以下の式になる」的なやつ … 数列の問題めちゃくちゃ多いので、これは重要。数学B「数列」、数学Ⅲ「極限 - 無限等比級数の和」など
・「Σ」や「期待値（E）」や「平均」に関する式について、「線形性」「期待値の線形性」を使って…… と言いながら、なんかサラッと式を分解してくるやつ … 水コーダーを目指すに当たっては押さえた方がいい式変形だと思います。数学B「数列」分野ですが、教科書等で簡単におさらいしたあと、「期待値の線形性」などでGoogle検索して、詳しく解説した記事を読んだ方がいいと思います。
・←この記号（Π。πの大文字） … 式変形ではないですが、詰まりがちなので入れました。大体の数学記号はGoogle検索で記事が出てくるのですが、コイツはすごく面倒で、どうやら「代数学の集合や関係の分野で出てくる『直積集合』」の意味と、「数列で出てくるΣ（総和。数列の全てを足し算したもの）の掛け算バージョン（総乗。数列の全てを掛け算したもの）」の2つの意味があります。どちらの意味になるかは、文脈次第です……

「図形っぽいやつ」編

・諸々の公式を理解するための前提 … 中1～3「図形」
・三角比、正弦定理、余弦定理など … 数学Ⅰ「図形と計量」
・図形に関する方程式、円と直線、点と直線の距離、線分の交差判定などなど … 数学Ⅱ「図形と方程式」。数学Ⅰ「図形と計量」、数学Ⅱ「図形と方程式」を必要に応じておさらいしつつ、「幾何ライブラリを作る」というような記事を探すといいと思います。
・三角関数、sin、cos、tan、asin、acos、atan、ラジアン、rad、θなどなど … 数学Ⅰ「図形と計量」、数学Ⅱ「図形と方程式」、場合によっては数学Ⅲ「平面上の曲線と複素数平面」も？
・複素数、複素数平面、直交座標、極座標、ベクトルの回転などなど … 数学Ⅲ「平面上の曲線と複素数平面」
・凸包 … 大学レベルの図形だと思うけどよく分かってません

筆者のバックグラウンド

ひとくちに文系出身・数学苦手erと言っても、その中でも多種多様な人がいるわけで、その辺り私はどうなの？ というところを紹介しておきます。
ざっくりまとめれば、「ほんとは苦手というほどでもないけど、競プロ界ではかなりの数学弱者の部類。特に整数については弱者だった」です。

経歴、仕事など

名古屋大経済学部出身、専攻は経済史（まあ歴史です）、今は30代の公務員（事務職、つまりいわゆる普通の公務員）です。
前職は高校生相手の学習塾講師（英語と、たまに国語）でした。

入試の二次試験には数学があったので、数ⅡBまではある程度勉強しました。
とはいえ、英語と国語で点数を稼いだ（前職で高校生に英語と国語を教えていることからも分かる通り）ので、数学が得意とは到底言えません。

とは言え、一般社会における意味での数学苦手erかというと、そういうわけでもないです。
全国模試の偏差値で言うと 50 ~ 60、センター試験本番の点数で言うと、数ⅠA 88点、数ⅡB 36点です。

学習塾時代の経験を踏まえてできる限り客観的に自己分析をすると、「数学をしっかり勉強したとは到底言えないけど、できないわけでもない、フツーの（ただし高校の国公立文系志望コース（≒数ⅡBの履修）を経た）比較的真面目な文系大学生」くらいであり、「競プロ界では、物凄く不利とまでは言わないが、かなり不利な部類」というところではないでしょうか。

また、ゆとり教育（というものが昔ありました）世代のため、数学Aの「整数の性質」（合同式、mod、ユークリッドの互除法……）を学んでいませんでした。
これはかなり競プロで苦労する原因になりました。

ただ、名古屋大学の二次試験で、なぜかやたらめったら確率漸化式（漸化式の仲間）が出題されていたので、確率と漸化式は結構頑張って勉強していました。
それは競プロにも生きていると思います。

「初中級者が解くべき過去問精選100問」「上級者が解くべき過去問精選100+50問」チャレンジシート

@e869120 さんが公開されている、上を目指す競プロerが解くべき過去問精選100問（100+50問）。
水～黄コーダーを目指すAtCoderユーザーが解くべき問題セットとして、多くの人に使われています。

元記事へのリンク

・初中級者が解くべき過去問精選 100 問

100問全部解けたら、水色どころか青色くらいの実力が付くと思います。

・上級者が解くべき過去問精選 100 + 50 問
※「上級者が解くべき過去問精選」の「100問」の部分は、「初中級者が解くべき過去問精選」と共通です。

50 問全部解けたら、ほぼ確実に黄色コーダーレベルのアルゴリズム活用能力がついたといって良いでしょう。

そろそろ私も過去問精選に挑戦しようと思い、挑戦状況を管理するチャレンジシートを作成しました。
同じように「これから過去問精選にチャレンジしたい！」という方がいましたら、ぜひご活用ください。
（自分用なのでレイアウト等は適当です。）

過去問精選は初級者には難しい問題も多いと聞くため、挫折せず着実に進められるよう、
各サイトの難易度推定や、@868120 さんご本人のコメント（チャレンジ問題とか、基本問題とか）を記載しました。
問題のカテゴリ分けの部分は、普段は非表示にして精進しようと思っています。

精選100+50問チャレンジシート

精選100+50問チャレンジシート（One Drive上のファイルへのリンク）

↓中身は以下のような感じです

初中級者が解くべき過去問精選100問

上級者が解くべき過去問精選100+50問（100問は初中級者と共通）

シートに記載した難易度（難易度推定）の出どころ

東京海上日動プロコン2020 E問題 - "O(rand)" 解説

ARC級のE問題、本番中のACは 88人 / 223人提出 で、Diff 2726 と、かなり難しい判定の出ている問題です。
実際、考察や実装自体は難しかったですが、要求される知識自体は「包除原理」以外には高度なものは無く、緑コーダーの知識でも十分解けるものでした。

こういった問題がコンテスト中に解けると一気にレートが上がると考えているので、どんどん攻略していきたいですし、折角攻略したので共有したいと思い、解説します。

問題

E - O(rand)

提出コード

概要

N個の相異なる非負整数 A1, A2, ..., AN があって、そこから 1～K個の数を選ぶ。
その選び方のうち、次の2つの条件を満たすような選び方の組合せは何通りあるか。

(1) 選んだ数の全てについてビットごとにANDをとっていき、答えがSになる
(2) 選んだ数の全てについてビットごとにORをとっていき、答えがTになる

制約：1<=N<=50, 0<=Ai, S, T < 2^18, Ai≠Aj など

大雑把な方針

そのまま考えると非常に難しいので、3パートに分けます。

パート1：コーナーケースの処理

(1) S[d]=1, T[d]=0 となっているような桁があれば、条件を満たすのは無理なので答えは 0
(2) S=T のときを処理（S=T=AiとなるようなAiがあれば答えは1, なければ答えは0）

※(2)の説明
S=Tの時、全ての桁でS[d]=T[d]=0 or S[d]=T[d]=1 となっている。
すると、S[d]=T[d]=0となっている桁は0しか選べないし、S[d]=T[d]=1となっている桁は1しか選べない。
ということは、例えば S[d]=T[d]=00101010 なら Ai も 00101010 しか選べないが、制約から各Aiは相異なるので、そのようなAiは「1つしかない（＝選び方1通り） or 1つもない（選び方0通り）」のどちらかであるため。

パート2：簡略化パート

2つの「除外」を行って、問題を簡略化します。
※ [d] はd桁目のビット を表すことにします。

(1a) S[d]=T[d]=0 となっているような桁では、Ai[d]=0 となっているような Ai しか選べないので、各 Ai のうち、Ai[d]=1 となっているものを除外してしまう
(1b) S[d]=T[d]=1 となっているような桁では、Ai[d]=1 となっているような Ai しか選べないので、各 Ai のうち、Ai[d]=0 となっているものを除外してしまう
(2) (1)の結果、S[d]=T[d] であるような桁は、「残っているどのAiを選んでもいい」状態になっています。つまり、「どうでもいい桁」になりました。ということで、桁を削除してしまいます。

※桁の削除の仕方
ビットの計算に慣れていないと、ここが若干面倒だと思います（私は面倒でした）。
説明するのは大変なので、提出コードを参考にしてください。
ざっくり言えば、削除したい桁より上を割り算で取り出し、それらの桁を1つ下げ、削除したい桁より下を余りの計算で取り出し、それらの桁をそのままくっつけました。

簡略化された問題のまとめ

一旦、簡略化された問題を整理しておきます。

・全ての桁について、(S[d], T[d]) = (0, 1) になった
・つまり 残っている各Aiについて、ANDをとると0000…、ORをとると1111… となるような組合せの数を求めたい

この2行目は、以下のように言い換えられます。

・ANDをとると0000... ：「0を1つ以上選ぶ」
・ORをとると 1111...： 「1を1つ以上選ぶ」

つまり

・どの桁を見ても、「0も1もそれぞれ1つ以上」選ばれているような選び方の数を求めたい

このように問題を整理できました。
あとは、本題パートで解いていきたいと思います。

※余事象：真正面から求めるのがつらい時、「場合の数全体 - そうじゃない場合の数」で求める。例：例えば0を1つ以上選ぶ組合せなら、「全ての選び方 - 0を1つも選ばない選び方」など

（注）S[d], T[d] = (0, 1)の桁が一つもないパターンはあるか？
条件に当てはまる桁が一つも無いパターンがあると、コーナーケースになるんじゃないか？
と、不安に思う方もいると思いますが、そういったコーナーケースは残っていません。
何故なら、(1, 0) パターンがある場合はパート1で処理されており、「全てが(0, 0) or (1, 1)」というパターンについても、そのパターンは「S=Tの場合」とイコールなので、やはりパート1で処理されているからです。

---

パート3：本題パート

（再掲）
・どの桁を見ても、「0も1もそれぞれ1つ以上」選ばれているような選び方の数を求めたい

「1つ以上選ぶ」という言葉が出てきて、にわかに余事象っぽくなってきました。
ただし、単なる余事象では計算できない複雑な組合せのため、そのような場合に使う「包除原理」を活用します。

なぜ普通の余事象で解けないか

一応、まずは普通の余事象で考えてみます。
（強い人からすると、いやいやそりゃ無理でしょという感じだと思いますが、慣れていないと違いが分かりにくいと思うので）

ある桁について、「0も1もそれぞれ1つ以上選ぶ」の余事象ですから、「0だけ選ぶ」か「1だけ選ぶ」のどちらかです。
これらの場合の数は、その桁の「0の数」と「1の数」が分かれば解けそうです。

しかし、ある1つの桁についての選び方の場合の数が分かっても、その選び方は具体的に分からないので、次の桁を考える時に「この選び方は前の桁の選び方と矛盾するのか？しないのか？」というところが分かりません。
こんな風に、余事象の考え方だけではどうしようもなくなってしまいます。

包除原理での考え方（立式）

（包除原理についての詳しい説明は ここ や ここ などを参考にしてください。）

包除原理は、「沢山の条件の『当てはまる・当てはまらない』を組合せて、最終的に目的の場合の数を求める」みたいなことができます。

その際、「条件の組み方」が大事になりますが、今回は、以下の2条件（A, B）を組み合わせることにします。

（条件A）Ai[d]が 全部0 もしくは 全部1 となるような選び方（0, 1のどちらか一方だけから全部取る）
（条件B）Ai[d]は 何をどう選んでもいい

※どうやって条件A, Bを持ってきたのか？
元々ある条件は、「(a)全部0 (b)全部1 (c)0と1混合」の3つであり、今回求めたいのは「全ての桁において (c) となる選び方」です。
ということは、包除原理も余事象の延長なので、(c) の余事象 つまり「0と1が混ざっていない＝全部0もしくは全部1」を条件にするというわけです。

この2条件を各桁に組み合わせて（包除原理に基づいて式を立てて）、問題を解きます。

＜出来上がる式＞
（例：残り桁数 4桁, 残っているAiの数 5）
求める答え = BBBB -BBBA -BBAB -BABB -ABBB +BBAA +BABA +BAAB +ABBA +ABAB +AABB -BAAA -ABAA -AABA -AAAB +AAAA
（包除原理の式は、満たす条件が奇数の場合「-」になり、偶数の場合「+」となる）
※BBAB といった書き方は、各桁が条件A（全部0か全部1）と条件B（何でもいい）のどちらに当たるか（及びその時の場合の数）を表します。

各項の計算法

包除原理によって式を立てることができましたが、各項の計算もなかなか難しいです。

例えば、ABAAの具体的な数（4, 2, 1桁目は全部0or全部1で、3桁目はどちらでもいいような選び方）というのは、どのように求めればいいでしょうか？
これは、下図のように「グループ分け」を考えることで求められます。

上図は、ABAA となるような選び方を示しています。
まず、Bの桁は何でもいいので、無視します（灰色で塗りつぶしました）。
次にAの桁ですが、これらは「各桁毎に、全部0か全部1」ですから、「取り出した組合せが、縦に見て全部0or全部1」になっていないといけません。
つまり、図中で色分けした1つのグループ（青、橙、緑、紫）のうち、1つのグループのみから選ぶ（グループをまたがって選ばない）必要があります。

ということは、ABAA の具体的計算は、以下のようになります。

ABAA = [青グループから1～K個選ぶ選び方] + [橙グループから1～K個選ぶ選び方] + [緑グループから1～K個選ぶ選び方] + [紫グループから1～K個選ぶ選び方]

もちろん BABB や BBBA などについても同じなので、これが計算できれば先程の式の答えは求められる＝問題に答えられる ということになります。

---

ここからの計算も私（緑コーダー）にとって簡単ではなかったですが、
ここから先は、茶上位～緑レベルの人がウンウン唸って頑張れば十分に解ける難易度だと思いますので、説明しないでおきます。
（提出コードにコメントを沢山入れましたので、必要になれば参考にしてください。）

ヒントとしては、「連想配列（map）のバケツ」「マスクビット」などがあります。

その他の注意点

・nCkの計算時、オーバーフローさせないように注意。私はここで割と詰まりました。

ABC169-F "Knapsack for All Subsets" DPの遷移式について

本番中は解けなかったのですが、苦手なDPに少しずつ慣れてきたこともあり、O(N^2 * S) のTLE解までは書くことができました（それでも十分嬉しい）。

解説を読み、O(N*S) の解法が理解できて解説ACできたので、自分の場合のDPの発想手順と、想定解のDP遷移式を解説します。

問題

F - Knapsack for All Subsets

概要

長さNの正整数列 A1, A2, ..., AN と 正の整数Sが与えられる。
そこから、数列Aの部分集合であって和がSとなるものの個数を求める…… なら分かりやすいが、今回は「数列Aの部分集合Tの部分集合Uであって和がSとなるものの個数を求める」という問題。

提出コード

DPを発想するまで

いやいやいや部分集合の部分集合で？？？ 和がS？？？ なに？？？ となって3分くらい頭がフリーズしました。

ちょっと落ち着いた頃、Uは、Aの部分集合の部分集合と言うと分かりにくいが、まあとにかくAの部分集合であることには違いない、と考え始めました。

すると、難しいところは置いておいて、とにかく「部分和問題」という典型の一種であり、DPで解ける可能性が高いのでは、となりました。
（ナップサックという問題タイトルがヒントになっています。F問題に挑戦する人だと大体ナップサックDPを書いたことがあるんだと思いますが、自分は名前だけ知っていて、概要は知らない状態でした。とにかく検索すれば見つかります）

O(N^2 * S) の TLE解

（一応載せてみましたが、TLE解なので読まなくていいです）

さて、DPを考えてみます。（残念ながらこれはTLEします）
求めたいのは条件を満たす部分集合Uの数なので、それをDP配列に入れる値にすることにします。
Tのことは今は考えるのを一旦停止しています。

DP[i][j][k] := 数列の左端から Ai までのうち j 個の数を使って作る、和 k となる部分集合の数
※どうせTLE解なので、遷移式は省略します。気になる場合は提出コードを見てください。

このDPを求められれば、最終的に、DP[N-1][1][S] ～ DP[N-1][N][S] の部分に、「数を1個～N個使って和がSとなる部分集合の数」が入ります。

これはそのまま答えにはなりませんが、ここに計算を加えると答えを出すことができます。
例えば数列Aの要素数が5(A0, A1, A2, A3, A4)で、和がSとなるある部分集合Uに使った数の個数が3(A0, A2, A4)だったとします。
この部分集合Uが属する部分集合Tは、(A0, A2, A4), (A0, A2, A4, A1), (A0, A2, A4, A3), (A0, A2, A4, A1, A3) の4種類です。
部分集合Tのパターンをよく見ると、これは Uに選ばれなかった各要素（今回ならA1, A3）それぞれにつき、「Tに入れる」「Tに入れない」の2パターンがあるので、
部分集合U の要素数 が j だった時、それが属する部分集合 T の種類は 2^(N-j) 種類 と求められるわけです。

これを使うと、
(答え) = Σ(j:1~N) dp[N-1][j][S] * 2^(N-j) % MOD　となります。

とはいえTLEなので、頑張ってDPの次元を落とす（ [ ] の数を減らす）ことになります。

次元の落とし方

さて、ここからどうやって [ ] を減らすか……
自分は残念ながら解説を読んで理解したのですが、恐らく考え方はこうです。

とにかく減らす対象は[i]か[j]か[k]かしかない、つまり「何個目までとったか」をなくすか、「何個とったか」をなくすか、「和がいくつになったか」をなくすかの3種類しかない。

そう考えてみると、「何個目までとったか」をなくしてしまうと、次にどれを取るか選ぶのに毎回O(N)かかってどうしようもないですし、「和がいくつになったか」をなくしてしまったら、どう考えてもにっちもさっちも行きません。

すると、「何個目までとったか」をなくすしかありません。

---

さて、そうすると先程のTLE解で最後に行った「2^(N-j)をかけて答えを出す」ができないので、答えそのものをDPに入れないといけないことになります。

ここで、若干放り投げ気味だった「部分集合T」と向き合うことになります。

今回の「答え（個数）」は何か？

実は今回の難しいポイントは、問題文の「答え」が何のことか、がわかりにくいことだったのじゃないかと思っています。

集合1~Nの空でない部分集合Tとして考えられる全てについてのf(T)の和…… などと言われると「何やねん！」とシャーペンを投げたくなりますが、
ゆっくり考えると、「『和がSとなるようなAの部分集合U』と『 U を含むような より大きい部分集合T』の組合せの数」と言い換えられます。

この「組合せ」という考え方を利用すると、遷移式が理解しやすくなると思います。

次元を落としたDP

それでは、O(N*S)のDPの解説に入ります。
TLE解では DP[i][j][k] としましたが、そこから「何個とったか」つまり [j] がなくなったので、DPはこうなります。

DP[i][k] := 数列の左端から Ai までのうちから、自由な個数の数を選んでつくる、『和 k となる部分集合U』と『Uを含むようなより大きい部分集合T』の組合せの数

このようにDPを組んだとき、まずは下の図のようになることを、よく考えて理解してください。
これが理解できれば、遷移式の理解もすぐです。

ちなみに、DP[0][2以降] = 0 です。そのようなUの数は0だからです。

恐らく「つまずきポイント」となるのは、数が「1」ではなくいきなり「2」から始まることだと思いますが、これは、Uの種類が1つであっても、それを含むようなTの数は複数あるからです。
このように、Uの種類とTの種類の増え方の違いを意識することがポイントです。

遷移式

以下の図のようになります。

いや、なんか図がグッチャグチャになってしまいましたが……。

DP[i-1][k-Ai] から、DP[i][k] にいく遷移は、UもTも「新しくAiを加える」の1パターンなので分かりやすいのですが、「×2」のところが難しいポイントだと思います。

これはともかく具体例を見ていただくしかないですが、
U には何も入れていないのに、T のパターンが2倍になる！ という遷移になっています。

なぜこうなるか？ というと、AiをUに入れなくても、Tには入れることができるし、入れないこともできることが理由です。

T:{} -> {3} と {1} -> {1, 3} がTにAiを入れた遷移 （これで ×1）
T:{} -> {} と {1} -> {1} がTにAiを入れない遷移（これで ×1）

この2種類の遷移があるため、「×2」が発生したということになります！

---

どうでしょうか？

分からないところがあれば、ぜひご質問ください。

提出コード

https://atcoder.jp/contests/abc169/submissions/13929206atcoder.jp

AtCoder 茶～緑はバケツ（バケット）道を極めるべき！

まえがき

茶コーダーの皆さん、緑色になりたいですよね。
緑コーダーの皆さん、水色になりたいですよね。

それで、DPを勉強しなきゃ、DFS・BFSに慣れなきゃ、数学力をつけなきゃ、ライブラリを充実させなきゃ、と色々努力してると思います。

私は基礎力向上のため AtCoder Problems でDifficulty（diff）が低い問題から埋めているのですが、
茶diff上位の問題（650～700強）を解いていくうち、

「茶～緑上位で一番重要なのは、バケツとmap（連想配列）を使いこなすことじゃないか！？」

と思い始めました。

そのくらい、この辺りのdiffでバケツ・mapを活用できる問題が多いのです。
茶diff上位の問題がある程度サクサク解ければ緑どころか水色も見えるので、この辺りの問題をしっかり固めるのは重要です。
実際、私は前回のABCではのD問題（茶diff上位でした）を比較的素早く解くことができ、1382パフォが出ました。えへん。

また、前回のABC-E ・(Bullet) では、mapにpairを入れて賢く使うというバケツ道（バケツを使いこなすプログラミング術のこと）中級のテクが問われ、なんとこれは青diff中位（1836）だったのです。
その問題については記事を書きましたが、数学要素があったり、数え上げが難しかったりするとはいえ、mapが賢く使えればかなり正解に近付けた問題です。

問題の例

ここで、「この記事で言うバケツ（バケット）ってバケットソートのこと？ 何を指してるの？」という疑問を持った方や、「そもそもバケツって知らないんだけど……」という方もいるかもしれませんが、一旦置いておきまして、バケツを賢く使う＝バケツの使い方で特に差がついた問題を中心に挙げてみます。
※「バケツが使える問題」というだけの条件だと、無数にありすぎて挙げきれないためです。

ABC061-C Big Array / Diff : 745（茶）
これはバケツ（バケットソート）そのものの問題。
2017年のコンテストとはいえ、この問題まで素早く（例えば合計30分で）解ければ、パフォーマンスはなんと1349です。

AGC002-B Box and Ball / Diff : 693（茶）
なんとAGC-B！
しかも8位のsnukeさんが解いていない問題！！（もちろん、他の問題に時間をかけていたといった事情もあるでしょうが……）

ARC033-B メタ構文変数 / Diff : 704（茶）
公式解説PDFだと「ソートして二分探索」とか「setを使う」とか書いてあります。
二分探索は難しそう。setは集合演算のやり方とか計算量が大丈夫か（私は）分からない。
でもバケツなら？　シンプルに素早く書けます！

ABC159-D Banned K / Diff : 504（茶）
これ、私は詰まってしまって、解説を読んで通しました。（ていうか解説を読んでも最初分かりませんでした。）
なぜ詰まったのか？ バケツの有用性を知らなかったからです。
（diffは低いですが、上2つより難しいと思ったのでこの位置に載せました。）

ABC168-E ・（Bullet） / Diff : 1836（青）
青ォォォォいッ！！　説明不要！！

ABC167-D Teleporter / Diff : 705（茶）
Kが物凄く大きいですが、「鳩の巣原理」とバケツを使って周期性を見つけることで解ける問題です。
これは多分緑～水以降でたまに出てくる典型なんじゃないかな？ と予想しています。
（まだ緑以降のdiffをあまり埋めていないため、本当かは知りません）

AGC036-B Do Not Duplicate / Diff : 1770（青）
これは「バケツを使って解く問題」とは言い難いですが、「高難易度帯ではバケツの考え方は活用できるのが当たり前」という例として挙げてみました。
周期性を使う解法とダブリングを使う解法があるようですが、周期性を使う場合は、上と同じく鳩の巣原理とバケツが使われます。
詳しくは、この記事にまとめました。

---

あとは…… けんちょんさんのブログの「バケット」カテゴリを見てください。（ひどい）
ていうか、けんちょんさんがカテゴリ作って13個も問題突っ込んでる時点で、私が記事書かなくても超重要に決まってますよね。
drken1215.hatenablog.com

バケツって何？

一番有名なのは「バケットソート（バケツソート）」ですが、この記事ではもう少し一般化した意味で使っています。

ここで言うバケツとは「配列の使い方」のことです。
くだけた言い方をすれば、バケツとは「各要素を表すラベルを貼った、各要素の情報を入れる配列」です。

（細かく言えば、「ある数列（または集合）の要素そのものを配列の添字（もしくは連想配列のキー）として使い、配列の値には出現個数や状態などの『その要素の情報』を入れる考え方」です。）

基本のバケツ

具体例と図で説明します。

＜問題例＞
「以下の入力が与えられます。各Kjにつき、数列A内に存在する各Kjの個数（Kj = AiとなるようなAiの個数）を出力してください。」
N, M, X
A1, A2, ... , Ai, ... , An （1 <= Ai <= X）
K1, K2, ... , Kj, ... , Km
（1 <= N <= 10^5, 1 <= M <= 10^4, 1 <= X <= 10^5）

＜入力例＞
5 3 9
2 1 2 7 4
7 2 3
（答え：1 2 0）

制約が小さければ、以下のような配列を作って、2重ループを回せばいいです。
（Kjについてループを回し、その中でAiについてループを回してKj=Aiとなるものを数える）

しかし、これは計算量がO(N*M)なので、制約が大きければTLEとなってしまいます。

---

ここで、バケツを導入します。
下図のような配列を用意して、配列の添字（0～9）を、Aiの要素としてありえる数（0～9）に見立てて、バケツ配列の値には「添字の値が登場した個数」を入れます。
（Ai=0は実際には登場しませんが、これで大丈夫）

このようにすると、今回の制約下でも間に合います。

具体的には、まず上記の配列を全て初期値「0」で作成してから、入力を受け取る時に、配列[Ai] の値に1ずつ足していきます。
入力が終わると図のような状態になりますが、ここで配列に入っている {0, 1, 2, 0, 1, 0, 0, 1, 0, 0} という値が、0～9の登場回数を示しています。
あとは、j = 1～Mについてループを回し、各ループ内で配列の値を1つずつ取り出せば、ACとなります。

＜疑似コード＞
配列 buckets[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
for ( i : 0 to N ) buckets[Ai] += 1;
for ( j : 0 to M ) 出力( buckets[Kj] );

---

ちなみに、下図のようにバケツ配列の上から順に値を取り出すと、自動的に昇順ソートが完了します。

これがバケットソート（バケツソート）です。
配列の要素にN回の +1 をして、あとはただ取り出すだけなので、O(N) でソートが完了します。

＜問題例＞
ABC061-C Big Array / Diff : 745（茶）

バケツの有用性

このように、バケツは要素の個数を数える問題に強いです。
せっかくなので応用をきかせたいところですが、他にはどのような問題に使えるのでしょうか？
具体的には「バケツの賢い使い方」の章でやるとして、ここでは一般的性質について書きます。

＜バケツにできること＞
・沢山ある「要素」のうちのどれかについての「情報（個数、状態、Yes/Noなど色々）」をO(1)で高速に取得・更新できる

ということで、「沢山の要素の集計」をしたり、「沢山の要素から特定の要素を選んで何度も処理をする」といったことに強いです。

＜具体的な応用例＞
・添字が順番に並んでることを利用してバケツソート
・要素を集計して、確率や場合の数などの数え上げに利用
　→（応用）要素をグループに分けて数え上げ（ABC168-Eのイワシや、平方分割）
・鳩の巣原理＆隣接リスト表現で周期性を利用（後述）

バケツの注意点

このように、単純なやり方で非常に大きな計算量改善をすることができるバケツですが、弱点もあります。

＜弱点１＞
・とりえる値の数と同じ量の添字を用意しないといけないので、1 <= Ai <= 10^9 のように数列の要素の範囲が大きいと MLE してしまう

＜弱点２＞
・値が実数や文字列など、整数以外だと添字で表現できない

特に弱点1が重要で、要素の値の制約を大きくしてバケツ対策をしてある問題も多くあります。
しかしそれはバケツの強力さを表しているとも言えます。

場合によっては、これらの弱点は解消できることもあります。
ここからは、バケツの応用例を挙げていきたいと思います。

ここからが本番！ バケツの賢い使い方

連想配列（map）でバケツを作る

そもそも連想配列はバケツの進化系と考えられます。
例えば制約が「値の範囲が -1*10^9 <= Ai <= 10^9 で通常のバケツには入れられない」というとき、連想配列なら（値の種類数さえ大きすぎなければ）何でも入れられます。

連想配列の練習問題

バケツに bool を入れる

ここから、一気に「差がつく」テクニックになっていきます！

AGC002-B Box and Ball / Diff : 693（茶）

上の問題に目を通してみてください。
すぐ解法を思いついた人は凄いですが、茶～緑では苦戦する人も多いのではないでしょうか。
（私は非常に苦戦しました。というか解説ACしました。）

この問題は、バケツを応用（以下の3つの応用を使います）して解くことができます。

1. バケツに「個数」ではなく「今の状態（各箱に入っているボールの数）」を入れる
2. バケツを2つ使う- 1つの箱につき1つのバケツしか作れない、というルールはありません。
3. バケツに「bool」を入れる

3つ目で大ヒントを出してしまいましたが、これ以上言ってしまうと解けた時の感動が無くなりそうなのでこのくらいにします。
ぜひやってみてください。
私はこの問題でバケツが本当に好きになりました。

バケツにタプルを入れる

バケツの「値」にタプル（C++ならpairやvector）を入れたり、連想配列バケツの key や value にタプルを入れるテクニックが頻出です。

ARC033-B メタ構文変数 / Diff : 704（茶）

この問題は、大雑把に言えば「AntさんとBugくんの両方が使った単語の数 ÷ AntさんとBugくんの少なくとも一方が使った単語の数」を出力する問題です。
もちろん、制約が小さければ単に集合（set）を使えばいいですが、TLEが怖いです。

そこで、このような「2つに仕切られたバケツ連想配列」を用意します。

そうして、1つ1つのバケツのvalueには pair を入れて、Antさんが使ったかBugくんが使ったら、それぞれのboolをTrueにします。

＜疑似コード＞
連想配列（key := int, value := pair) buckets[N];
for ( i : 0 to NA-1 ) buckets[i][0] = true;
for ( i : 0 to NB-1 ) buckets[i][1] = false;

これで、あとは連想配列の value を前から順番に見ていって、{true, true}だったら「または」と「かつ」の両方に入れ、{true, false}, {false, true} だったら「または」だけに入れれば完了です。
前計算 O(NA+NB), 最後の計算部分 O(NA+NB) で解くことができました。

---

＜発展問題＞
ABC168-E ・（Bullet） / Diff : 1836（青）
なかなか恐れ多い難易度の問題ですが、バケツ連想配列が使えれば、あとは少々の数学と、丁寧な組合せ計算（あと、MODに気を付けないといけないですが……）の問題です。
この問題を解いて、私はますますバケツ信者になりました。

バケツで「組み合わせ」を見つける

AtCoderなどの競プロの問題では、「何らかの条件を満たす組み合わせ」に関する問題が多いです。
例）条件を満たすものの個数、条件を満たす組のうち最小の○○、など

実は、このタイプの問題とバケツは非常に相性が良く、頻繁に解法として使われます。
「何かの組み合わせだ……」→「バケツか！？」と考えると、割と早く解法にたどり着く気がします。

---

基本的な考え方について、架空の問題例で紹介します。

＜問題例＞
N人が相互に全員とじゃんけんをします。各人（i : 1～N）の出せる手が決まっている（H1～HN）時、各人i～Nが勝てる相手の人数を出力しなさい。
＜解法＞
これは結局、ある人iについて、（ i , iが勝てる相手 ）という組み合わせの総数を求めるという「組み合わせの問題」です。
よってバケツを考えます。
＜バケツの使い方＞

すごく単純なように思えますが、緑～水くらいのDiffでも、これをするだけで解ける問題が結構あり、頭に入れておくべきだと感じます。

---

また、バケツに入れたものをソートしておき、二分探索などをすることによって、より複雑な「条件を満たす組み合わせ」を求めることもできます。
先日の M-SOLUTIONS プロコンオープンでは、F問題として、まさにこの考え方で解ける問題 / Diff : 2004（黄）が出ました。
（実装を簡単にするため、解説PDFを参考に座標の回転を行っていますが、座標の回転を行わなくてもACすることができると思います。）

「自分が衝突してしまうような飛行機を探す」というのは、結局「自分がじゃんけんで勝利できる相手を探す」と本質的に変わらず、あとは「どのようにバケツ分けをすればいいか」という問題と言えます。
もちろん、変数の範囲その他諸々の理由で、明確にバケツ分けができない問題も多くあると思いますが、今回は座標の範囲が限られており、直角にぶつかる場合をうまく工夫すればバケツ分けができる問題でした。

私の提出コード

＜問題例＞
ABC152-D Handstand 2 / Diff : 1063（緑）
これは正直、バケツ分けをして数えるだけの、バケツ好きとしては非常に簡単な問題ですが、
結構最近のコンテストにも関わらず、緑Diff中～上位になっています。
なんとお買い得な問題でしょうか。

ARC048-B - AtCoderでじゃんけんを / Diff : 1281（水）
先程のじゃんけんの例を少し複雑にした問題です。

M-SOLUTIONSプロコンオープン2020-F - Air Safety / Diff : 2004（黄）
この回はE問題も難しく、F問題に置かれたせいでDiffが実際以上に上がっている面もあると思いますが、本質的にはバケツ（と座標を上手いこと工夫する）だけで解ける問題で黄色Diffというのはなかなか非自明です。
茶～緑はバケツを極めるべきという記事ですが、水～青くらいでもまだまだバケツ道を極めるには至っていないのかもしれません。

バケツに移動先を入れる ～鳩の巣原理と周期性～

（現在執筆中です）

ABC167-D Teleporter / Diff : 705（茶）

AGC036-B Do Not Duplicate / Diff : 1770（青）
現在執筆中です