mayoko’s diary

プロコンとかいろいろ。

CodeForces

Educational Codeforces Round 2 D. Area of Two Circles' Intersection

問題 codeforces.com 解法 アイデアだけなら大学受験の典型ですね(手計算でとけるかは置いておいて)2 つの円の半径を r, R (r R+r R-r >= d なら, 円 r は 円 R に完全に含まれるので, 答えは pi*r^2 それ以外の場合は, 辺の長さがそれぞれ R, r, d の三角形…

Educational Codeforces Round 2 C. Make Palindrome

問題 codeforces.com 解法 回文になっているためには, 文字列の長さが偶数の場合, すべての文字が偶数個ずつ 文字列の長さが奇数の場合, 1 つの文字を除いて, すべての文字が偶数子ずつ ある必要があります。で, 辞書順最小にすることを考えると, ある文字の…

Educational Codeforces Round 1 E. Chocolate Bar

問題 codeforces.com 解法 落ち着いて dp すれば良いです。dp[n][m][k] = (n*m の長方形で, ぴったり k 個の square を作るには最低いくつのコストが必要か?) を考えます。分割の仕方は 縦に切るか横に切るかしかなく, 2 つに分割した長方形に対して, 一方…

Codeforces Round #219 (Div. 1) C. Watching Fireworks is Fun

問題 codeforces.com 解法 普通に dp しようと考えると, dp[m][n] = (m 個目の花火の時座標 n にいるような場合で, 喜び度の max 値) というのが考えられて, これは dp[m][n] = (dp[m][n-diff], dp[m][n-diff+1], ..., dp[m][n+diff] の最小値) + abs(A[m]-n…

Codeforces Round #219 (Div. 1) B. Counting Rectangles is Fun

問題 codeforces.com 解法 累積和の鬼になります。 まず, ok[y1][x1][y2][x2] = (長方形 (y1, x1, y2, x2) が good rectangle であるかどうか) というのを考えたいですが, これは長方形 y1, x1, y2, x2 内の値の cell の値の合計が 0 であれば良くて, これは…

Codeforces Round #341 (Div. 2) D. Rat Kwesh and Cheese

うーん, これは… 問題 codeforces.com 解法 結局 log を一回取るだけで良かったようです。ナニコレ一応学んだこととしては, long double が扱える範囲が結構大きいことですね。@mayoko_ 64bitの小数が10^308位じゃなかったですかね。80bitの小数型は指数分に2^16…

Codeforces Round #341 (Div. 2) E. Wet Shark and Blocks

Codeforces Round #341 (Div. 2) に参加しました。 E 解けないのはダメだ… 問題 codeforces.com 解法 dp[i][j] = (上から数えて i 桁目の時点で, x で割った余りが j になっているような場合の数) とします。すると, dp の遷移は dp[i+1][(j*10+a)%x] += dp[…

Codeforces Round #215 (Div. 1) C. Sereja and the Arrangement of Numbers

問題 codeforces.com 解法 p 個の数字を使えるとすると, その p 個の数字は w の大きい方から順に選ぶのが明らかに最適です(w は関係ないですね)。ということで, 問題は N 個からなる数列が与えられた時, 最大いくつまで数字を使えるか, の p を求めることで…

Codeforces Round #215 (Div. 1) A. Sereja and Algorithm

問題 codeforces.com 解法 まず, 2 文字以下なら絶対にアルゴリズムは終了します。3 文字以上の時は, xzy または yxz または zyx が繰り返し並ぶ構造になっていれば収束しますが, これは 指定された区間における x, y, z の数が区間の長さの大体 1/3 になっ…

Codeforces Round #213 (Div. 1) C. Beautiful Set

問題 codeforces.com 解法 適当に書いたら通ってしまったという感じ(解説を見ると writer もいろいろ解法ありそうと思っていたようです)なので証明も何もないんですが, やったことを書きます。素数の limit 番目まで使う, と決めた時, どのような整数集合が…

Codeforces Round #213 (Div. 1) B. Free Market

問題 codeforces.com 解法 集合 A から, D 円以内で交換できる品の集合 B があるなら, 集合 A から集合 B にシフトしていく, というのを貪欲にやっていけば良いです。集合 A と集合 B に同じ品の集合 C がある可能性がありますが, その場合は, A\C, B\C を交…

Good Bye 2015 D. New Year and Ancient Prophecy

問題 codeforces.com 解法 問題設定がこの問題に非常に似ています。 mayokoex.hatenablog.comまず大雑把に解法を説明します。dp[i][j] = (i 番目までの数を分割した時, 最後の数は j 桁であるような場合の数) とします。また, dpSum[i][j] = (i 番目までの数…

Good Bye 2015 C. New Year and Domino

問題 codeforces.com 解法 長いですが, 大事なことは 「長方形区間から飛び出すタイルは右側か下側にしかないので計算量は O(Q(W+H))」ということだけです。タイルの埋め方は, (y, x) と (y+1, x) を覆うようにタイルを埋める(下方向に埋める)か, (y, x) と …

Codeforces Round #210 (Div. 1) B. Levko and Array

問題 codeforces.com 解法 c(a) の値について二分探索します。c(a) dp[i] = (i 番目の要素を固定するとして, i 番目以下の数のうち値を変更しなければならない要素の数の最小値) とします。 これがわかると, (dp[i]+(n-i-1)) の最小値が K 以下なら c(a) = 1…

Codeforces Round #210 (Div. 1) A. Levko and Array Recovery

問題 codeforces.com 解法 配列 a の j 番目の数が i 番目のクエリの時点で +k されているとしましょう。この時, j を含む区間 [l, r] において最大値が d になっているというヒントが与えられたとすると, j 番目の数は d-k 以下になっていなければなりませ…

Codeforces Round #336 (Div. 1) B. Zuma

問題 codeforces.com 解法 まず少し観察します。 例えば 1 1 4 5 1 4 という数列を考えると, 例えば 1 1 4 5 1 4 -> 4 5 1 4 -> 4 1 4 -> 終わり というようなものが考えられます。これを考えると, 数列の部分数列(連続でなくて良い)の中でいかに上手く回文…

Codeforces Round #336 (Div. 1) A. Chain Reaction

Codeforces Round #336 に参加しました。相変わらず D が解けないおじさん。 問題 codeforces.com 解法 右から r 個の ビーコンを消す時, 残りのビーコンのうち何個のビーコンが破壊されずに残るのかが分かれば, 最高でビーコンがいくつ残るのかがわかります…

Codeforces Round #335 (Div. 1) B. Lazy Student

問題 codeforces.com 解法 最小全域木を作るときは, 小さいコストの辺を優先して選んでいき, もしその辺を追加してもループが得られなかったら木の辺として追加する, というアルゴリズムを使いますが, この問題の基本的なアイデアはそれです。頂点 1 にすべ…

Codeforces Round #335 (Div. 1) A. Sorting Railway Cars

Codeforces Round #335(Div. 2) に参加しました。また D 問題の実装が詰め切れず 3 完…ていうか今回 A 問題が一番難しくて B 問題が読解困難, C が一番手をつけやすかったという。 問題 codeforces.com 解法 例えば 9 3 4 5 6 7 8 2 1 という数列を考えると,…

Codeforces Round #334 (Div. 1) C. Lieges of Legendre

問題 codeforces.com 解法 ゲームの構造的に, grundy 数が使えます。f(n) = (皿に石が n 個乗っている際の grundy 数) とすると, 皿に石が n 個乗っている状態からは, (a)皿に石が n-1 個乗っている状態, または (b)石が n/2 個乗っている皿が k 個ある状態 …

Codeforces Round #334 (Div. 1) B. Moodular Arithmetic

D 問題にしては簡単すぎない? 問題 codeforces.com 解法 k = 1 の場合のみ特別な場合分けが必要ですが, 基本的な方針は以下のとおりです。k != 1 のとき, f(0) != 0 であるとすると矛盾するので, f(0) = 0 です。a を任意の非ゼロ自然数として, a*k^b (b は…

Codeforces Round #207 (Div. 1) B. Xenia and Hamming

問題 codeforces.com 解法 x と y の文字列の長さを求めます。で, その最小公倍数を求めます。その値が g であったとすると, x の i+a*g (0 なので, それらの値を足し算して求めれば良いです。 const int MAXN = 1000010; int alpha[MAXN][26]; int main() {…

Codeforces Round #207 (Div. 1) A. Knight Tournament

問題 codeforces.com 解法 2 通り解法を紹介します。一つは vector を使う方法で, もうひとつは set を使う方法です。vector を使う方は, next[i] = (i の次にトーナメントに残ってる人) というのを保持しておきます。最初は next[i] = i+1 ですが, 各クエリ…

Codeforces Round #334 (Div. 1) A. Alternative Thinking

出るつもりだったのに開始時間を勘違いして出れなかったこどふぉ。 問題 codeforces.com 解法 もっと簡単に解けるらしいですが, dp で解きました。dp[now][start][use] = (now 番目の数字を見ていて, 最初の数字は start にするつもり, 反転させているフラグ…

Codeforces Round #333 (Div. 1) C. Kleofáš and the n-thlon

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

Codeforces Round #333 (Div. 1) B. Lipshitz Sequence

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

Codeforces Round #333 (Div. 1) A. The Two Routes

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

Codeforces Round #333 (Div. 2) B. Approximating a Constant Range

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

Codeforces Round #332 (Div. 2) D. Spongebob and Squares

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

Codeforces Round #332 (Div. 2) C. Day at the Beach

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