問題 TopCoder Statistics - Problem Statement 解法 長さ x を決め打ちして, その長さの数列が存在するかを判定します。これができれば後は二分探索をやるだけなので判定方法を考えます。数列の 1-indexed での座標 x までの和を S[x] とすると, 条件より以…

SRM 524 の練習会に参加しました。easy だけしか解けなかったしそれも見事にひっかかって再提出しました。 問題 TopCoder Statistics - Problem Statement 解法 素数だったら (素数-1, 1) とやれば 2 回, 合成数だったら (その数字) で 1 回, というので基本…

問題 kupc2015.contest.atcoder.jp 解法 配列 B の後ろから順に対応する A の数字を決めていきます。今, B[i] に対応する A[j] を決定したいとすると, j は, まだ配列 B の要素とまだ対応していない j の中で, 一番右側にあるものを選べば良いです。これを高…

問題 kupc2015.contest.atcoder.jp 解法 計算の構文木を作って, その構文木を幅優先探索して得られる文字順を反転させると答えになります。例えば以下のような感じですね。 デバッグ用に計算結果も出力してくれます↓ int calcs(string s) { stack<int> X; int n =</int>…

こどふぇす予選問題全完出来ないのはまずそう。 問題 code-festival-2015-qualb.contest.atcoder.jp 解法 kmjp さんのコードを参考にして書きました。 解説に書いてあった通り, set で黒マスの区間を管理しながら答えを求めていけば良いです。S からスタート…

これは解けるべきだったんや… 問題 kupc2015.contest.atcoder.jp 解法 桁 DP するだけです。dp[n][diff][carry] = (n 桁目までの時点で X+N と X のビットカウントの差が diff で X+N のキャリーが carry となるような X の最小値)としてがんばります。 cons…

嘘解法っぽいけど通ってしまった。正当性あるんですかね。 問題 kupc2015.contest.atcoder.jp 解法 H > W と仮定します。とりあえず, 三角形の一つの頂点は長方形の頂点と一致し, 残りの頂点は長方形の辺と重なるようにあるはずです。 ということで, 以下の…

KUPC2015 に参加しました。 ABCDE 解いて 60 位くらいでした。うーん。 問題 kupc2015.contest.atcoder.jp 解法 方針としては, 最後に滞在する街で場合分けしてそれぞれの場合に得られるお金の最大値を求める, という感じで解きます。そのためには, 街 i に…

問題 abc030.contest.atcoder.jp 解法 python 多倍長最高で通します。 N, a = map(int, raw_input().split()) a -= 1 k = input() b = map(int, raw_input().split()) for i in range(N): b[i] -= 1 used = [-1]*N step = [-1]*N cur = a loop = 0 cnt = 0 w…

問題 dwango2015-honsen.contest.atcoder.jp 解法 dp[n][x][renzoku][f2] = (n 文字目の時点でニコニコ文字列が x 個あり, 25 という文字列が直前に renzoku 個続いていて, 直前の文字が 2 であるかどうかのフラグが f2 である場合に, 全体としてニコニコ文…

問題 TopCoder Statistics - Problem Statement 解法 CodeForces に上がっていた解説を参考にしました。codeforces.com問題を簡単化していきます。前提として, Eulerian Graph は, 「連結でありかつすべての頂点の次数が偶数であるようなグラフ」, almost Eu…

問題 TopCoder Statistics - Problem Statement 解法 n 以上で最小の素数を p1, n 未満で最大の素数を p2 とすると, 実は n 番目の task を持っている人は p2 より大きく p1 以下の番号の人に絞られます。これは, 任意の素数 p に対して p と p+1 の swap が…

問題 codeforces.com 解法 半分全列挙するだけです。覚えておく量は, 「L と M の差」, 「L と W の差」だけで十分です。 const int MAXN = 30; const int INF = 1e9; int Q[MAXN][3]; int n, N; struct quests { vector<int> select; int L, M, W; }; map<pii, quests> qs; vo</pii,></int>…

問題 codeforces.com 解法 Stern Brocot 木というのが元にあるようです。実は, この操作は Stern Brocot 木の操作とそれぞれ対応しています。 まず, Alice がみかんを, Bob がりんごを最初に 1 個ずつ持ってる状態は Stern Brocot 木では (0/1, 1/0)(分数と…

問題 TopCoder Statistics - Problem Statement 解法 典型 dp を 2 回やります。まずひとつ目の dp は, dp[l][i] = (i 番目までのブロックを使って長さ l のブロックを作る方法は何通りあるか)という dp です。 これは, まず l を i-1 番目以下のブロックを…

問題 TopCoder Statistics - Problem Statement 解法 やるだけ問題です。基本的に a と b を使うタイプのやつは割り算で ub 以下のものの個数を求めて, c と d を使うタイプのものは ub 以下のものを全列挙します。で, 全列挙したものの中で ab タイプと被る…

前のこどふぉの問題を解こうとしたら Stern-Brocot 木というのを考えるらしいので AOJ で練習してみました。 Spaghetti Source - Stern-Brocot 木既約分数を探索するのに都合が良さそうですね。 問題 Rational Irrationals | Aizu Online Judge 解法 Stern B…

問題 codeforces.com 解法 lca を使って lca と同じようなテクニックを使って解きます。lca の時と同じように, vals[logk][v] = (v から 2^logk だけ上までの頂点における, ID の小さい順の数列 p1, p2, ..., p10) というのを保持しておきます。 で, 頂点 u …

問題 codeforces.com 解法 dp[k][i] = (数列 a をつなげた個数が k 個で, 末尾の添字が i となるような場合の数) とします。これがわかれば, 数列が k 個つないでいるようなものが大体 p = L/N - k 個あるのでそれを数えて dp[k][i] * p の和を取っていけば…

問題 No.291 黒い文字列 - yukicoder 解法 dp[n][k][u][r][o] = (n 文字目までの時点で, "K" のストックが k 個, "KU" のストックが u 個, "KUR" のストックが r 個...) の時の"KUROI" が出来た substring の数 という DP をやります。最高で 100/5 = 20 個…

頭良すぎて禿げた。 med より難しくないですかこれ。 問題 TopCoder Statistics - Problem Statement 解法 dp[i][single][pair] = i 番目の文字を見ている時点で, 「;」のようにセミコロンが単体でまだペアになる文字が決まっていないものが single 個あって…

SRM 671 に参加しました。0 完太陽でレートが落ちてしまいました。med は %= MOD するとかいうしょうもないミスで落としたので辛い。 問題 TopCoder Statistics - Problem Statement 解法 w[a]*w[c] = w[b]*w[d] ということは w[a]/w[b] = w[d]/w[c] という…

これ本番出てたら「あぁ med やっておけば良かった…」とかなりそう(easy はわからなかったけどこっちは考えたらわかったので)。 問題 TopCoder Statistics - Problem Statement 解法 B さんは, A さんのどれかのトークンに狙いを定めてそれを集中狙いするの…

寝坊したので SRM 670 は不参加でした。 問題 TopCoder Statistics - Problem Statement 解法 実は条件を満たすような LCS の最大値は文字列 s の長さを n として必ず n-1 であることがわかります。これは, 以下の場合分けを考えることによりわかります。 s …

Div2 A, B の絶望的な読みにくさに比べるとこちらはややマシ。まだ言いますけど Div2 A, B は関係ないこと書きすぎでホント英語弱者に優しくない 問題 codeforces.com 解法 dp[t][row][col] = (時間 t に row, col にいてゴールすることは可能か)をやるだけ…

あまりの問題文の長さに撤退してしまったこどふぉ。ただ最近言い訳ばっかして Splatoon やってるだけなのでちょっと頑張らないといけないですね〜 問題 codeforces.com 解法 子供の診察順に処理していきます。i 番目の子の治療ができるかを確かめるために, …

問題 No.288 貯金箱の仕事 - yukicoder 解法 まず, ゆきうさぎさんはまずお金を全部貯金箱さんに預けて, そのあと貯金箱さんがなるべく少ない硬貨の枚数でゆきうさぎさんに返せば良い, ということがわかります。つまり, この問題は本質的には「お金をなるべ…

本番書いたコードがなぜ通っているのかよくわかってない。でも通れば正義。 今まで見た ARC B 問題の中では一番むずかしい気がします。 問題 arc045.contest.atcoder.jp 解法 解説の通りやってみました。 AtCoder Regular Contest 045 解説 from AtCoder Inc…

ARC 045 に参加しました。途中まで B も解けなくて死ぬかと思いましたがなんとか C まで解けました。 問題 arc045.contest.atcoder.jp 解法 xor の特徴からして, 頂点 v から 頂点 u までのパスにおける xor 和 = (頂点 0 から v までの xor 和) xor (頂点 0…

問題 codeforces.com 解法 順列の置換は, 一般に巡回置換の積で表すことが出来ます。巡回置換については wikipedia を参考に -> 置換 (数学) - Wikipedia巡回置換の積それぞれのパーツを分析していきます。一つの巡回置換が A 個の成分で構成されているとす…