http://codeforces.com/contest/1036/problem/CL≦x≦Rのなかでclassyな数の個数を答えよ。 ※ classy：10進数表記した時に0でない数が3個以下である数 前提知識 桁DP 解法 http://codeforces.com/contest/1036/submission/42623549[L,R]が扱いづらいので、[0,R…

http://codeforces.com/contest/1036/problem/B(0,0)から(n,m)への移動を考える。 2種類の移動がある。 1. 隣接するマスへ移動する（上下左右） 2. 対角線上へ移動する（左上、右上、右下、左下） K回移動して(n,m)へ行く方法は複数あるが、その中で対角線移…

http://codeforces.com/contest/1036/problem/A0～2Nまでの2N+1個の頂点がある。 i番目の頂点について i%2=0ならば頂点(i,0)、i%2=1ならば頂点(i, A[i])とする。 このA[i]の値は自由に決められる。 0,1,2番目で作られる三角形、2,3,4番目で作られる三角形、4…

https://yukicoder.me/problems/no/732 解法 https://yukicoder.me/submissions/283736cとabc=a+b+cをそれぞれ全探索する。 「N以下の素数の個数はN/logN個くらい」というのがあるため、それぞれ全探索でO(N^2/log^2N)。 O(N^2)は厳しいが、これなら確かに見…

https://yukicoder.me/problems/no/730 解法 https://yukicoder.me/submissions/283423やり方の1つとして、ある文字が2回以上でてこないことを判別しよう。 cnt[c] := 文字cが何回現れたか をmapを使って数える。 foreachでmapを与えると、mapならばpairで帰…

https://yukicoder.me/problems/no/729 解法 https://yukicoder.me/submissions/283415C++にはとても便利なswap関数というのがある。 大体のものを何も考えずに低コストでswapできる。 stringの要素もそれに漏れず、特に何も考えずにswapできる。 自分は今ま…

https://yukicoder.me/problems/no/731 前提知識 最小二乗法 解法 https://yukicoder.me/submissions/283487N個の数を頂点(i, A[i])として考えると、求めたい答えはちょうど線形近似になっている。 そのため、線形近似式を最小二乗法で求めよう。 もう少し具…

https://yukicoder.me/problems/no/733 前提知識 O(3^N)の部分集合の列挙を使ったbitDP 解法 https://yukicoder.me/submissions/283452この問題はbitDPを知っていないと解くのは難しい。 ok配列をまず作ろう。 ok[msk] := 集合mskの問題を1人でT時間以内に解…

http://codeforces.com/contest/1037/problem/DN頂点の木と[1,N]の順列Aがある。 この木について、頂点1からBFSをして訪れた頂点を順番に記録して、順列Aにできるか判定せよ。 解法 http://codeforces.com/contest/1037/submission/42453314※全て0-indexedに…

http://codeforces.com/contest/1037/problem/C2進数表記されたN桁の数A,Bがある。 Aに対して以下の操作を行ってBにするための最小コストは？ iビット目とjビット目をswapする（必要コストabs(i - j)） iビット目のビットを反転させる（必要コスト1） 解法 h…

http://codeforces.com/contest/1037/problem/BN個の配列Aが与えられる。(Nは奇数) この配列の中央値をSにしたい。 ある要素を+1か-1する操作を行う時、最小何回の操作で中央値をSにできるか。 解法 http://codeforces.com/contest/1037/submission/42452613…

http://codeforces.com/contest/1037/problem/A[1,N]の数を作るために最小いくつの整数を用意すればよいか。 例) N = 6 1,2,3を用意すれば 1=1, 2=2, 3=3, 4=1+3, 5=2+3, 6=1+2+3 で全て作ることができるため、答えは3 解法 http://codeforces.com/contest/1…

数え上げ問題のテクニックを紹介した金字塔として、DEGwerさんの数え上げテクニック集という資料がある。 この資料に書かれたテクニックが用いられた問題を以下にまとめる。 1. はじめに 2. 状態をまとめる 3. 探索順の変更 3.1. 大きい順に並べる = 動的計…

https://beta.atcoder.jp/contests/arc102/tasks/arc102_b 解法 https://beta.atcoder.jp/contests/arc102/submissions/3127759「2^20=1048576＞10^6」であるので、いつもの2の累乗を足していく構築テクをもとに考える。 小さいケースで考えてみよう。 L=2^3…

https://beta.atcoder.jp/contests/arc102/tasks/arc102_a 解法 https://beta.atcoder.jp/contests/arc102/submissions/3127393(a+b) % K = 0 (a+c) % K = 0 これを言い換えると (a+b) % K = (a+c) % K b % K = c % K となる。 他の組合せでもやると、a%K = …

https://beta.atcoder.jp/contests/abc108/tasks/abc108_b 解法 https://beta.atcoder.jp/contests/abc108/submissions/3127271回転行列を知らないと解くのは難しい。 dx=d2-d1, dy=y2-y1とした、(dx, dy)というベクトルを考える。 すると、(x2,y2)から(x3,y…

https://beta.atcoder.jp/contests/abc108/tasks/abc108_a 解法 https://beta.atcoder.jp/contests/abc108/submissions/3127069[1,K]の中で偶数の個数をa, 奇数の個数をbとする。 すると、aはfloor(K/2)となる。これはC++ではK/2と書くだけで良い。 割り算で…