2018-04-09

精進4/8

https://arc061.contest.atcoder.jp/tasks/arc061_c dijkstraを工夫しようと思って失敗した。グラフの方を工夫しましょう。
https://arc066.contest.atcoder.jp/tasks/arc066_b これ通せたのは成長感じる。桁DPなんですが、背反+遷移をちゃんと意識して解けたので良かった。
https://arc079.contest.atcoder.jp/tasks/arc079_c N=50程度なのでaが大きい場合は工夫して、aが小さい時は愚直にやればいいと思ったんですが1CaseだけWA出てる…。和のmodが普遍みたいなmodが必要十分になることが多いので注意。

2018-04-08

ARC094

iff.

https://beta.atcoder.jp/contests/arc094

惨敗でした。

C
えーわかんないのでDPした。
D
C(C+1)>=ABの式は出たんですが、方針が悪く詰めきることができず…
解説放送の二分探索のほうがわかりやすそう。
E
一回目の提出が1byte差で落ちたんですが、そこから冷静に直せたのは良かった。
でもやっぱり遅いよなぁ
F
どうせまた変な必要十分条件があるんやろと思ったらそうでした。しかし思いつかず。必要十分考えるとき和を見るのは大事っすね。

2018-04-06

CSA Round#75

FFT Square Decomposition

https://csacademy.com/contest/round-75

初参加です。

A
はい。
B
変なdfsした
C
sort and lower_bound
D
priority_queue
E
平方分割でmodが小さい時はsegtreeで愚直に、大きい時は二分探索と思ったんですが通らず…。
F
NTTやるんですが、式変形だけ書いておきます。

f(i)=(N-i+1)!Σ(k=i-1...N)[(k-1)/2](k-2)!/(k-i+1)!
=(N-i+1)!Σ(u=0...N-i+1)[(u+i-2)/2](u+i-3)!/u!
<=>f(N-1-l)=l!Σ(u=0...l)[(N-1+u-l)/2](N-2+u-l)!/u!
=l!Σ(u=0...l)F(u)G(l-u)
ただしF(i)=1/i!,G(i)=[(N-1-i)/2](N-2-i)!
となってNTTの式に変換できました。

2018-04-04

精進4/4

BitOperation Game

実は引っ越しして一人暮らし始めたんですが、今日になってやっとwifi環境を用意出来たので、精進再開です。

http://codeforces.com/contest/959/problem/C 真ん中に2つ点がある木と、rootに全ての点が隣接している木を出力する。
http://codeforces.com/contest/959/problem/D エラトステネスの篩的なことをやる
http://codeforces.com/contest/959/problem/E 数式めんどい
http://codeforces.com/contest/959/problem/F 面白い。置換群のお話。集合Sの要素xについてx^aがSに属さなければ全てのxについてx^aがSに属さない。逆にあるxについてx^aがSに属せば全てのxについて成り立つ。これを使って愚直DPを高速化する。
https://beta.atcoder.jp/contests/arc085/tasks/arc085_b これも面白い。DPかなと思ったら全然違った。初手全取りすればコストはもちろんabs(W-An)、1つ残しはabs(An-1-An)となる。2つ以上残すのは実は意味がない。なぜなら後手は必ず値をabs(An-1-An)以下にできるからだ。
https://apc001.contest.atcoder.jp/tasks/apc001_d n要素の次数列がn頂点の木をなす<=>全ての次数が0以上であり和が2n-2であるを利用すれば簡単。
https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_g 脳内AC。半分全列挙
https://arc092.contest.atcoder.jp/tasks/arc092_b これ500じゃないよなぁ…bitの桁ごとに見るとlower_boundでまとめられることに気づく。

2018-03-29

精進3/29

