http://codeforces.com/contest/1028/problem/CN個の長方形がある。 格子点のうち、最低でもN-1個の長方形に含まれる点を1つ答えよ。 前提知識 累積和 考察過程 1. 最低でもN-1個というのがややこしいので、まずはN個の長方形に含まれる点を考えてみる 2. 全…

http://codeforces.com/contest/1028/problem/Bs(x) := xの各桁の総和とするとき、s(a)≧n, s(b)≧n, s(a+b)≦mを満たすa,bを求めよ。 a,bは2230桁以下にせよ。 考察過程 1. まずは一番作りづらそうな場合を考えてみる 2. m=1,n=1129が一番きつそうな感じがある…

http://codeforces.com/contest/1028/problem/A縦N×横Mの盤面がある。 この盤面は最初は全て白色（W）だが、一部奇数の長さの正方形が黒色（B）で塗られている。 黒色の正方形の中心の座標を求めよ。 解法 http://codeforces.com/contest/1028/submission/42…

http://community.topcoder.com/stat?c=problem_statement&pm=15008円状にpeople人いる。 i番目の人がもし生きていれば、(i+1)番目の人を銃で撃つ（N-1番目は0番目を撃つ）。 どの順番で銃を撃つかはN!通りあるが、この中で生存者がalive人となるのは何通り…

150個の1×1×1の箱がある。 10×10の平面の上にこの箱を置いていく。 (0,0)から(9,9)まで100マスの上に順次置いていく。 箱を中途半端な位置に置くことや空中に浮くように置くことはできない。 平面を除いた周りから見える箱の面積がsurfaceになるように箱を置…

https://beta.atcoder.jp/contests/arc101/tasks/arc101_c 前提知識 個数系包除原理（偶奇で更に圧縮するテク） 二乗の木DP 解法 https://beta.atcoder.jp/contests/arc101/submissions/3082593求められる手法が多いので、そちらを学習してからの方がオスス…

https://beta.atcoder.jp/contests/arc101/tasks/arc101_b 前提知識 二分探索 解法 https://beta.atcoder.jp/contests/arc101/submissions/3082371答えで二分探索する。 check(x) := 全ての区間の中で中央値がx以上のものが過半数超えているか 全ての区間の…

https://beta.atcoder.jp/contests/arc101/tasks/arc101_a 考察過程 1. 最適な動きを考えてみると、負に行って正に行って終えるか、正に行って負に行って終えるのが最適 2. どれだけ負に行くかであるが、負のろうそくをi個経由した場合は正のろうそくをK-i個…

https://beta.atcoder.jp/contests/abc107/tasks/abc107_b 解法 https://beta.atcoder.jp/contests/abc107/submissions/3080988操作ができなくなるまで操作をするが、whileの中に処理用の関数を入れて実装した。 check() := 操作を行って、操作が行えれば1, …

https://beta.atcoder.jp/contests/abc107/tasks/abc107_a 解法 https://beta.atcoder.jp/contests/abc107/submissions/3080925後ろからに直すにはN-i+1をすれば良い。 注意点も特に無い問題。 int N, i; //-----------------------------------------------…

https://beta.atcoder.jp/contests/summerfes2018-div1/tasks/summerfes2018_d 考察過程 1. 最小パス被覆かな？と一瞬思うが、この方針でいくとWA 2. この方針ではない時に考えられるのは木DPくらい 3. パスの状況も追加で保存しておく必要がありそう 4. 正…

https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_c 考察過程 1. とてもむずかしい問題に見える 2. なるべく難度を落として考えてみると、サンプルが怪しいことになっている 3. 答えと一例が等しくなっている 4. もしかして全部同…

https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_b 考察過程 1. 全探索する対象を考えてみる 2. DとKの境目が全探索できそう 3. よくよく考えると、境目が決まると、DDDDKKKKが作れるか作れないかを判別することができる 解法 htt…

https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_a 考察過程 1. A問題にしては難しく見える 2. とても簡単な解法を考えてみると、10^100回シミュレートしてみるのが楽そう 3. 計算量的に難しいので、できるだけシミュレートする 4…

https://yukicoder.me/problems/no/727 解説 https://yukicoder.me/submissions/280706組合せ数学をする。 （全体の組合せ）＝（買われた関係の組合せ）×（売り手の置き方の組合せ）×（買い手の置き方の組合せ） （買われた関係の組合せ）は先頭から何番目の…

