https://atcoder.jp/contests/abc132/tasks/abc132_e 前提知識 BFS 解説 https://atcoder.jp/contests/abc132/submissions/6191952問題の解き口が分からない場合は、より簡単な問題に取り組むのも方針の1つである。 今回はけんけんぱだから難しいのであり、…

https://atcoder.jp/contests/abc132/tasks/abc132_d mod上での二項定理 解説 https://atcoder.jp/contests/abc132/submissions/6191711この問題はmod上で二項定理を解く方法が分からないと解くことができない。 そちらをまずは勉強しよう。 今回のちょうどi…

https://atcoder.jp/contests/abc132/tasks/abc132_c 解説 https://atcoder.jp/contests/abc132/submissions/6191460まずはソートしよう。 ソートして、N/2-1個目とN/2個目の間を見れば整数Kの取りうる範囲が分かる。 N/2-1個目の数をA, N/2個目の数をBとす…

https://atcoder.jp/contests/abc132/tasks/abc132_b 解説 https://atcoder.jp/contests/abc132/submissions/6191382piは多くても18通りであり、これは全探索ができる。 piを全探索して、条件を満たすかどうか判定して数え上げよう。 条件を満たすかを判定す…

https://atcoder.jp/contests/abc132/tasks/abc132_a 解説 https://atcoder.jp/contests/abc132/submissions/6191286c++のstringは実はソートができる。 ソートをすると、ASSAはAASSのように同じ文字は同じグループでまとまってくる。 あとは、条件を確かめ…

https://yukicoder.me/problems/no/845 前提知識 bitDP 制約からbitを使えと語りかけてくるので、bitDPする。 状態遷移を考えると、最後に訪れた駅も記憶しておくのが良さそう。 dp[msk][lst] := まだ訪れていない駅の集合mskで最後に訪れた駅がlstのときの…

https://yukicoder.me/problems/no/844 前提知識 動的計画法更新最適化（SegTree） 解説 https://yukicoder.me/submissions/354954何から始めようかという問題である。 フローっぽい雰囲気もあるが、レベルが2.5だし、制約も10^5なので違うだろう。 天才最適…

https://yukicoder.me/problems/no/843 前提知識 素数列挙 あるといい知識 素数定理 解説 https://yukicoder.me/submissions/354876以下の実装では関数として隠蔽してしまっているが、 makePrimes(N) := [2,N]の素数の集合を返す makePrimesBool(N) := [2,N]…

https://yukicoder.me/problems/no/842 解説 https://yukicoder.me/submissions/354661解くためのアルゴリズムとしては、各小銭について何枚とるかというのを全探索すると、 O(ABCDEF)で、これは10^6なので間に合う。 問題が実装なのだが、rep記法とかを使っ…

https://yukicoder.me/problems/no/841 解説 https://yukicoder.me/submissions/354599実装問題。 isDonichi(s) := sが土曜日曜どっちかならtrue という関数を作っておいて、それを使って判定して、答えていこう。 string S1, S2; //-----------------------…

有理数問題とは 精度の関係でdoubleで保持するのではなく、有理数の形（分数の形）で計算結果を保持したほうがいいときがある pythonとかで高精度でやる方法もあるし、有理数ライブラリを持っておくと有利な場面もある 問題 AC Grand Election SRM761 Div1 E…

https://atcoder.jp/contests/abc131/tasks/abc131_e 解説 https://atcoder.jp/contests/abc131/submissions/6082165こういう構築系は、最小ケースと最大ケースを考えるのが、常套テクである。 最小ケースは完全グラフを作ればK=0にできる。最大ケースはスタ…

https://atcoder.jp/contests/abc131/tasks/abc131_d 前提知識 区間スケジューリング 解説 https://atcoder.jp/contests/abc131/submissions/6077645この問題はほぼ区間スケジューリング問題である。 区間スケジューリングを解くには終了時間が最も早い仕事…

https://atcoder.jp/contests/abc131/tasks/abc131_c 解説 https://atcoder.jp/contests/abc131/submissions/6076233常套テクとして「区間[a,b]の個数は区間[1,b]の個数-区間[1,a)の個数」というのがある。 （今日の北陸アルゴリズム勉強会でtorusさんが言っ…

