A問題1分、B問題1分、C問題23分、の3完だった。 また調和級数に負けた。しかし、今回は完全に数学力不足で考察しても気づかない類の問題だったので、どうしようもなかった。国立二次の問題集を買って整数問題の例題を全て解いておいたのだが、その程度だとD…

https://atcoder.jp/contests/cpsco2019-s3/submissions/9723196 同じアルファベットが連続することからランレングス圧縮しておくと楽 アルファベットが3文字しかないので、連続部分列をグループ化したときアルファベット遷移は2×3=6通りしかない。6通りの組…

https://atcoder.jp/contests/cpsco2019-s4/submissions/13597815 退屈Tを固定すると書き換え回数changeが計算できる 書き換え回数の条件で二分探索することで退屈Tが求まる 退屈TをO(1)で考えるのは難しいので、退屈Tが許される範囲を二分探索で求める。退…

https://atcoder.jp/contests/joi2008yo/submissions/10331886 計算量 が許されるので、毎回ダイクストラ法をする グラフアルゴリズムの基本問題。制約から辺の本数が最大で、頂点数が最大でしかないので、でもTLEしない。したがって、注文票クエリ毎にダイ…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4186995 単一始点最短経路はダイクストラ法 ダイクストラ法の計算量は 到達できない頂点はINFを出力するので、各頂点を十分大きな値infで初期化する。スタート地点を0として、ダイクストラ法で最短経…

https://atcoder.jp/contests/abc128/submissions/15677953 制約が10しかないのでbit全探索する ループの最後まで行けたらans++と書くと実装が楽。 任意の電球1個について「配線を辿ってスイッチの個数のmod2がpかどうか」はで判定できる。電球が10個しかな…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4610462 bit全探索した通りの答えをメモ化 制約を見ると20しかないのでbit全探索できそうと予想する。全ての組み合わせを調べても最大通りしかないので、全探索しても処理できる。ただし、各質問毎に…

https://atcoder.jp/contests/abc160/submissions/11321133 ダイクストラ法は単一始点から全ての終点までの最短経路を求める ダイクストラ法は 基本的にとにしか辺が存在せず、それとは別に追加される辺が1本しかない。そのため、辺の本数が頂点数と殆ど同じ…

https://atcoder.jp/contests/abc161/submissions/14393212 bit全探索より柔軟な再帰全探索に慣れる サンプル４がヒントで最大で3234566667しかないので10桁まで全列挙すれば良い 隣接桁の絶対値が1以下だけ処理するのでより遥かに少ない計算量になる 再帰関…

A2分、B1分、D30分、の3完だった。大学入試の進数変換問題が簡単すぎて、その程度の知識ではABCでは通用しない。今回はEまでdif8K以下という特殊なセットなので、運悪くレーティング下がるのは仕方ないかもしれない。が、流石に2週間連続でレーティングが下…

https://atcoder.jp/contests/abc161/submissions/14637689 dif16Kなので天才的なプログラミング的思考力が必要 働く日が一意に決まる条件および線形時間で処理するロジックの発想が難しい 前からの貪欲は自明なので気づける 前からの貪欲と後ろからの貪欲を…

https://atcoder.jp/contests/abc160/submissions/11401406 上位X個、上位Y個以外は無視できる。 無色のリンゴを基準にして交換を考えることで まず、赤のリンゴX個と緑のリンゴY個以外は無視する。美味しさの総和を最大化するには最も小さい赤か緑のリンゴ…

https://atcoder.jp/contests/cpsco2019-s4/submissions/13596303 チーム内の最小を決め打ちすると[最小, 最大]の範囲が通りある あとは通りの上記範囲に対してnCrを考えれば答え チーム内のを決め打ちするとも決まり、[min, max]の範囲が通りあると気づける…

https://atcoder.jp/contests/tkppc4-1/submissions/13233825 単調増加、減少をカウントするためフラグの初期値を0にして、単調増加になったらフラグを1、単調減少になったらフラグを-1にする 絶対値の差 はマスjとマスiの距離（のようなイメージ）になるの…

https://atcoder.jp/contests/abc007/submissions/14492447 最短経路を記録するので更新してないグリッドだけ選んで移動していく BFSの基本問題。BFSは移動先座標をキューに入れて実現する。4方向に移動しながら、現在いる座標+1で移動先の座標を更新してい…

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)の値が変わらないことに着目しつつ、…