ABC解説記事解説 - Motsu_xe 競プロのhogeやfuga

こんにちは、もつ鍋です。本年の目標の1つとして、ABCの解説記事を毎回書いてみる、というものを設定いたしました。次回から書いていきたいと思うのですが、それに当たって、記事の扱いについて今回一筆したためたので、次回以降の解説記事の参考にしていただければと思います。

方針

ここでeditorialと同じことを書いたところで仕方ないので、それなりにABC早解きがある程度(ある程度)得意である自分の生の思考を垂れ流しにし、どのように考えて解答に至るのかの参考になるようなものにしたいと思います。コンテスト中のIQが下がった状態での解法を書くので、もっと良い解法があることも多いですが、それはeditorialや他の記事を読んでください。
どういう思考の順番で解法に至ったのかを重視したいので、途中で多少間違っている思考が混ざる場合もありますが、それは注意書きした上でそのまま書きます。
このような性質上、問題自体は既に理解している状態で読んだ方がより良いかもしれません。とはいえ解説を名乗っている以上、解説としての機能も最低限はあるように書くつもりです。
以下に解説のフォーマットを掲載します。

X - 解説の見方*1

思考

コンテスト中に行った思考を垂れ流します。これがそのまま解説として機能する程度には詳細に書こうと思っています。

実装例

コンテスト中に書いたものを多少読みやすく整形したC++14 (GCC 5.4.1)の実装例を掲載します。
一応下にコンテスト中の提出へのリンクもつけておきます。
カス実装のときはその旨書いておくので、実装は参考にしないでください。
基本的に

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

はされていると思って読んでください。それ以外のマクロなどは特に前提としないつもりですが、普段私が使っているマクロ(カス)は

#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

だけですが、もしこれを使っちゃってたらごめんなさい。コメント入れてくれれば直します。
またmodint構造体など、書いていたら冗長になってしまう構造体などの定義は省略することがあります。定義が気になる場合は、コンテスト中の提出をご覧下さい。

終わりに

思考の言語化は、思考の整理や高速化に役立つんじゃないかと思い、需要も0ではないでしょうし、このような記事を書くことにいたしました。慣れないうちはカス記事を量産してしまうとは思うのですが、そこはご容赦を。改善点などあれば、コメントなどでバシバシ指摘してくださると大変嬉しいです。

*1:見出しで問題名を書きます。