ABC195

■A - Health M Death
if (0 == H % M)

■B - Many Oranges
全探索

■C - Comma
n桁の数に打たれるカンマの数は、(n - 1) / 3

■D - Shipping Center
制約が小さいのでどうにでもなります
価値の大きな荷物から順番に、その荷物を入れられる最小の箱に詰め込んでいく

■E - Lucky 7 Battle
dp[i][j]:= N - iターン終了時点で、mod7がjの状態に持っていければ高橋くんが勝てるのならばture
そうでないならfalse

初期値は、dp[0][0] = true
高橋くんはいずれかの遷移で高橋くんの勝ちパターンに入れるならtrue
青木くんはいずれの遷移でも、高橋くんの負けパターンに入るならtrue
とdpを遷移させ
最終的にdp[N][0] = trueなら高橋くんが、falseなら青木くんの勝ち

つまるところXor Battle(agc45-A)

■F - Coprime Present
Eを解き終えたときには残りが20分のため考察が終わらず
B-Aが小さいので、共通の素因数として持つ可能性がある素数は高々20種類
なので状態数が(B-A)*(2^20)程度なら十分に高速にbitdpの処理ができるので
dp[i][j] = i個目まで見て、jの立っている素数はすでに選択したものに含まれている選び方
とする。

■感想
B,C,Dがいつもより少し重たくないですか？
EとFは配置が逆なら正解者数も大きく変わりそう。

ARC-C問題埋め(041～050)

■41:C - ウサギ跳び
方針的には簡単だが、実装が少し面倒
端っこの処理を上手にやらないと事故が起きる。

■42:C - おやつ
ナップサック
一番安いものを覗いて予算内に収まればいいので
入力情報をソートしてdpを使い回すといい

■43:C - 転倒距離★★★
配列Aは0,1,2,3,4....と読み変えて問題がない
それに合わせてBもマージする。
そしてAB間の転倒数が偶数なら成立、奇数なら非成立なのもわかる。
BからAを転倒数の半分を超えないとこまで復元すると求めたいものが出来る

注意しないといけないのはN=10^5の転倒数はintで収まらないことがあること
このせいで謎のREとTLEが出て困った

■44:C - ビーム
XとYは独立で考えていい
dpは更新が少ないので使い回す。

■45:C - エックスオア多橋君
aとbを結んだ経路のxorはaからxと、bからxを結んだそれぞれのxorのxorと同じ(共通部分が打ち消されるため)
答えがintで収まらないことがあること
x=0のときにa==bは除く必要がある

■46:C - 合コン大作戦
片側をsortし、もう一方をそのsortに都合のいいようにsortする
その中から条件を満たす最弱を割り当てる
(注)
早い：auto it = st.lower_bound(men[i].second);
遅い：auto it = lower_bound(st.begin(), st.end(), men[i].second);

■47:C - N!÷K番目の単語★★★
前から決めていく
使われていない数の何番目を使うかを決めていく
あとはセグ木上で二分探索

■48:C - 足の多い高橋君★★★
回分の繰り返しになることにわかればいい
わかればそれの繰り返し二乗法

■49:C - ぬりまーす★★★
強連結成分分解(SCC)を使う
タイプ２の条件の読み替えと、
使わない点の処理方法(頂点Nを増やして、それと双方向に結ぶ等)

■50:C - LCM 111
lcm(A,B) = A*B/gcd(A,B) = (A/gcd(A,B))*(B/gcd(A,B))*gcd(A,B)
なので1000100010001みたなもののmodMでの値を行列累乗の容量で求めればいい

ARC112E - Cigar Box

E:FPS解を考える

最終的に左右に動かす数をLとRとすると
m個をL+R種類(最低一回は使用)で塗る場合の数は
[x^m](e^x-1)^(L+R)*m!であり
(e^xとm!は展開すると7!/(3!*2!*2!)みたいな形になるので求めたいものがもとまる)
最後のm-(L+R)以外は左右が自由なのと
L種とR種の順番を考慮する必要があるので
[x^m](e^x-1)^(L+R) * 2^(m-(L+R)) * m! / (L!*R!)
を求めたい

