昔の easy は簡単(最初に考えた方針が間違えていて, しかもサンプルが無かったら絶対 WA してた)。 問題 TopCoder Statistics - Problem Statement 解法 n = (木の本数) とします。 まず, 答えが n-1 以下になることは明らかです。一番低い木に合わせて他の…

問題 TopCoder Statistics - Problem Statement 解法 気づくべきなのは一つで, 答えは必ず K 以下になる, ということです。かっこ良く言うと鳩の巣原理からわかりますが, まぁ明らかでしょう。 ということで, dp[n][state] = n 番目の文字を見ている時点で, …

問題 TopCoder Statistics - Problem Statement 解法 正方形を作る際, 左下の点を決定すれば, どのような正方形になるかは一意に決まります。ということで, 左下の点がどこに来る可能性があるのかを考えると, これは各 (x[i], y[j]) (0 こころとしては, 位置…

SRM 400 番台の easy は簡単(ホントか) 問題 TopCoder Statistics - Problem Statement 解法 まず, 一回の白石の移動で目的の場所まで動かせたら Romeo の勝ちです。そうでない場合は, Romeo は負けないように動かします。どんなふうに石を動かしても次に St…

してやられた！という感じです。 問題 TopCoder Statistics - Problem Statement 解法 当然すべての場合を考えていると間に合わないので, 見方を変えます。ランダムに選ばれた結果, 木の高さがそれぞれ h[0], h[1], ..., h[n-1] になったとします。 整数の組…

昔の SRM は easy は簡単(と言いつつ少し迷いましたが)なのであんまり書く意味が無いような気もしないでもない。 問題 TopCoder Statistics - Problem Statement 解法 あるサイズ S で塗れるのであれば, それより小さいサイズでも塗ることが出来るのは明らか…

問題 TopCoder Statistics - Problem Statement 解法 K が小さければ, dp[n][t] = (t の人が数を変更する番の時, 残りの数が n であった場合の, 求める数) という dp で解けます。求める数というのは, もし t が勝てる場合は, 最小ターン数を, 負ける場合は …

問題 TopCoder Statistics - Problem Statement 解法 さっきと同じように dp を考えます。dp[n][s] = (長さ n の数列で, スコアの合計が s であるようなものの数) という dp が自然な気がしますが, 今回の dp では最小要素がどこにあるのか, という情報も必…

問題 TopCoder Statistics - Problem Statement 解法 cartesian tree で注目すべき特徴は, ・数列の最小の要素が cartesian tree の一番上に来る ・最小の要素を中心に, 数列は左側と右側に分かれる ・で, 左側と右側でまた cartesian tree が出来るというこ…

問題 TopCoder Statistics - Problem Statement 解法 まず, あつまるべき座標を決定した際にそれぞれのアヒルはどのように動かすのが最適かを考えてみましょう。各行にはたかだか 1 匹のアヒルしかいないので, ある一列にアヒルを揃える際は, (a, c), (a+1, …

問題 No.307 最近色塗る問題多くない？ - yukicoder 解法 すべての盤面が一色になるまでは各クエリごとに幅優先探索をして愚直に色を変えていき, すべての盤面が一色になったら各クエリごとに全体の色が変わることを O(1) で記憶しておけば良いです。計算量…

あさプロの時はものすごく混乱してて結局解けなかったんだけど, 今やったらめっちゃあっさりだった。 問題 code-festival-2015-morning-middle.contest.atcoder.jp 解法 N は奇数なので, 最後にすべてのコマが同じ色になる時コマは絶対に白色になっています…

いつ追加されるんだろうとずっと思ってたけどやっと追加されたので解きます。 問題 code-festival-2015-morning-middle.contest.atcoder.jp 解法 繰り返す文字列は左側と右側に分かれるので, 左からの i 文字と残りの右側 n-i 文字でなるべく長い, 一致する…

この問題好き(だけどプロの人は典型とか言いそう)。 問題 jag2015autumn.contest.atcoder.jp 解法 考えやすくするために「1年生の集合」「2年生の集合」「3年生の集合」という集合を表した頂点(これらを A, B, C とする)を考えます。すると, 求めるべきなの…

問題 codeforces.com 解法 Kleofáš のランクの合計が S であるとしましょう。すると, 結局求めるべきなのは n 試合終わった後にランクの合計が S 未満であるような人の数の期待値です。ということで, 以下のような dp を考えます。dp[i][j] = (i 試合終わっ…

問題 codeforces.com 解法 i と j が 2 以上離れている整数の組(i, j) について, |h[i]-h[j]|/|i-j| が L(h) として採用されることは無いです。つまり, i と i+1 について, |h[i+1]-h[i]| という値のみ考えれば良く, 他の値は無視して構わないです。あとやる…

問題 codeforces.com 解法 ごちゃごちゃ書いてますが, 一つのルートでは目的地まで距離 1 で行けて, もうひとつのルートでは距離 1 で行けないので, 何も考えず２つのルートの最短経路の最大値を取れば良いだけです。 struct edge { int v; ll w; edge() {} …

Codeforces Round #333 (Div. 2) に参加しました。D 解きたかった〜〜〜〜〜〜〜〜〜〜 問題 codeforces.com 解法 しゃくとり法的にやります。しゃくとり法のやり方はいろいろあったと思いますが, 僕はセグメント木でやりました。seg1[l, r] = (区間[l, r] …

問題 jag2015autumn.contest.atcoder.jp 解法 長さが短いものから順に処理していきます。 処理するときは, その手前のファイル, それより後のファイルをどれだけ消せるかを確かめていけば良いです。要するに貪欲法ですが, 小さい順に消していけば, 「消せる…

問題 jag2015autumn.contest.atcoder.jp 解法 各場所よりも右にある "" の数を数えると, 最終的にどちら側にたどり着くかがわかります。 例えば >>> という文字列を考えた時, 左から 4 番目にある文字 "" の数は 2 つで, これより右側にある " こんな感じで,…

問題 jag2015autumn.contest.atcoder.jp 解法 N! 通りの全探索をするだけです。 ll calc(const string& s, const string& t) { int n = s.size(); ll p = 1; for (int i = 0; i < n; i++) p *= 10; ll S = stoll(s), T = stoll(t); ll tmp = abs(S-T); retur…

問題 jag2015autumn.contest.atcoder.jp 解法 S からは交互に文字を取っていくことになるので, 要するに焦点となるのは, 「S から 1 つおきに文字を取っていったもの(s とする)と, T の部分文字列とで, 最長共通部分文字列が s に一致するかどうか」というこ…

問題 www.hackerrank.com 解法 明らかに上半分を掛け算する方に使って下半分を割り算に使ったほうが得になります。ということで, この場合の分数の値を出力すればよいですが, C++ ではこれが面倒です。これをやるためには, 下半分の掛け算と上半分の掛け算の…

前々から書く時ちょっと迷うことがあったのでメモ。整数 の素因数分解を O() でやります。 void calc(ll x, map<ll, int>& M) { for (ll i = 2; i*i <= x; i++) { int cnt = 0; while (x%i == 0) { x /= i; cnt++; } if (cnt) M[i] += cnt; } if (x > 1) M[x] += 1; }</ll,>

こういう問題でギリギリ攻められるのあんまり好きじゃないんですが… まぁこの問題の場合だとまだ仕方ないかなって感じしますけど… 問題 codeforces.com 解法 m m*n + (m-1)*(n-1) + ... + 1 * (n-m+1) となります。そこで, m の値を決め打ちして, n の値が存…

問題 abc031.contest.atcoder.jp 解法 n 番目の v, w の対応では各数字がどのような文字列に対応しているか, というのを深さ優先探索すれば OK です。具体的な実装は, dfs(m, num, cur, S) = 「n 番目の v, w の対応を調べているが, v の方は num 番目の数字…

出る気まんまんだった Codeforces Round #332 (Div. 2) は寝坊。 問題 codeforces.com 解法 ある区間 [l, r] でソートしてやるだけで全体をちゃんとソートしたことになるためには, [0, r] に含まれる数が, 全体で見た時に [0, r] 番目の数のみで構成されてい…

問題 codeforces.com 解法 桁 DP するだけです。dp[keta][carry] = (keta 目の桁で, 繰り上がりが carry であるような場合に, 和を N にするような 6 つの数字が存在するか)みたいなことをやります。各状態では, 6 つの数字を 0, 4, 7 のどれにするかを 3^6 …

問題 codeforces.com 解法 まず, 問題文をちゃんと把握します。 普通の問題と違って, この問題の場合だと, それまでに通ってきた文字列が一致していれば, 自分のターンに遷移させるマスが変わっても良いというのがポイントです。 と言ってもアレなので例を挙…

問題 codeforces.com 解法 左からいくつの荷物を取るかで全探索します。左から i 個の荷物を取るとすると, 「連続して同じ手を使うとコストが増える」というのを無視した場合かかるコストは l * (w[0]+w[1]+...+w[i-1]) + r * (w[i]+...+w[n-1]) となります…