SRM埋め(3)

SRM 714 easy
easyはこれくらいの難易度が良いよなぁ。何ターン目までに消さないといけないという条件が求まる。

SRM 713 easy
難しい。保留->わかったんですけど、easyにしては実装複雑すぎでは?と思ってkmjpさんの解説記事見たら全く同じでおったまげました。(p^d)^a=(p^e)^bみたいにpという一番簡単な形で累乗を表せばあとは適当にgcd取りながら計算していけばいいです。しかしこれがめんどくさい上に、工夫しないとO(n)になって死んでしまう。大変。

SRM 712 easy
良問。まず1ターン行動するとsumは2倍になることから何回行動するかはわかる。実験してみると2項係数がかかった式になるのでできる。Combinationをバグらせて遅かった。コード貼っときます。

ll C(int a, int b) {
	ll tmp = 1;
	rep(i, 0, b) {
		tmp *= (a - i);
		tmp /= (i + 1);
	}
	return tmp;
}

簡易版ですね。

SRM 711 easy
まずnがk桁1が連続するか見る。そうでなかったらk桁連続するところを1にしてそれ以降0にするのが最適。最初バグったコードを投げたけどなぜかsys test通った(えぇ…)

SRM 710 easy
できたんだけどこういう解法が怪しいやつは得意じゃない…。typeAとtypeBは可逆です。typeAのみでN-1に石を全部置けたらあとはtypeBでTに戻せばいいです。間隔的にはN-1以外のholeに作用させまくれば良さそうですが、実験してみるとそれでうまくいきそうなことがわかります。

SRM 709 easy
Aの要素が50以下なのでYのうち影響を及ぼすのは下6桁のみです。よってbitdpできます。

SRM 708 easy
constructive多すぎでは…similarityは減らしたくて、そうすると長さ1の文字列を並べるのが良いです。後はwxwxwx....みたいな文字列で帳尻合わせします。

SRM 707 easy
へびみたいにpathを蛇行させればいいです。実装まあまあ工夫できて結構早く通せた。

SRM 706 easy
混乱したのもあるけど無駄にdijkstra書いたせいで遅くなってしまった。ベルマンフォードは更新される数だけループする以外は、dijkstraの更新と同じことをちゃんと覚えておきましょう。あとtupleの使い方も覚えておきましょう。get < idx > (tuple)ですよ。

SRM 705 easy
グラフ張ってループあるか見るだけですがこういうめんどくさいのはSCCにやらせましょう。

SRM 704 easy
あまりバグらせることなくうまく出来たなぁと思ったけどみんな早すぎ。直径を最初に取ればいいです。よくあるやつ。

SRM 703 easy
あーこれtopcoder40問目のeasyだったのに誤読+全然思いつけなくてつらかった。sortして、前の方から順番に辺を張るみたいなことをすればいいです。

SRM埋め(2)

当分easyで鍛えます。(気分でmedときます)

scoreですが目安としては
5分で満点*0.95
10分で満点*0.9
15分で満点*0.8
20分で満点*0.7
36分で満点*0.5
と覚えておけばよいでしょう。早解きは正義。

SRM 730 easy
「「「「「non decreasing」」」」コードは1発で書けたからもったいない。

SRM 729 easy
dpやるだけ

SRM 729 med
状態削減が本質になることに気づくのが遅すぎるし、角だけでいいと思って嘘解法してしまった。ダメダメ。辺全部試しましょう。

SRM 728 easy
結構好き。1つだけ見た時取りうる長さの候補がO( (logA)^2)通りだから、全部長さを試してminを取れば良い。
SRM 728 med
なんか昔に解いていた。座圧してdp

SRM 727 easy
難しい。後回し。->解きました。面白い。良問。SAがあったら直後にNを挿入して、後にTAを加えればいいです。なければ後にSANTAを加えればいいです。
SRM 727 med
真ん中の#の個数と.の個数を決め打つ

SRM 726 easy
条件整理して同じようなDPを3回する。

SRM 725 easy
bitDP復元

SRM 724 easy
まずorでbitが0の桁は2つの数もその桁は0です。1+0,1+1を判別するためにはt=sum-orを考えればいいです。ただし(t & or)==orを満たしている必要が有ります。(これを見逃した)桁ごとに条件が出たので、あとは簡単です。

SRM 723 easy
これはうまく出来た。上のbitから見ていって2つ以上そのbitを持つ数があれば、答えは(2^(k+1))-1みたいな形になります。
1つならその数をvとしてvを削除、v-2^kを追加して下の桁を見に行けばよいです。

