https://atcoder.jp/contests/sumitrust2019/submissions/14461892 制約を見て計算量の少ない要素の全探索がないか探す意識を持つ 文章の通りにSから暗証番号を作ると大変なので、暗証番号が1000通りしかないことに着目する。暗証番号の範囲が[000,999]しか…

https://atcoder.jp/contests/abc095/submissions/14420440 複数の要素を包含している物を全探索すれば、他の要素がO(1)で決まるのでコスパ高い AピザとBピザを全探索するとだが、ABピザを全探索すると残りのAピザとBピザが減算でO(1)になるのでで済む。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4587473 幅優先探索はキューを使う キューはFIFO 幅優先探索の基本。注意点として、他の頂点から遠回りして更新済み頂点に辿り着いたとき再び更新しないように if (res[to] != -1) continue; が必要。…

https://atcoder.jp/contests/abc157/submissions/13434967 BITで点加算と範囲取得が BITを複数本もつデータ構造に慣れる 文字列の長さがでクエリ数があることから、合計を求めるクエリ1個につきまたはで処理したいという気持ちになる。そこで、Binary Index…

https://atcoder.jp/contests/abc156/submissions/13470562 人の移動パターンは関係ないので意識してしまうと一生答えが出ない 移動すると空部屋が増える傾向にある→移動した人を部屋の外に集めて空部屋以外に再分配する重複組み合わせ どの部屋を空部屋にす…

https://atcoder.jp/contests/abc155/submissions/14397627 四捨五入的な考え方で最善の枚数が得られそうで得られないので意外と難しい 支払い金額と繰り下がりをdpで全て全探索する 初期値は dp[0][0] = 0; 繰り返しは rep(i, 0, Size(N) - 1) rep(d, 0, 2)…

https://atcoder.jp/contests/abc154/submissions/14394556 桁DPは状態 EQ (equal: 同値) と LT (less than: 未満) を持つのが定跡 初期値は dp[0][0][state::EQ] = 1; 繰り返しは rep(j, 1, Size(N)) rep(k, 0, K + 1) 更新は if (k + 1 <= K) dp[j][k + 1]…

A1分、B4分、C13分、の3完だった。 今回のような簡単なセットを落とすようだと一生緑のまま。ゴミ。 A - Five Variables https://atcoder.jp/contests/abc170/submissions/14295713 頑張ってタイピングする。 B - Crane and Turtle https://atcoder.jp/conte…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4416724 互いに行き来できる=頂点の到達可能性=BFSかDFSで到達した頂点に印を付ける 互いに行き来できるということは、グリッドをグラフに変換したときに閉路が存在するということなので強連結成分分…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4573439 問題設定が長いので見落としがないよう注意 最短距離（最短到達時間）で更新するとき、更新済み頂点を continue するのを忘れずに書く DFSの基本問題。DFSで木構造の各頂点を処理する時は①か…

https://atcoder.jp/contests/abc106/submissions/14176996 約数は積なので素因数分解が定跡 約数の個数は素因数分解した因数の(指数+1)の積で得られる。 素因数分解の計算量はなので、全探索しても全体計算量でTLEしない。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4570639 を減算でに落とす定跡は低dif帯で頻出 制約が緩いので3重ループでもTLEしないと思うが、3個目の数は減算で確定するので2重ループに減らす工夫も出来る。重複なしなので1個目の数iをrep(i, 0, …

https://atcoder.jp/contests/abc153/submissions/14123891 個数無制限ナップサックDPは一次元で処理できる（ただし、繰り返しは二重ループ） 配るDPで制約オーバーするときは貰うDPでも制約オーバーで実装する infはオーバーフローしない程度の値（例えばと…

https://atcoder.jp/contests/abc152/submissions/12833879 全ての積が同じ値になる⇔全てBiで割り切れる⇔lcm(Ai) lcmがインフレするときは素因数分解を利用する 大きいAiと小さいBiの積にする必要があると分かるが、更に詰めていくと「全ての積が同じ値（な…

https://atcoder.jp/contests/abc151/submissions/12468410 Σ(X- Y) ⇔ ΣX - ΣY max(x)とmin(x)の決め打ち 素直に実装すると一生処理が終わらないので、線形処理できるように工夫する。max(x)とmin(x)を決め打ちすればf(x)の値が変わらないことに着目しつつ、…

https://atcoder.jp/contests/abc148/submissions/14100952 初めてコンテスト本番で解けたE問題。 積の数字の個数→素因数分解の考え方は大事（今回は素因数分解しない） 2の因数は大量にあるので、5の因数の個数だけ調べれば良い 数弱だと数式の意味は分かり…

