問題 jag2015summer-day2.contest.atcoder.jp 解法 見た目からわかるように bitDP で解きます。dp[state] = (今暗い部屋のうち state で表される部屋にいる可能性がある場合の, 最小移動距離) とします。すると, 各部屋から i 番目の部屋に移った時の次の状…

今回の div2 med は div1 easy とほとんど同じっぽいですが, だとするとこの hard は med よりも簡単な気がする… 問題 TopCoder Statistics - Problem Statement 解法 dp で解きます。dp[now][preorder][prenum] = (now 番目の店を見ていて, 直前のビルは 1 …

「言われてみるとアタリマエ」みたいな問題解けないの非常に辛い。 問題 TopCoder Statistics - Problem Statement 解法 三項間漸化式を解く感じになります。まず, どのようなときに K が勝つのかを考えます。これは, 「K 以外のすべての人にボールが回った…

問題 jag2015summer-day2.contest.atcoder.jp 解法 逆からたどっていく感じでやります。"ABC" という文字列を見つけたら, それを "A" "B" "C" のいずれかに変換する, ということを繰り返して, 最終的な文字列が "ABC" になったら勝ちです。ただし, 例えば "A…

問題 jag2015summer-day2.contest.atcoder.jp 解法 二分探索をします。ok(x) = (x 以下の数のうち, N 回目の操作で選ばれる数があるか) という判定をします。この判定ができると, 結局のところ求めたい x というのは ok(x) が true になるような数の中で最小…

問題 arc044.contest.atcoder.jp 解法 せっかくなので部分点解法も載せておきます。d[t][x][y] = (時刻 t に座標 x, y にいるときの最短距離) というようにすると, d[0][x][y] = 0 をスタートにしてダイクストラすれば答えが求まります。で, 満点解法です。…

ARC 044 に参加しました。 B が難しかったせいか, C の部分点取るだけで結構上位にいけました。いや上位とっても解けないと意味無いですけど。 D は言われてみるとかなり簡単だったので C 捨てて考えても良かったかも。 問題 arc044.contest.atcoder.jp 解法…

SRM 667 に参加しました。 見事に貪欲解法にハマって 0 完です。久しぶりのプログラミングコンテストなのでレート下がるだろうとは思っていたんですがなんか悔しいレートの下がり方をした感じですね。 問題 TopCoder Statistics - Problem Statement 解法 bi…

問題 codeforces.com 解法 まず前提知識です。順列は必ずサイクルの集合で表すことが出来ます。例えば, 2 1 4 3 という順列を考えると, この順列は, 1 2 3 4 の交換によって表現されます。これは, (1, 2) というサイクルと (3, 4) というサイクルの集合で表…

Codeforces Round #319 (Div. 1) の Virtual Participation をやりました。A しか解けなくて死んだので結果的には寝坊してレートを得した感じです。 問題 codeforces.com 解法 割と単純です。まず x 軸を 1000 ごとに分けます。そして, その 1000 ごとの区切…

なんか SRM の div2 hard は難易度に安定感がない感じがする…(こんな簡単じゃないのもたくさんある気がする) 問題 TopCoder Statistics - Problem Statement 解法 頂点が 2 以下の場合はその 2 頂点がなす直線と直角方向に離れれば 2 頂点との距離が増えてい…

なんかやけに簡単な気がする。 問題 TopCoder Statistics - Problem Statement 解法 答えは (LESS 関数を使った数) * log(0.5) となる。そのため, merge 関数を実際に動かしてみて LESS を使う回数をシミュレートしていけば良い。 const double LOG = log(0.…

問題 tenka1-2015-final-open.contest.atcoder.jp 解法 kmjp さんの解説を参考にしました。kmjp.hatenablog.jp 得た知見 「全部やる」みたいな問題で実際に全部やるのは無理なので, 問題を小分けにする 今回の場合は「全部やる」 = 「すべての順列を試す」, …

問題名, 「ひま」でも良かったと思います。 問題 No.93 ペガサス - yukicoder 解法 writer の解説がわかりやすいのであんまり言うことがないです。 ペガサス - 解説ただ dp の遷移が結構難しいというか面倒です。ソースコードでコメントの説明をつけましたが…

問題 tenka1-2015-final-open.contest.atcoder.jp 解法 LCA とオイラーツアーを使えば解くことが出来ます。まずオイラーツアーしてそれぞれの頂点が最初に現れる場所(下のソースコードで言うと BEGIN)を覚えておきます。すると, クエリで与えられる M 個の頂…

明後日からまた暇になるのでたくさん解けそうです。 問題 Problem - 552C - Codeforcescodeforces.com 解法 2 通り紹介します。まずひとつ目。 w が 2 と 3 の時は m がどんな値であろうと OK です。よって, それ以外の場合について考えればよいですが, m が…

大学受験のとき使った参考書を引っ張ってきました。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335 解法 まず寄り道回数のうち左に移動する回数を i 回として横移動と縦移動を分けます。そして, 「横移動の場合の数」と「縦移動の場…

コメンタリー見てなんとなくうれしくなりました。 問題 No.278 連続する整数の和(2) - yukicoder 解法 n から始まる N 個の整数の和は, n + (n+1) + ... + (n+N-1) = Nn + N(N-1)/2となります。X は, 任意の n について上記の値の約数になっていなければなり…

yukicoder に参加しました。みんな作問になんとなく「センス」があるのを感じて羨ましいなぁと思っています。 問題 No.277 根掘り葉掘り - yukicoder 解法 30 分くらい想定誤解法で考えていました。 部分木に対する木 DP の要領でやろうとすると頂点 v につ…

納得できたようなできてないような。 問題 Problem - C - Codeforcescodeforces.com 解法 こどふぉ解説の図を使わせていただきます。Codeforces Round #318 [RussianCodeCup Thanks-Round] Editorial - Codeforcescodeforces.com木が 2 行の紙に書ける場合は…

いや〜この問題好きですわ。 問題 Problem - 573B - Codeforcescodeforces.com 解法 問題の特徴を観察してみます。まず, 両端のブロックは必ず消えます(問題の本質とは関係ないですが, このことより (N+1)/2 ターン以内にすべての tower が消滅することがわ…