SRM 722 easy
桁dpで良いです。でもdpの形にする必要はなかった。

SRM 720 easy
渾身の出来。だいぶ時間意識したら結構うまく実装できた。疲れるけど。
digit1とdigit2のそれぞれ1つの桁に注目して数え上げdpすればいいです。

SRM 719 easy
どっかの行に行って移動します。
SRM 719 med
根を含む部分木を選択して、その部分木上にない頂点を取る問題になります。割と速く通せたと思う。欲を言えば緩和にもう少し早く気づけたらよかった。

SRM 718 easy
渾身の出来。適当に0かけながらDPするだけ。

SRM 717 easy
フローからの復元と思って、それで通ったけどなんか想定解は違ったみたい。ちゃんと理解したい。

SRM 716 easy
A = sa + sb, B = sb + sc, C = sc + saみたいに対称な形にして、sa,sb,scのうち一番短いものを01010101...として、残りは000000....と111111....にするみたいな方針で通りました。

SRM 715 easy
いやどういうこと。今までtopcoderで解いた中で一番簡単だったかも。+の数と-の数大きい方が答えです。

SRM埋め

最近のSRM無駄にconstructive多いっすね。


SRM 742 easy
1,0.5,0.25,0.125....と1,2,4,8,16....を作って適当に繋げれば良いけどバグった。
SRM 742 med
kmpチックにbitdpすればいい

SRM 740 easy
どういうことやねんと思ったら罠が有りました…
SRM 740 medium
dp復元久しぶりに書いてめちゃくちゃバグった。

SRM 739 easy
虚無実装だけど、こういうのはだいたい全探索できるからありがたい。
SRM 739 med
にぶたんしたあと適当に貪欲でいいなぁと思って実装したけど、条件を間違えまくって辛かった。
正しいのは、前の餌場から見ていって、空腹度が大きい牛を使っていくんですが、今の餌場では空腹を満たせない時、次の餌場でもそうであればfalseです。

(SRM 738は神回です)
SRM 738 easy
長さが整数である格子点上の2点がかなり少ないことを利用する。
SRM 738 med
実は独立に考えて良い。良問。

SRM 737 easy
面白い。全要素のxorをXとする。ある要素aをとって、X^aが0になる方法はたかだか1通り。
またX^a<=aという条件がつくが、これはXの最上位bitがaに含まれていることと同値。
よって奇数なら64, 65, 66...とかすればN<=37なので良くて、偶数なら全要素が上の条件を満たすのは不可能で、
1つ犠牲にすれば奇数と同じ状態になる。
SRM 737 med
は?0,1,-1に気をつけて掛け算するんですが、多倍長整数がいる。やめて。

SRM 735 easy
aaaaaa...とbbbbbb...を取ればたかだか2です。
SRM 735 med
条件はX(X-1)=0(mod m)です。XとX-1は互いに素なので、mの互いに素な積を全部試して、extgcdする。

SRM 734 easy
まず軸上は最初に除いておきます。そうすると、x>0,y>0,x^2+y^2<=r^2,gcd(x,y)=1なるx,yの個数を求めればよいです。
あとはx全部試してyは包除原理します。
SRM 734 med
ブラックジャックなんてしないで…

SRM 733 easy
ほんとうにやるだけ

SRM 732 easy
これ難しすぎるだろ…1点をひっくり返すのを繰り返すのが良いとわかりますが、領域が分かれている時もあるので注意。

SRM 731 easy
こういうの速くならないんだよね…dfsしていけばいいですが、文字列の扱いが若干複雑。

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

https://beta.atcoder.jp/contests/dwacon5th-prelims

アー

A
Nかけましょう。
B
なぜかバグらせた…上からbit決めましょう。
C
なんで思いつかなかったのかなぁ…ちゃんと順番決めて見ていかないからダメ。DとMの数もってしゃくとりすればいいです。

int N, Q;
string S;

void solve() {
	cin >> N;
	cin >> S;
	cin >> Q;
	while(Q--) {
		int k; cin >> k;
		ll res = 0;
		int D = 0, M = 0;
		ll cnt = 0;
		rep(i, 0, k) {
			if(S[i] == 'D') D++;
			if(S[i] == 'M') {
				M++;
				cnt += D;
			}
			if(S[i] == 'C') res += cnt;
		}
		rep(i, k, N) {
			if(S[i - k] == 'D') {
				D--; cnt -= M;
			}
			if(S[i - k] == 'M') M--;

			if(S[i] == 'D') D++;
			if(S[i] == 'M') {
				M++;
				cnt += D;
			}
			if(S[i] == 'C') res += cnt;
		}
		cout << res << "\n";
	}
}