https://yukicoder.me/problems/no/728 解法 https://yukicoder.me/submissions/280679まずは愚直解法を書こう。 ll ans = 0; rep(j, 0, N) rep(i, 0, j) if (A[j] <= A[i] + R[i] and A[j] - L[j] <= A[i]) ans++; cout << ans << endl; A[j]≦A[i]+R[i]かA[…

https://yukicoder.me/problems/no/726 考察過程 1. 一見難しそうな問題に見える 2. 勝敗判定系は手法がそんなに無いので1つ1つ考えていく 3. マンハッタン距離みたいな移動をするので、x,y座標は独立に扱えそう 4. 考察過程でこのような図が出てくる 5. Xに…

https://yukicoder.me/problems/no/725 解法 https://yukicoder.me/submissions/280648実装力が試される問題である。 自分は文字列を先頭から見ていって、treeoneがあればforestに変換する。 そうでないなら、そのままTに追加するという処理をSが無くなるま…

http://codeforces.com/contest/1025/problem/DN頂点とその頂点に割り当てられている数が分かっている。 以下の条件を満たす二分探索木が作れるか 二分探索木になっている（左辺の頂点＜その頂点＜右辺の頂点） 辺の端点の数のgcdが1より大きい 前提知識 区…

http://codeforces.com/contest/1025/problem/BN個の数のペアから成る配列がある。 この配列のWCDを「全てのペアの少なくともどちらか片方の約数である数」とする。 WCDを1つ答えよ。 なければ-1 考察過程 1. GCDをもじってあるし、ペアの値も上限10^9なので…

http://codeforces.com/contest/1027/problem/EN*Nの盤面を白と黒で塗る。 以下の条件を満たす塗り方をmod998244353で答えよ。 隣接する横の列の塗り方が全く同じか逆である 隣接する横の行の塗り方が全く同じか逆である 面積がK以上の長方形が1つの色だけで…

http://codeforces.com/contest/1023/problem/D1～Qの数から成るN要素の配列Aがある。 一部0となって、抜けている箇所がある。 0の部分を適切に埋めて、以下の操作によって配列Aが作れるか判定せよ。 作れるなら、0を適切に埋めて答えよ。 「iを1からQまで順…

https://beta.atcoder.jp/contests/abc106/tasks/abc106_d 考察過程 1. O(MQ)はすぐに思いつくが、O(M)を改善したい 2. N≦500をうまく使って高速化したい 3. O(NQ)が理想っぽい。ここから考えると、各クエリについて左端を全探索できる 4. 右端については累…

https://beta.atcoder.jp/contests/abc106/tasks/abc106_c 考察過程 1. 一見難しそうだが、300点問題なのでなるべく簡単に考えるように努める 2. 5000兆日後だと、1以外の文字は10^18個以上に必ずなる 3. なので、普通にすると先頭の文字がK文字目になる 4. …

https://beta.atcoder.jp/contests/abc106/tasks/abc106_b 解法 https://beta.atcoder.jp/contests/abc106/submissions/3039853約数列挙をする。 enumdiv(n) := nの約数の配列を返す これはi≦nを満たすiで全探索すればO(n)で実装できる。 しかし、後々のこと…

https://beta.atcoder.jp/contests/abc106/tasks/abc106_a 解法 https://beta.atcoder.jp/contests/abc106/submissions/3039760道を片側に寄せて考えよう。 すると、縦がA-1ヤード、横がB-1ヤードになるので、答えは(A-1)*(B-1)になる。 int A, B; //-------…

Contest: https://www.codechef.com/PROC2018/problems/PROC18C Practice: https://www.codechef.com/problems/PROC18C1≦L≦R≦10^18が与えられる。 以下の条件を満たすペアの組み合わせ数mod(10^9+7)でを答えよ。ペア(x,y)が以下の条件を満たす xもyも[L,R]に…

https://www.codechef.com/problems/PROC18DN（≦200）個の数とN-1個の+,-演算子が順番に並んでいる。 適切に括弧をつけることで計算結果を最大化せよ。 前提知識 区間DP 考察過程 1. そもそもyukicoderで似た問題を見た これ 2. この問題の解法のエッセンス…

http://community.topcoder.com/stat?c=problem_statement&pm=14958とても大きい数Xがある。 この数に対して、以下の操作を行う。 a＜b＜cを用意し、a桁目をb桁目に、b桁目をc桁目に、c桁目をa桁目に数を移動させる このとき、leading-zeroとなるのは不正な…

http://codeforces.com/contest/1019/problem/Bインタラクティブ問題。 N要素（Nは偶数）の配列Aがある。 この配列は以下のような特徴がある。 隠されている 円状である。つまり、1番目とN番目は隣接していると考える 隣接している要素の数はちょうど1だけ離…