https://atcoder.jp/contests/abc131/tasks/abc131_b 解説 https://atcoder.jp/contests/abc131/submissions/6074212食べるリンゴを全探索する。 N個のリンゴすべてを材料としてできる味と、リンゴi以外を材料としてできる味の差は L + i - 1である。 差の絶…

https://atcoder.jp/contests/abc131/tasks/abc131_a 解説 https://atcoder.jp/contests/abc131/submissions/6073193条件にある通りに連続する数字があるかを判定する。 3通りあるので、ループしてもいいし、そうじゃなくてもいい。 string S; //-----------…

https://yukicoder.me/problems/no/79 解説 https://yukicoder.me/submissions/353422cnt[i] := レベルがiであるユーザー数 を計算しよう。 あとは、これを使って、cnt[i]が最大で、かつ、その中でiが最大のものを答えると答え。 int N, L[101010]; int cnt[…

https://www.facebook.com/hackercup/problem/589264531559040/ 提出 前提知識 構文解析 解説 https://codeforces.com/gym/102249/submission/55747916とっても難しそうな問題に見えるので、エスパーしよう。 x=false, x=trueの時を評価して、どちらも同じ結…

https://www.facebook.com/hackercup/problem/2426282194266338/ 提出 解説 https://codeforces.com/gym/102249/submission/55747853Leapfrog: Ch. 1に加えてyesの条件が増えるが、bが2以上であれば、カエルは行ける。 ABB.. AB.B. .BAB. .B.BA ..BBA .ABB.…

https://www.facebook.com/hackercup/problem/656203948152907/ 提出先 解説 https://codeforces.com/gym/102249/submission/55747583A以降のマスの個数をn, 最小限必要なBの個数をbとすると、以下のような表になる。 n b 2 1 3 2 4 2 5 3 6 3これをみると、…

https://atcoder.jp/contests/abc130/tasks/abc130_e 動的計画法 動的計画法 解説 https://atcoder.jp/contests/abc130/submissions/6001273mod10^9+7で制約が10^3くらいなので、dp[10^3][10^3]かなーと経験則的に思う。 2つの数列があって、dp[s][t]である…

https://atcoder.jp/contests/abc130/tasks/abc130_d しゃくとり法 解説 https://atcoder.jp/contests/abc130/submissions/6000372微妙に何から手を付ければいいか分からない。 こんなときは全探索対象を探す訳だが、ここにも典型テクがある。 条件を満たす…

https://atcoder.jp/contests/abc130/tasks/abc130_c 解説 https://atcoder.jp/contests/abc130/submissions/6000248ABC300点問題なので、なるべく単純に考えることにする。 この問題はある種の構築問題である。 構築問題の典型テクとして「理論値の最大値を…

https://atcoder.jp/contests/abc130/tasks/abc130_b 解説 https://atcoder.jp/contests/abc130/submissions/6000104跳ねる動きをシミュレートする。 N≦100なので、シミュレートしても間に合う。 int N, X, L[101]; //-------------------------------------…

https://atcoder.jp/contests/abc130/tasks/abc130_a 解説 https://atcoder.jp/contests/abc130/submissions/6000049問題文の通りに分岐して解く。 int X, A; //-----------------------------------------------------------------------------------------…

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b 前提知識 UnionFind 解説 https://atcoder.jp/contests/diverta2019-2/submissions/5943792なにか全探索対象を探す。 どこを全探索しようかなと色々考える。 1つ目を全探索すると、自由度…

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_a 解説 https://atcoder.jp/contests/diverta2019-2/submissions/5943412まず、みんなボールは1個以上受け取るので、先に渡しておこう。 最大-最小を最大化したいのだが、最小は0にすればい…

https://yukicoder.me/problems/no/840 前提知識 行列累乗によるDP高速化 DPテク11「文字列の部分列の個数を添え字に持つ典型」 解説 https://yukicoder.me/submissions/352662Nが大きい、かつ、数え上げということなので、まずは行列累乗路線で考える。 「…

https://yukicoder.me/problems/no/838 前提知識 DPテク17「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」 解説 https://yukicoder.me/submissions/352656まず、前の問題が解けないと解けないので、こちらを理解する。 get(L, R)…

https://yukicoder.me/problems/no/837 前提知識 「マンハッタン距離の差の和の最小値は中央値に集めるとき」 解説 https://yukicoder.me/submissions/352655マンハッタン距離の総和の最小値の地点は中央値であるというテクを使う。 高さの変更先は2つあると…