http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4726957 最長増加部分列の計算量は 小さい数字に貪欲に更新することで部分列の長さが増加する可能性を増やす。二分探索したときendであれば、その数字を追加することで長さが1増える。更新するべきか…

https://atcoder.jp/contests/abc135/submissions/15552119 桁DPで処理する 初期値は dp[0][0] = 1 繰り返しは rep(i, 1, Size(S)) 更新は if (S[i] == '?') rep(j, 0, 13) rep(k, 0, 10) dp[i][(j * 10 + k) % 13] += dp[i - 1][j] など 出力は dp.back()[5…

https://atcoder.jp/contests/abc137/submissions/15521766 x日後を前から見るのでなく、後ろから見たほうが条件が狭くなる （後ろから）x日以内に報酬を貰えるバイトのうち最大を貪欲に選べばok x日後を前から考えるより後ろから考えたほうが条件が狭くなる…

https://atcoder.jp/contests/abc138/submissions/15508780 根の値 < 部分木の値に必ずなる⇒累積和 制約から各クエリを以下で処理しなければならない。根の値が伝搬されて必ず「根の値 < 部分木の値」になることから累積和になっていることが分かる。DS_Nyaa…

https://atcoder.jp/contests/abc140/submissions/15507196 https://atcoder.jp/contests/abc140/submissions/9416948 任意区間に対して人の位置を反転させた上で向きも反転させる 反転したとき「連続文字列をグループ化した個数」と「幸福度」の増減に着目…

https://atcoder.jp/contests/cpsco2019-s1/submissions/15476330 DPでシミュレーションして数列の一般項を求める 初期値は dp[0][0] = dp[0][1] = 1 繰り返しは rep(i, 1, 3 * N) 更新は dp[i][0] += (dp[i - 1][1] + dp[i - 1][2]); など 出力は Sum(all(d…

https://atcoder.jp/contests/cpsco2019-s1/submissions/15470682 Kが小さいのでK種類の商品を全探索する 大きい硬貨から貪欲に支払いを構成する Nが32なので全探索はできないが、Kが最大6なので個の全探索は出来そうという気持ちになる。小さい硬貨で支払う…

https://atcoder.jp/contests/abc084/submissions/15381403 素数テーブルと2017に似た数字の前処理をしておくことで各クエリをにする 制約から各クエリを以下で処理する必要がある。範囲クエリをで処理する方法として累積和を使いたくなる。素数テーブルを用…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4693828 素因数分解の計算量は Nを2から順番に割っていって因数を求める。このとき割る数はまでで良い。もし、以上の数字aで割れるとすると商bは以下になる。もし、aとbが両方以上だとN < abとなるた…

https://atcoder.jp/contests/joisc2010/submissions/15253528 最小全域木のうち最長の辺をK-1個だけ取り除いてK個のグラフに分ける K個の開催都市を何処にするかは無関係（一度に複数人通行させれば料金一律なので） 辺をK-1個だけ取り除くことでグラフをK…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4213849 クラスカル法による最小全域木の計算量は 最小全域木は全ての頂点を通るグラフの最短距離となる。最小全域木のアルゴリズムにはプリム法とクラスカル法がある。実装方法は蟻本p100に載ってい…

https://atcoder.jp/contests/abc141/submissions/15353189 priority_queueのtop、pop、pushを多用しリアルタイムに最大値を取得、更新する この類の問題は買う値段などを決め打ちして二分探索するような定跡もあるが、今回はokとなる値が不明となるため二分…

https://atcoder.jp/contests/abc142/submissions/15352890 https://atcoder.jp/contests/abc142/submissions/15351653 因数分解した因数の組み合わせが約数になる 素因数分解した因数の個数 ⇔ 約数のうち素数の個数 「互いに素でなければならない」という条…

https://atcoder.jp/contests/abc145/submissions/15338725 ベクトルの個数が分かれば格子状の最短経路問題と同じ (i+1, j+2)と(i+2, j+1)のベクトルs,tの個数が分かっていれば、格子状の最短経路問題と同じ。ベクトルの個数は連立方程式で求まる。連立方程…

https://atcoder.jp/contests/abc162/submissions/14903598 gcd=t の決め打ち 緩和した条件なら簡単に計算できる 降順に答えを求めるとメモ化が役に立つ 上記結果とメモ化した答えを足したり引いたりすることで設問の答えを得る ではTLEするので、gcd=tとな…

https://atcoder.jp/contests/abc147/submissions/13626753 https://atcoder.jp/contests/abc147/submissions/15303781 「集合nと集合mの片道は全部でn×m個」＝「完全二部グラフ」＝「辺の数はn×m個」 制約からが許されないので、ビット桁ごとに処理して計算…

https://atcoder.jp/contests/abc151/submissions/13015367 https://atcoder.jp/contests/abc151/submissions/15292083 スタート地点が#の時どこにも移動できないので何もせず結果を返すことに注意 制約が縦横20しかないことからやが許される。つまり、スタ…

https://atcoder.jp/contests/abc152/submissions/15125443 条件X∧Yを満たす値の個数を二次元配列[X][Y]で管理する 先頭X末尾Yとなる値の個数をbcount[X][Y]とする。1からNまで線形処理すればbcount[1][1]からbcount[9][9]までの個数は得られる。あとは先頭S…

https://atcoder.jp/contests/abc012/submissions/10345521 max(始点v[i]から目的地v[j]への最短経路)がminになるバス停v[i]を見つける つまり全点対間最短経路を求めればok 最大値の最小値が答え。つまりバス停について、に引っ越した時の最大値、に引っ越…

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 をデクリメントすると得られる 円環はデータを余分に増やすと実装が楽になることが多い 制約から二分探索で処…