ABCDEFGとJの8完で58点、中級まで点数が1問足りなかった…(´・ω・`) 全体的に、普段の競技プログラミングで出題される数学的傾向の強い問題ではなく、数学は使わないけどプログラミング特有の発想、考察、実装力を問う問題が多い印象を受けた。競技プログラミ…

https://atcoder.jp/contests/otemae2019/submissions/8913567 答えが単調減少する = 原因が何か考える ans = min(ans, nyaa) で処理できる 答えが単調減少していくことから原因が何か考えると、数列BにおけるA[i]の個数 > 数列BにおけるA[i+1]の個数 のとき…

https://atcoder.jp/contests/abc147/submissions/12449956 数値の範囲が程度で小さいときはビットで表現する定石がある データ範囲をビットで表現すると 数値の加減算=ビットシフト で処理できる 各マス赤か青か2択あるので素直に実装するとの組み合わせに…

A1分、B2分、C2分、D18分、の4完で前回に引き続き目標の水色パフォが出た。 A - Multiplication 1 https://atcoder.jp/contests/abc169/submissions/13787127 頑張ってタイピングする。 B - Multiplication 2 https://atcoder.jp/contests/abc169/submission…

https://atcoder.jp/contests/otemae2019/submissions/13761829 逆転の発想で「1箇所に集める」と考える 制約からまで処理して良いと分かる。問題文のとおりに「任意の駒を任意のマスに移動させる」とすると整理しづらいので、計算量から予想して逆転の発想…

https://atcoder.jp/contests/abc145/submissions/12428154 商品を1個だけ手に持てるナップサックは通常DPと逆順DPを組み合わせると暗記 繰り返しは rep(i, 1, Size(nyaa)-1) rep(t, 0, T) 出力は ans = max(ans, dp1[i - 1][t] + dp2[i + 1][T - 1 - t] + n…

https://atcoder.jp/contests/ttpc2019/submissions/13679593 xor 演算は移項できる A xor B = X ⇔ B = X xor A 「xor 演算は（ビットサイズが同じなら）X以上のB → X以下の値2個 に分解できる」と暗記する つまり B = X xor B' (X < B, B' < X) が構築でき…

https://atcoder.jp/contests/abc144/submissions/13628299 答え（が条件を満たすかどうか）で二分探索をする Kが無ければ簡単でAの昇順とFの降順を掛け算するのが最善になる。Kがある場合は値の大きいAを優先して減らせば良いが、求めたい最小値以上に減ら…

https://atcoder.jp/contests/kupc2019/submissions/13635953 K=1のときは有名で以下が答えになる 天秤の片方にしか分銅を載せられないなら 天秤の左右に載せられるなら K=1のときは有名で「バシェの分銅問題」という名前が付いているらしい。 ただし、今回…

https://atcoder.jp/contests/abc143/submissions/12257779 ワーシャルフロイド法を使ってショートカットを追加 補給回数の新しいグラフを作る 任意の頂点で燃料を満タンにリセットするため、単純な最短距離が最善とはならない。ワーシャルフロイド法を使う…

https://atcoder.jp/contests/kupc2019/submissions/13604182 初期値は dp[0]=0 繰り返しは rep(i, 1, Size(newItem)) rep(j, 0, n * Pow10(4) + 1) 更新は if (0 <= j - newItem[i].first) dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - newItem…

https://atcoder.jp/contests/abc142/submissions/11902212 初期値はdp[0]=0 繰り返しは rep(i, 0, M) rep(j, 0, Pow2(N)) 遷移は dp[next] = min(dp[next], dp[j] + key[i].a); 出力は dp[Pow2(N) - 1]; 制約からbitDPと分かる。 各鍵key[i]と宝箱の空き状…

https://atcoder.jp/contests/dp/submissions/11937787 初期値は rep(j, 0, 10) if (j == CtoL(K[0])) dp[0][j % D][stEQ] += 1; など K以下の整数全てとmod(D)全てで繰り返しは rep(i, 0, Size(K)) rep(j, 0, 10) rep(k, 0, D) 状態は state::LT (less than…

https://atcoder.jp/contests/abc141/submissions/11639951 ZアルゴリズムはS[i]からの部分列と先頭からの部分列の最大一致文字数を返す Zアルゴリズムの計算量は ZアルゴリズムはS[i]からの部分文字列が先頭S[0]からの文字列と何文字一致するかで返す。した…