https://beta.atcoder.jp/contests/arc060/tasks/arc060_d 最小項数は1or2orNで、1とNの時は簡単。2はKMP法でできる。
[https://beta.atcoder.jp/contests/agc013/tasks/agc013_d DPにするのが難しいタイプの問題はホント苦手。でもこれはとりあえずdp[i][at]:=iまで進めた時赤がat個だけある場合の数をとりあえず求めてから背反にする方法を考えると解ける。
https://beta.atcoder.jp/contests/agc005/tasks/agc005_d こっちはDPにするまでが難しいタイプなので解けます…。マッチングの数え上げに帰着できるんですが、よく見ると直線グラフになっているので前処理コンビネーションして解けます。
https://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_a おまけ。各文字ごとにyahooを挿入することを考えてDP

2018-03-29

ARC085E: MUL

https://arc085.contest.atcoder.jp/tasks/arc085_c

maximum closure problemという問題なんですが、集合を2つに分ける+DPでできない場合は疑ったほうがいいです。
さて今回最大化したいのは、
S-min(Σbi+Σci)です。ここでbiは破壊する宝石のうち値が正のものであり、ciは破壊しない宝石のうち値が負のものについて絶対値をとったものです。
Sをsupersource,Tをsupersinkとして、S側にグラフcutが含まれるとき宝石を破壊し、T側に含まれていたら宝石を破壊しないことにします。
そうすると、宝石n*iはiの倍数なので、n*iが破壊されないのにiが破壊されるということはありません。なのでi->n*iにコスト無限の辺を張ります。
あと、i->Tにコストbiの辺を張ることで、もしbiが破壊されるグループに入ってる場合、その分損をしていることを表現します。
同じようにS->iにコストciの辺を張れば完成です。あとはSからTにフローを求めればmin(Σbi+Σci)が求められます。

int N;
int A[MAX_N];

void solve() {
	cin >> N;
	ll S = 0;
	rep(i, 1, N + 1) {
		cin >> A[i];
		if(A[i] >= 0) S += A[i];
	}
	int s = N + 1, t = N + 2;
	MF::init(N + 3);
	rep(i, 1, N + 1) {
		for(int j = i * 2; j <= N; j += i) {
			MF::add_edge(i, j, linf);
		}
	}
	rep(i, 1, N + 1) {
		if(A[i] >= 0) {
			MF::add_edge(i, t, A[i]);
		}
		else MF::add_edge(s, i, -A[i]);
	}
	cout << S - MF::get(s, t) << "\n";
}

2018-03-29

3/28精進

https://beta.atcoder.jp/contests/agc004/tasks/agc004_c 赤と青を交互に並べる。
https://beta.atcoder.jp/contests/agc012/tasks/agc012_b うーんこういうのダメだよなぁ。dp的に考えるのが苦手。bellman-fordっぽくやる。
https://beta.atcoder.jp/contests/agc013/tasks/agc013_c 場所はわかるので、ある点について反転する回数を求めれば全部わかる。
https://beta.atcoder.jp/contests/agc018/tasks/agc018_b ずっとどうやったらこんなの思いつくんだと思っていましたが、必要条件から攻めれば思いつけます。Constructive的発想。
https://beta.atcoder.jp/contests/cf16-tournament-round1-open/tasks/asaporo_c 最小全域木上のpathで最大の辺を選べば良いことがわかる。sとtを同じ点とみなすをsとtの間にコスト0の辺を張るという言い換えはお見事。
https://beta.atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_e 漸化式やるだけ。受験数学かな?
https://beta.atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_d 余りがjのやつとM-jのやつで最大マッチング。グラフの形がだいぶ特殊なので簡単な貪欲法でできる。
https://beta.atcoder.jp/contests/cf16-tournament-round3-open/tasks/asaporo_d スライド最小値やるだけ。
https://beta.atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_d ちょっと考えると111111222222223333333...みたいな形にすれば良いことがわかる。
https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d だからdpになるととたんにわからなくなるよなぁ。DPだと思ったらとりあえず性質に関する考察やめて状態について考えるべき。