D
わかったけどもっと速く詰められたよなぁ…値が3個だけというのはすぐ気づけたのに、累積和にすぐ言い換えられなかった…。
最大最小は和と交換可能、100回唱えます。
E
これもiteration回そうぜ…
問題自体はめちゃくちゃ面白いです。多項式の係数のgcdってこんな扱いできるのか。

int N;
ll A[MAX_N];

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	sort(A, A + N);
	ll res = 1;
	rep(i, 0, N) MUL(res, gcd(A[i], i));
	cout << res << "\n";
}

C解けていれば赤パフォだったと思うと悔しすぎる。

自分で決めたルールをちゃんと守れていない感。

DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選

https://beta.atcoder.jp/contests/ddcc2017-qual/tasks

去年の予選です。ばちゃコンしました。

ABはい
C set
D
とりあえず、対称な4マスずつに分けて考えれば良いことがわかります。
すると縦に対称、横に対称、3マス塗られている、4マス塗られているの4パターンについて考えればよいです。
しかし最初に縦か横に対称性がある時、除かなくてはならないことに注意です。

int N, M;
int A, B;
string S[MAX_N];

void solve() {
	cin >> N >> M;
	cin >> A >> B;
	int V = 0, H = 0, D = 0, C = 0;
	bool odd = false;
	rep(i, 0, N) cin >> S[i];
	rep(i, 0, N / 2) {
		rep(j, 0, M / 2) {
			int cnt = 0;
			cnt += (S[i][j] == 'S');
			cnt += (S[i][M - 1 - j] == 'S');
			cnt += (S[N - 1 - i][j] == 'S');
			cnt += (S[N - 1 - i][M - 1 - j] == 'S');
			if(cnt == 4) D++;
			if(cnt == 3) {
				C++;
				odd = true;
			}
			if(cnt == 2) {
				if(S[i][j] == S[N - 1 - i][j] && S[i][M - 1 - j] == S[N - 1 - i][M - 1 - j]) V++;
				else if(S[i][j] == S[i][M - 1 - j] && S[N - 1 - i][j] == S[N - 1 - i][M - 1 - j]) H++;
				else odd = true;
			}
			if(cnt == 1) odd = true;
		}
	}
	if(odd || (V && H)) cout << max(A * (V + C), B * (H + C)) + (max(A, B) + A + B) * D + A + B << "\n";
	else {
		if(V) cout << max(A * (V + C - 1), B * (H + C)) + (max(A, B) + A + B) * D + A + B << "\n"; //C == 0
		else if(H) cout << max(A * (V + C), B * (H + C - 1)) + (max(A, B) + A + B) * D + A + B << "\n"; // C == 0
		else cout << max(A * (V + C), B * (H + C)) + (max(A, B) + A + B) * D << "\n"; //C == 0, V == 0, H == 0
	}
}

場合分けを詰めるタイプの問題苦手なんだよなぁ。

「みんなのプロコン 2018」決勝B: 経路が色々

https://beta.atcoder.jp/contests/yahoo-procon2018-final/tasks/yahoo_procon2018_final_b

たぶん想定解よりも思いつきやすい方法で。
base-3でやらず、base-2でやりました。例えばK=217(二進法で11011001)ならこのようにやります。

........#
.##.###.#
..#..##.#
.........
.......#.
.......#.
.....#.#.
.....#.#.
...#.#.#.
...#.#.#.
.#.#.#.#.
.........

ポイントは下の三角形の領域で2^Nを作り出していることです。
上の3行でうまくbitに対応するように制御している感じです。よく見ると3行目が..#..##.(#)となっており、1が.、0が#に対応していることがわかります。

ll K;
ll ans[64][61];

void solve() {
	cin >> K;
	for(int i = 1; i < 61; i += 2) {
		for(int j = 0; j < i; j++) ans[62 - j][i] = 1;
	}
	rep(i, 0, 3) ans[i][60] = 1;
	int pv = 0;
	rep(i, 0, 60) {
		if(!(K & (1ll << (59 - i)))) {
			ans[1][i] = 1;
			ans[2][i] = 1;
			pv = 0;
		}
		else {
			if(pv == 1) ans[1][i] = 1;
			pv = 1;
		}
	}
	cout << 64 << " " << 61 << "\n";
	rep(i, 0, 64) {
		string str;
		rep(j, 0, 61) str += (ans[i][j] ? '#' : '.');
		cout << str << "\n";
	}
}

