今回は出来が良かったので記事に残すことにした
結果
順位：11670人中2227位
得点※：1000点（1）
ペナルティ付き最終解答時間：54:11
パフォーマンス：1179
※（）内の数字はWAの回数
各問題の結果
| 得点 | WA回数 | 解答時点での経過時間 | |
|---|---|---|---|
| A | 100点 | 0 | 1:09 |
| B | 200点 | 0 | 3:32 |
| C | 300点 | 0 | 14:20 |
| D | 400点 | 1 | 49:11 |
| E | 500点 | 4 | - |
| F | 600点 | - | - |
レート変化
746→806 (+60)
6級に上がった
解答
A: Registration
問題要約
文字列$S$の末尾に1文字追加したものが$T$になっているか
解答
文字列$T$の末尾1文字を消したものが文字列$S$になっているか判定
コードを見る（クリックして下さい）
Submission #13020872 - AtCoder Beginner Contest 167
B: Easy Linear Programming
問題要約
1と書かれたカードが$A$枚，0と書かれたカードが$B$枚，-1と書かれたカードが$C$枚あり，その中から$K$枚選んだときの和の最大値？
解法
なるべく大きい数字が書かれたカードから選ぶ。
$K\leq a$なら和はK，$ a < K \leq a+b $なら和は$a$, $ K>a+b $なら和は$a-(K-(a+b))$
解答
上の式から分かるようにcの値は今回使わない。
コードを見る（クリックして下さい）
Submission #13026464 - AtCoder Beginner Contest 167
C: Skill Up
問題要約
$i\,(1\leq i \leq N)$ 番目の参考書は$C_i $円で，購入して読むと$ j\,(1\leq j \leq M)$ 番目のアルゴリズムの理解度が$A_{i,j}$だけ上がる。このとき，全てのアルゴリズムの理解度を$ X$以上にしたいとき，目標達成に必要な金額の最小値？（達成不可能の場合もあり）
主な制約：$1\leq N,\,M\leq 12$
解法
制約の値から，参考書の選び方$2^{N}$通りを全探索しても間に合う。bit全探索のリストの作成はproduct()関数が便利。
必要な金額を最初に十分大きな値にしておき，達成可能な選び方を見つけたらその金額に更新。どのような選び方でも達成不可能であれば最初に設定した値のままになっている。
解答
コードを見る（クリックして下さい）
Submission #13042367 - AtCoder Beginner Contest 167
D: Teleporter
問題要約
1から$N$までの番号がついた$N$個の町がある。各町にはテレポーターが1台ずつ設置されてる。町$i\,(1\leq i\leq N)$ のテレポーターの転送先は町$A_i$である。町1からテレポーターをちょうど$K$回使ったときに到着する町の番号？
主な制約：$2\leq N\leq 2\times 10 ^ 5 ,\,1\leq K\leq 10 ^ {18} $
解法
テレポーターを毎回追っていては最大$10^{18}$ 回計算する必要があるため間に合わない。
$K\geq N$の場合，必ず既に訪れた町に来ることになる。1つの町から転送できるのは他の1つの町だけであるので，既に訪れた町に来たらそれ以降は同じ町の巡り方を繰り返し続ける。
既に訪れた町に着いたらその町（以下，町Xとする。）に前回来た時から何回転送したか ($ loop $) と，最初に町1から町Xまで何回転送したか ($ cunt $) を記録する。求めたい$ K $回転送したときに到着する町は，町Xから$K-cunt$を$loop$で割った余りだけ転送した町になる。これは$K< N$でも，2回以上同じ町に来ることがあれば同じように求まる。
$K<N$の場合全ての町が初めて訪れる場所である可能性があるが，その場合は$ N $の制約から移動回数は最大$2\times 10 ^ 5 -1$なので間に合う。
解答
実装するときありがちな1ずれたりする場合は，「とりあえず試してサンプルケースで正解したら合ってる。」方法で良いと思う。
コードを見る（クリックして下さい）
Submission #13063629 - AtCoder Beginner Contest 167
E: Colorful Blocks
コンテスト中にACできなかったが，解法は合っていたので書く。
問題要約
$ N$個のブロックが横一列に並んでいる。各ブロックを$M$種類の色から選んで塗る。隣り合うブロックが同じ色で塗られている組が$K$組以下であるような塗り方は何通りか。（998244353で割った余りを答えよ。）
解説
隣り合うブロックが同じ色で塗られているような組が$k$個であるときを考える。
隣り合うブロックが同じ色で塗られているような組の位置の選び方は，$N-1$個のブロック同士の合わせ目から$K_x$個を選ぶ組み合わせで$ {} _ {N-1} C _ {k} $通り。
隣り合うブロックが同じ色で塗られているような組を1つのブロックと考えれば，$N-k$個のブロックを隣り合うブロックが違う色であるように塗っていけばよい。この塗り方は，最左端のブロックが$M$通りから選び，それ以外のブロックはその左のブロックの色以外の$M-1$通りから色を選ぶので， $M(M-1)^{N-1-k}$通り。
最後に$k$を0から$K$まで和を取ることで，求める塗り方は$\displaystyle\sum_{k=0}^K{} _ {N-1} C _ {k} M(M-1)^{N-1-k}$通り。
実装・解答
組み合わせ計算のクラスはネットに転がってるのを少し変えた感じ。
ブラックボックス化して中身は見るつもりないから余分な改行無くして圧縮してある。
逆元を使うことで高速に$ {} _ {n} C _ {r} $を求めることができる。詳しい理論はまだ理解していない。
また，$M(M-1)^{N-1-k}$は毎回計算していては時間かかるので，$k=K$のときから和を取っていき毎回$M(M-1)^{N-1-k}$の部分に$M-1$を掛けていけばよい。
コードを見る（クリックして下さい）
Submission #13110387 - AtCoder Beginner Contest 167
感想
今回のE問題はAtCoder Problemsによるとdiff1000強でかなり易化していた
そのおかげで解法は分かったが，組合わせ計算のライブラリが劣っていたのと，累乗を毎回計算していてテストケースのうち半分くらいTLEだった
まだ今回みたいな数学系の問題は全然触れていないので仕方ないけど，今後は解けるようにしたい
今回のコンテストで，緑を取り返した
精進グラフはとっくに水色まで行ってしまった
今は🧪も含めてdiffの値順に解いていて，執筆時点ではちょうどdiff1000まで解いた
今週中に緑diff残り60問解き終えて，今週末のAGCでまたレート上げたい