そのために[x^m](e^x-1)^kを先に考える
(e^x-1)^k = Σc(k,i)*(-1)^(k-i)*(e^x)^i
=Σc(k,i)*(-1)^(k-i)*(e^xi)
なので
[x^m](e^x-1)^k=Σc(k,i)*(-1)^(k-i)*i^m/m!
なので前計算パートがO(k^2)で収まること
本計算パートもO(k^2)で収まるので十分高速

ABC194F - Digits Paradise in Hexadecimal

コンテスト中にバグらせていた自分の解放がやっと通ったのでメモ書き。
以下の３パターンのうちの満たすものを合計する
１：Nと上からn桁は一致するNより小さいもの
２：Nより桁数が小さいもの
３：Nそのもの

その前に前計算パートで
memo[i][j]:=丁度j種類の並べ替えで作れる、サイズiの文字列の数
を求めておく。

１：Nと上からn桁は一致するNより小さいもの
上からn桁はNと一致するもの、n+1桁目はNのn+1桁目より、小さいものとして
ここまで使った文字数をusedと置くと
残りのN.size() - 1 - n桁を、必須要素のK-used種類と非必須要素のused種類で埋めればいいので
Σmemo[N.size() - 1 - n][K-used + i]*Binomial(16 - used , K-used) * Binomial(used , i)
(iは非必須要素から何種類を選択するか)

２：Nより桁数が小さいもの
Σmemo[i][K]*Binomial(16,K)*15/16;
15/16は0から始まるものを除外するため。

３：Nそのもの
これは上からsetで管理しておいてsetのサイズを見ればいい。

ABC194

■A - I Scream
if,else if,else if,else

■B - Job Assignment
N*Nを全探索
i == jだけ別処理

■C - Squared Error
展開すると
(N-1)ΣAi*Ai-ΣAi*Aj (i !=j)
なので
N*ΣAi*Ai-(ΣAi)^2

■D - Journey
等差*等比の無限和を調べると
ΣN/(N-i)

■E - Mex Min
答えの候補をsetで管理してそれの最小値を出力させる
なんてすると2.5秒かかったが、4秒制限なのでAC

■F - Digits Paradise in Hexadecimal
桁dp
コンテスト中に惜しいところまで行っていたはずなのですが
なんか微妙にあわず。
あきらめて解説AC

ABC193

■A - Discount
(double)100 * (A - B) / A;

■B - Play Snuke
やるだけ

■C - Unexpressed
なにも考えずにやると2^4と4^2が重複するので
エラトステネスの篩っぽくやるかsetに突っ込んでいく

■D - Poker
#と#の候補が9*9程度なので全パターン試して足す

■E - Oversleeping
できなかった。。。
YとQの制約が小さいので
x = t1(mod (X + Y) * 2) (X <= X + Y)
x = t2(mod P + Q) (P <= P + Q)
となるxをYQケース考えそのminが答え。
ACLの中国剰余定理 (CRT) を使う

■F - Zebraness
最小カットに帰着させる
要勉強

競技プログラミング：虚無埋め編

競技プログラミング歴：半年(初回参加は"C - Multiplication 3"のABC169)
プログラミング歴：半年
レート：青下位
最高パフォ：2300(AGC49)
AC数：1500
学歴：中卒(実質ね)

同レート帯で比較するとAC数が他の人より多いのではないかと思います。
なので虚無埋め歴を残しておきます(解説AC含む)

①ABCの全埋め
②ARCのAB埋め
③AGCのA埋め
④ARCのC埋め
⑤AOI難易度5まで埋め
⑥PAST埋め

ここらあたりまでを埋めるとだいたい1500程度が埋まり
AtCoderで必要な知識が足りないということはないと思います。

ここから更に埋めるなら以下
⑦AOI難易度8まで埋め
⑧AGCのBC埋め
⑨旧ARCのD埋め
⑩新ARCのE埋め

以下、現状の実力では予定なし
未：新ARCのF埋め
未：AGCのDEF埋め
未：AOI難易度9以降埋め
未：他サイトのコンテスト

私は、⑦に進む前に過去に解説ACしたABC-Fの復習をしていきたいと考えています
確実に解けるのがわかっている問題を埋める意味がありますか？(青から見た緑以下)
といわれるとおそらくないです。
私が律儀に埋めているのはただの性格の問題です。