読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

Educational Codeforces Round 5 E. Sum of Remainders

問題 codeforces.com 解法 前似たような問題解いてましたね… mayokoex.hatenablog.com 上の記事のは問題設定がわかりにくいですが, 今回のは問題設定が率直でわかりやすいです。10^7 程度までは正直に余りを計算します。それ以上の数での余りは, n/div の商…

Educational Codeforces Round 5 D. Longest k-Good Segment

問題 codeforces.com 解法 しゃくとり法やるだけ, なんですがバグらせまくりました…区間系書くときは, 「閉区間か半開区間か」とか「区間がどのような性質を持っているか」とかは意識すべきですね。そういえば珠玉のプログラミングにもそんなことが書いてあ…

Educational Codeforces Round 4 E. Square Root of Permutation

問題 codeforces.com 解法 順列では「順列 p の i 番目の値が p[i] だったら i -> p[i] に有向辺を貼ってグラフを作る」というのがよくあります。この考えで問題文の順列 q のグラフを作り, そこから p = q^2 を作ることを考えると, p[i] は, 「q のグラフで…

Educational Codeforces Round 4 D. The Union of k-Segments

問題 codeforces.com 解法 未だに問題の意味が正確にはわからないのでアレなんですが, 現れる数ごとに区間が重なっている数を +1, -1 していって, 重なる数が k 以上のところを取り出していけば良いです。 int main() { int n, k; cin >> n >> k; vector<pii> mem</pii>…

Codeforces Round #221 (Div. 1) D. Tree and Queries

問題 codeforces.com 解法 前使ったばかりの, データ構造をマージする一般的なテクを使います。M[v][color] = (頂点 v 以下の subtree において, 色が color の頂点がいくつあるか) N[v][num] = (頂点 v 以下の subtree において, 頂点数が num 以上ある col…

Codeforces Round #221 (Div. 1) B. Maximum Submatrix 2

問題 codeforces.com 解法 maxi[row][l] = (row 行目の l 番目の要素から始めると, 1 が最大どこまで連続しているか) というのを, 各行 row について, しゃくとりっぽく O(m) で求めます。そしたら, l 列目からスタートする長方形について, 面積が最大にする…

Codeforces Round #221 (Div. 1) A. Divisible by Seven

問題 codeforces.com 解法 1, 6, 8, 9 を適当に並び替えると, 7 で割った余りが 0, 1, ..., 6 のいずれにもなりえます。ということで, 0, 1, 6, 8, 9 以外をとりあえず並べて, 1, 6, 8, 9 を全体の数が 7 の倍数になるように並べます。最後に, 0 を並べて終…

Educational Codeforces Round 3 E. Minimum spanning tree for each edge

問題 codeforces.com 解法 まず普通に MST を作ります。で, その木に辺 (u, v) を追加したと考えると, 閉路が出来ます。閉路のいずれかの辺を取り除くと再び木になるので, 閉路の中からコストが最大の辺を取り除けば良いです。最大の辺はどうやって取り除け…

Educational Codeforces Round 3 D. Gadgets for dollars and pounds

問題 codeforces.com 解法 冷静に考えるとちょっと前準備をしてから答えに対して二分探索すれば良かったと思うんですが, 答えを 1 つずつ足していって, それが条件を満たすかを 3 分探索で調べる, という方法で AC しました。ある日程 ans について, i あと…

Educational Codeforces Round 2 E. Lomsat gelral

問題 codeforces.com 解法 "データ構造をマージする一般的なテク" を使います。なにそれ, という人は以下のページをご覧ください。 topcoder.g.hatena.ne.jp今回の問題の場合, M[v][color] = (頂点 v 以下の部分木で, 色が color の頂点がいくつあるか) とい…

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] 番目の数のみで構成されてい…

Codeforces Round #206 (Div. 1) E. Lucky Number Representation

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

Codeforces Round #206 (Div. 1) B. Game with Strings

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

Codeforces Round #206 (Div. 1) A. Vasya and Robot

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

Codeforces Round #206 (Div. 1) C. Vasya and Beautiful Arrays

問題 codeforces.com 解法 配列がすべて d の倍数になるように出来るとすると, 配列のすべての数が m*d + x (x は min(k, d-1) 以下の数)という形で表せることになるので, このようになっているかを調べます。d を全列挙したとしても, これを調べるのにかか…

Codeforces Round #331 (Div. 2) C. Wilbur and Points

Codeforces Round #331 (Div. 2) に参加しました。 AB しか解けず撃沈。C は誤読して難しい問題を解いていたようでアレですが, それに気づいてからも実装に時間がかかるなどしてやっぱり実装力無いなぁと。 問題 codeforces.com 解法 とりあえず誤読してない…

Codeforces Round #330 (Div. 1) C. Edo and Magnets

問題 codeforces.com 解法 各マグネットの中心(重心)座標しか興味ないので入力値からそれを求めます。この時, double で管理しようとすると不幸になるのですべての座標が 2 倍されてると考えて座標が整数になるようにしましょう。この重心座標については, ど…

Codeforces Round #330 (Div. 1) A. Warrior and Archer

つい最近, 作問ミスをしたので他人事ではない。 問題 codeforces.com 解法 なんとなく思うのは, Warrior 側の人は, 端っこ以外の数字をとっても得しないということです。つまり, Warrior 側の人が取る数字は左端から l 個, 右端から r 個 (l+r = (n-2)/2) と…

Codeforces Round #330 (Div. 1) B. Max and Bike

問題 codeforces.com 解法 問題の様にセンサを取り付けると, センサはサイクロイドと呼ばれる軌道を描きます。 d = f-s とすると, d の の部分の倍数の部分はどうなろうと関係ないので, 結局のところ調べるべき図形は以下のような部分だけになります。 は左…

Codeforces Round #204 (Div. 1) C. Jeff and Brackets

問題 codeforces.com 解法 Darsein さんの解法を参考にしました。方針としては, dp[m][l][r] = (m 個の n 文字で作ったカッコを並べた時, regular bracket sequence にするために左側に "(" を l 個つける必要があって, 右側に ")" を r 個つける必要がある…

Codeforces Round #204 (Div. 1) B. Jeff and Furik

気づくべきことはすぐ気づいたのに漸化式間違えて時間食った。 問題 codeforces.com 解法 要するに, 反転数が 0 になるために何回操作が必要か, という問題です。方針としては, とにかく反転数を減らすのが良いです。状態は反転数のみで記述できて, 反転数が…