http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4675382 全点対間最短経路はワーシャルフロイド法を使うと なので隣接行列に対して解が得られる ワーシャルフロイド法では存在しない辺の値をinfにして渡す必要がある ワーシャルフロイド法は単純な三…

https://atcoder.jp/contests/joi2015ho/submissions/15037441 https://atcoder.jp/contests/joi2015ho/submissions/15727225 循環バッファはサイズを余分に持つと実装がシンプルになる 区間DPは逆順に処理しても同値というテクニックが使える場合がある 初…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4663385 行列の順番は変えずに「どの区間の行列から掛け算するのが最善か」という問題 初期値は rep(i, 0, n) dp[i][i] = 0; それ以外は inf 繰り返しは rep(range, 1, n) rep(l, 0, n) 更新は rep(m,…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4516218 初期値 dp[0][w] = 0; 繰り返しは rep(i, 1, Size(item)) rep(j, 0, W + 1) 更新は dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - item[i].second] + item[i].first }); 出力は dp…

A問題2分、B問題3分、C問題10分、の3完だった。 頭が悪すぎて無理・・・どうすればレート上がるのか。 A - Number of Multiples https://atcoder.jp/contests/aising2020/submissions/15147907 頑張ってタイピングする B - An Odd Problem https://atcoder.j…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4516128 n-2が負数にならないようにfor文を書く 問題文に答えが書いてある。再帰関数の練習問題として紹介されることが多いが、自分はグラフ探索ライブラリをコピペするときしか再帰関数を使わないの…

https://atcoder.jp/contests/cpsco2019-s2/submissions/12179381 状態遷移図を書いてエスパーする（） Nimっぽい文章だがNimではない。状態遷移図を書くとaとbが両方奇数から始めるとAliceは勝てず、それ以外ならAliceは勝てそうという気持ちになる（適当）…

https://atcoder.jp/contests/cpsco2019-s2/submissions/15106499 括弧の深さは累積和 正常な括弧列なら累積和が負にならない 正常な括弧列なら末尾で累積和が0になる 問題文が分かりづらいが、サンプルからエスパーすると括弧の深いところに | を挟むと美味…

https://atcoder.jp/contests/abc156/submissions/10570710 r=0を含むので注意 文章を数式にするととなる。なんとなく前半が式変形できそうという気持ちになる。調べてみると二項係数の和はに等しいという情報が得られる。 https://mathtrain.jp/nikoubekijo…

https://atcoder.jp/contests/abc157/submissions/13265285 芋づる式の構造は Union-Find (disjoint-set) にするのが典型テクニック union-findと「二次元」配列を組み合わせて計算量を落とす 二次元配列で細かく区切ることで無駄を無くす i番目の人に対する…

https://atcoder.jp/contests/joi2009ho/submissions/14908294 左回りと右回りの両方を二分探索する 左回りは upper_bound 右回りは upper_bound をデクリメントすると得られる 円環はデータを余分に増やすと実装が楽になることが多い 制約から二分探索で処…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4632584 lower_boundとupper_boundを比較することで値が存在するか分かる lower_bound(x) == upper_bound(x) 値xが存在しない lower_bound(x) != upper_bound(x) 値xが存在する 制約からはTLEするので…

https://atcoder.jp/contests/abc150/submissions/14879069 std::next_permutationは辞書順に順列を列挙してくれる 「辞書順で」という問題設定になっているが、STLのnext_permutationは辞書順に順列を列挙してくれる。現在の順列が何番目かcount変数で管理…

https://atcoder.jp/contests/abc145/submissions/15054171 順列はstd::next_permutationが使える next_permutationに渡す数列はソート済みである必要がある 三平方の定理はstd::hypotが使える Nが8以下と非常に小さいので8!通り全列挙してもTLEしない。std:…

A5分、B3分、C14分、D19分、の4完だったけど、4WAして水色パフォ出なかった。 4回バグらせるだけで水色パフォ出ない高速実装コンテスト糞ゲーすぎない？ A - Payment https://atcoder.jp/contests/abc173/submissions/14978429 難しすぎて2WAした。dif1000だ…

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で移動先の座標を更新してい…