yukicoder埋め

https://yukicoder.me/problems/no/753

dp[level][bit][winner]:level段のトーナメントをbitに属す挑戦者で作る。勝者がwinnerの時の場合の数
として求めます。高速化いろいろしてAC。

https://yukicoder.me/problems/no/749

和と積のクエリが混ざっている時ってこうやれば良いんですね。解説で群論による考え方が記載されていたのであとで読みたいですね。
ai->kは0を掛けてkを足すクエリに言い換えられます。

struct segtree { // this is piece of shit. use BIT
	int n; vl sum, add, mul, fib;
	void init(int mx) {
		n = 1;
		while(n < mx) n *= 2;
		sum = vl(n * 2, 0);
		add = vl(n * 2, 0);
		mul = vl(n * 2, 1);
		fib = vl(n * 2, 0);
	}
	segtree(int mx = 0) { init(mx); }
	inline void lazy_eval(int k, int l, int r) {
		int m = (l + r) / 2;
		if(add[k] || mul[k] != 1 || fib[k]) {
			MUL(sum[k * 2 + 1], mul[k]);
			ADD(sum[k * 2 + 1], (vx[m] - vx[l] + mod) * add[k] % mod);
			ADD(sum[k * 2 + 1], (F[vx[m]] - F[vx[l]] + mod) * fib[k] % mod);
			MUL(mul[k * 2 + 1], mul[k]);
			MUL(add[k * 2 + 1], mul[k]);
			MUL(fib[k * 2 + 1], mul[k]);
			ADD(add[k * 2 + 1], add[k]);
			ADD(fib[k * 2 + 1], fib[k]);

			MUL(sum[k * 2 + 2], mul[k]);
			ADD(sum[k * 2 + 2], (vx[r] - vx[m] + mod) * add[k] % mod);
			ADD(sum[k * 2 + 2], (F[vx[r]] - F[vx[m]] + mod) * fib[k] % mod);
			MUL(mul[k * 2 + 2], mul[k]);
			MUL(add[k * 2 + 2], mul[k]);
			MUL(fib[k * 2 + 2], mul[k]);
			ADD(add[k * 2 + 2], add[k]);
			ADD(fib[k * 2 + 2], fib[k]);

			add[k] = 0;
			mul[k] = 1;
			fib[k] = 0;
		}
	}
	void addapp(int a, int b, ll s, int k, int l, int r) {
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			ADD(sum[k], (vx[r] - vx[l] + mod) * s % mod); //here too
			ADD(add[k], s);
		}
		else {
			lazy_eval(k, l, r);
			addapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
			addapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
			sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
		}
	}
	void mulapp(int a, int b, ll s, int k, int l, int r) {
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			MUL(sum[k], s); //here too
			MUL(add[k], s);
			MUL(mul[k], s);
			MUL(fib[k], s);
		}
		else {
			lazy_eval(k, l, r);
			mulapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
			mulapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
			sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
		}
	}
	void fibapp(int a, int b, ll s, int k, int l, int r) {
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			ADD(sum[k], (F[vx[r]] - F[vx[l]] + mod) * s % mod);
			ADD(fib[k], s);
		}
		else {
			lazy_eval(k, l, r);
			fibapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
			fibapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
			sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
		}
	}
	ll ga(int a, int b, int k, int l, int r) {
		if(b <= l || r <= a) return ll();
		if(a <= l && r <= b) return sum[k];
		else {
			lazy_eval(k, l, r);
			ll lv = ga(a, b, k * 2 + 1, l, (l + r) / 2);
			ll rv = ga(a, b, k * 2 + 2, (l + r) / 2, r);
			return (lv + rv) % mod;
		}
	}
	void show() {
		vector<ll> tmp;
		rep(i, 0, n) tmp.push_back(get(i, i + 1));
		debug(tmp);
	}
	ll get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b)
	void addupdate(int a, int b, ll s) { addapp(a, b, s, 0, 0, n); } //[a, b)
	void mulupdate(int a, int b, ll s) { mulapp(a, b, s, 0, 0, n); } //[a, b)
	void fibupdate(int a, int b, ll s) { fibapp(a, b, s, 0, 0, n); } //[a, b)
};

https://yukicoder.me/problems/no/255

前の問題のsegtreeをそのまま使えます。