JAG 2017 day1 (snukeセット)

Programming 参加記 ICPC

Tasks - Japan Alumni Group Summer Camp 2017 Day 1 | AtCoder


A:しりとり
適当なオイラー閉路を考えてその途中までを取るとか考えると正当性がわかりやすい

B:リス
ちょっと迷走仕掛けたが、「最終的な場所」で考えればいいことがわかる

C:すごろく
動的FFTみたいなやつ(segtreeっぽい といってもいいかも)
左からDPを埋めるとして、ある区間を正しく計算する関数calc(l,r) を用意する.
calc(l,r)では、分割統治っぽく、まずcalc(l,m)を呼んで、次に[l,m) から[m,r) への全ての遷移をFFTでやって、最後にcalc(m,r)分を追加する とやればよい.

コンテスト中は面に出てくる値の種類が多い時は速く終わるからモンテカルロ とかやってました(カス)

D:くさかべ
ま、幾何ライブラリ写経したんですけどね(ここらへんもはやタイトルが全く関係ない)

E:ベクトル式
BNFを書き換えたほうがいい みたいな問題はたまにあるので、これLLじゃないよ～とか思ったら考えたほうがいいと思います

F:逆から見てにぶたんすると片方向きだけでいい.左から貪欲に取ると右方向には極小(そ)

G:2リストらしい.頑張ってグラフを作ると一般の場合でも解けるが、H=2だとサイクルができちゃうケースが限られているのでそれだけやればOK

H:

過半数がどうこう、よりまず自由度3で条件2だから一つ決めればすべて決まるというのに気づくのが重要

イベルタルってこんな動き方するんですか?(いいえ)

I:
フローに必要な辺 のやつ
正当性は簡単.
あるフローFを固定する.Fの残余グラフの(有向)サイクルに含まれない→確定(Fに含まれてる⇔かならず使う,含まれてない⇔必ず使わない)
含まれてるならそれにそって流せばその辺は消せるので、どっちもありうる.
x→y があるサイクルに含まれている ⇔ sccでa,bが同じ成分 なので余裕

J:
2WA(ha?)

K:パンプキン
一応式を書くとa+bがデカい順でOK.

ちゃんと「ん」で終わってしりとりが終了している.
最近始めたので読解がすんなり出来た.裁きの光ってカードが好きです.

yukicoder ☆5,6

何故か埋めています。解法メモなのでネタバレ注意。

☆5

42:
63:
93:

変なことをすると下から挿入できるが、普通に包除

114:
137:

特異問題です。これはむずい
1,x,x^2,..なら順番に倍数だから、modでピッタシになるようにdpするっていうのが出来たわけだが、今回はxを自由に使えるっていうのをx,2x,4x,..が1枚ずつあると言い換える。それでx_1,..,x_N,2x_1,..,2x_N,..っていう順番で使うかどうか決めていけば、各状態ではSum x_N 通りくらいしか持たなくて良い。
自由DPのときに分割するのは典型っぽいがその後こんなうまくいくのはびっくりしたなあ

214:
234:
243:
248:
263:
271:
283:

カス

284:

異なる二種類の和のmax みたいなのは 上位2種類持っておけば良い Bicycles(蝶々のやつ)とか

295:

まずこういうふうに並べるのが最適なのを示すのがアレだが、無駄に分割するのは意味がない(すべての文字でマージすれば絶対に積が大きくなる)のでOK.
あとはすごく小さいケースだけ場合分け
max制限がある数え上げでパラメーターtがあってn^tオーダーとかだとtが1,2,3とかのケースだけやればいいみたいなのあるよね

377:

Burnsideのいい練習問題だと思う.
不変な(x,y)の集合 みたいなのを考えたくなるが、ちゃんとBurnsideがわかってれば G = Z/HZ * Z/WZ の各元ごとにかんがえればいいことはわかる

382:

最大独立点集合, 乱択おもったより強いなあ(まあ乱数ガバいからまともに作ったケースだと落とされるのかな)

426:

苦行segtree

435:

無.なぜかmod 9 の世界でかけたり割ったりする時に 3^a * b (b = 1,2) の形で持っていたが,bは1,2,4,5,7,8なんだよなあ. 気をつけます

465:
474:

一時期ちょっと流行ったmod2系. Lucasの定理の拡張でmod素べきとかもあるので、困ったら使ってもいいかも(まあ愚直にやれるなら↑435みたいにやればよい).

540:

予想投稿サイトやめろ

UTPC2011

Atcoder Programming

D:探索ゲーでpair<pair<int,int>,pair<int,int>>とかやるのつらいので、tupleを使う.勝手に辞書順が入ってるのでsetに入れられる

	using State = tuple<int,int,int,int>;
	queue<State> que;
	que.push({1,2,3,4});
	int a,b,c,d;
	tie(a,b,c,d) = que.front();
	cout<<a<<b<<c<<d<<endl;

E:
長さNの数列a,bがある、indexのリストを選んで、(prefix sum of a) ≤ bとなるようにせよ.という問題

まずどの順に選べばいいかが先にわかるというのが典型テク.連続する二つのswapを比べるとこの場合はbが小さい順がいいことがわかる.

なので今何個選んだかのDPで出来るんですけど、実はO(NlogN)になるらしい.

b昇順にするのまでは一緒、とりあえず貪欲に選ぶことにしていって、選んだ結果超えちゃったら、その時点でbが一番でかいやつを諦める(b昇順であることから諦めるのは高々一回であることがわかる).
証明:hoge

F:構成.帰納法

G:長さ選んで三角形→連続するように詰めれる

H:キャッシュ戦略→MCF.各sに対して[s,s+1)か[s,t)のどっちを選ぶか決められるんだけど、はじめ全部ちっちゃい方を選んでいると思うと、[s+1,t)を選んで重なりがf-1個 とみなせる,かなり特殊っぽい

I:(x==3)みたいな式が書きたいんだけど、これは(x==4)みたいな2冪にたいしてできれば良くて、でも冷静に考えるとこれはできないことがわかる,ちゃんというと、xの上の桁がyの下の桁に影響をおよぼすことは絶対にない.
なので出力のi桁目を決めるときは入力の0~i桁目を使えば良くて、(x==3?8:0)みたいなのは簡単にかけるのでOK.

J:まずN!通りのうちの数え上げになる.優先度順に見れば単純に二分木に挿入するだけになる.根が何番目か決めることでO(N^3)のDPができる.更新部分が畳み込みなのでO(N^2logN)にできる.hがでかいとこはどうせほぼ0なので、O(Nlog^2N)にできる.double版多項式まともに作ってなかった・・・

K:M≤N+500 圧縮です

L:永続

SRM710

Programming SRM

難しすぎる. 0完で-100くらいくらって黄色になった.

easy:
AとBは逆操作.なのである標準形みたいなのを設定してそこに持っていけばいい.標準形としてはぜんぶおなじとこに集まってるのとかを選べば良くて、これに持っていくにはAを選びまくれば良い.

操作が二種類ある時は、それを組み合わせて一般的で簡単な操作を作れないか(石を1つ動かすとか), 実は実質一種類の操作に落とせないか(ex.f(x) = 4x+3, g(x) = 8x+7), 逆操作になってないか などを疑いましょう。


med:
こんなの実験しないと絶対に解けません。
考えると、magicを無視した状態で、「xorが0 もしくは全ての山が1」の盤面にしたら負け というのがbase stepとしてわかる.
あとは頑張って実験をすると、
その状態で次に動かすプレイヤーの敗北条件は,
{ \displaystyle \begin{cases} \text{ if } \exists i , x_i>=4 & \bigoplus_{i=0}^{n-1}x_i=1 \\ \text{ otherwise } & \bigoplus_{i=0}^{n-1}x_i=2 \end{cases} }
であることがわかるので、これを計算して終わり。
証明:
ifの方を①,otherwiseの方を②とする.
勝ち状態で回ってきたときに①→①,②→②,①→② のどれかを使って負け状態を回せることと、
負け状態で回ってきたときに①→①,②→②,①→② のどれを使っても勝ち状態を回すことになることを示せば良い.
①→①はxorを0にすると負けなので1→2以上→1→2以上→・・・と遷移することからわかる
②→②は,
xor=1のとき, 全1でないことから2,3があり、しかも2以上は2個以上ある.なので3→0か2→1をしてよい
xor=3のとき,同様に2か3がある, 3があるときは3->2, ないときは2があり、かつ1もあるので1→0 でよい
xor=2のとき(負け), 1か3にしか遷移できないのはそう.
①→②は
勝つ側:4以上がひとつ→なしとなるので、事前状態はxor4以上.なのでこれを使ってxorを2にして渡せる.
負ける側:xor=1で回ってきているので4以上がひとつであることはありえない.

いや示せって言われたら示せるけどこんな場合分け実験せずに出来るわけないよね.

hard:
包除パートが見えるので、簡単やんけ!って思ったら前半の列挙パートが本質だった(座標の値が一致しても良いことに注意)
長さが正のintervalの端点の順序としてあり得るものは、A055203 - OEISで、N=6で既にデカいので全列挙は不可能.
なので左から頑張っておいていくDPをすごく頑張って書くと通る.
はじめどうせ求めるものは座標の値が一致しないものなんだからこの前提で包除すればええやん!って思ったけどそうではありませんね?
包除するときどういう形で求めているかちゃんと考えましょう

CF395

Eの賢い解法を見つけたのでメモのついでに


A:
色が異なるu-vを見つけたらuかvを選ばねばいけない

B:
x1%2,y1%2で類別すると同じのは接さない

C:
N=1,Mを除いておくと、総和の式からxとdの一次式が出てくる.同様に二乗和の式による制限によって高々二通りにまで制限できるので、これを満たすか判定してから、OKならまともに判定すればよい.(最後の判定いらないかも(解2つは+-の方に対応している気がする))

D:
hash
解いてないけど、
rng-58.blogspot.jp
がかなりためになる

E:
Bellをキーにしてdpの遷移をsegtreeに載せるんだけど、別に遷移先が一意に定まるのでdoublingっぽくするだけで合成とか考えなくて良い.クエリはlogN.


賢い解法を見つけた.
Submission #24402210 - Codeforces
とりあえず単に左から順にdfsで全連結成分を求める.
区間が与えられたら、とりあえずdfsの根の数を数える.本来の根が入って　ない連結成分をあとは数えれば良くて、これは、(区切られた後の)連結成分の内「dfsの値が一番小さいもの」の数を数えればよく、これを満たす頂点は絶対に区間の端っこK個に入っている.
理由:根は左にある、区間の外にある場合は左K個に入ってるはずで、内側にある場合は区間の右にはみだしてその後戻ってくるという形になっているが、このときは右K個に入っている.
判定するのは簡単(区切った後につながってるものとdfsidの大小を見るだけ)なので、解けた.
前処理O(NK),クエリO(K^2).

これ天才的だと思うんだけど

SRM707

Programming SRM

起きたら始まってたんですけど、結果から言うと出なくてよかった・・・
easyとmedが思考パートが無な上にかなりひどかった.しかもChalゲーだったのでかなり自分にはきつそう.

easy:
本当にただやるだけ、FAのコードも見たけど方針が違うとかではなく単純にただただ面倒.落ち着いてやるのが重要

med:
本当にただ場合分けをするだけ.証明をするつもりでつねに気をつけてやるのが重要.

hard:
このセットだと一番面白い. 時間軸にグリッドを拡張するとMCF(遷移だけコスト-1)になる.時間条件がある(例えばin→in→out→outはダメだがin→out→in→outはOK)ので時間軸を無視する訳にはいかないが、冷静に考えるとアクセスする2頂点だけ新しくノードを作れば良い.時間制限から負閉路がないことがわかるので、負閉路なし負辺入りMCFを貼る(はじめの一回だけBellman Fordをする).


SRMだとやったことないけどこれはストレステスト必須かな・・・

AGC009

Atcoder Programming

DEGwerは天才。
日露交流コンテストみたいなのが事前にあったのでネタバレを抑えるのが大変だった

A:後ろは押す場所が一意に決まるので後ろから決めていく貪欲.

B:xが誰に勝ったか、というのはわかるので、その部分をどういう順で戦わせるか考えると、相手のトーナメントの深さがわかっていれば浅いやつと先に戦えば良い.

C:dp[a][b]:Aの最後がa,Bの最後がb の通り数. とするとO(N^2). 連続して片方に置く分には(置けるなら)通り数は変わらないので、dp[a][a+1]とdp[a+1][a]の二つに着目すると、dp[a][a+1以上]みたいなのはdp[a][a+1]か0になる.これで1次元のDPにすると更新は区間になるので、頑張る.
初期化と最終的な答えは、一番初めに-infをAに,次に-infをBに割り振って、最後にinfを割り振る、と考えると楽.
本質的に同じだけどもうちょっと見通しのいい方法があって、
DPa[i][j]を,i番目まで見て最後aを置いていて、最後にbを置いたのはj となる通り数とおいて、DPa[i]という配列を一気に更新すると考えると、自然に区間sum,点val,refresh(全部0にする)が必要になる、BITでもって、最後のはこれまでのクエリを巻き戻してやればできる.

列を二つに分ける典型っぽい.

D:天才,めちゃくちゃ難しいと思う

まず実際のuninity kの構成をしたときに,中心として選んだ部分にkと書く,という風にして木にラベルを付ける問題になる.この条件は、「二つの同じラベルaの付いた頂点の間にはaより大きいラベルが存在する」と同値になる.書くのが面倒になったので公式解説に対する追加部分だけ書くと、このfの単調性は,f(x,y,..)=「各xの2進表記をinf進数だと思って足して、それより大きい最小の各桁01のもの」となることがわかるので、これから明らか.
結局この貪欲が何やってるかというと、「部分木の最小のuninity kを持つ」という嘘貪欲よりもうちょっと情報を持っていて、今kの構成状況のどの状態にいるかというのまで持って貪欲している.
これを持たなきゃいけないというのは、ただの一直線のものを端から木DPすると考えると、状態としては上述のものを持たないとどうしようもない、ということから考えつくべきっぽいが、難しいですね

E:これ解けないのは反省ですが、難しいです
まず多分木の形で考えるのはいいとして、そのあとちゃんと数式に落として、あと難しいのは深さdiがhoge個, みたいなまとめ方をするんじゃなくて最終的なもののK進表記がどうなってるか、というのを固定して考えると条件がmod K-1で一致,かつN以下 みたいなふうにかける.

どうやれば解けたかというと、数を数えるんだから、その複数ある表記法をわたって考えると難しくて、ちゃんと正規化してひとつのK進数、と思って本来数えたいものを素直に数えればよかったわけですね.

解きたかったなあ


すごいセットだった.

D:

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
int bsr(int x) { return 31 - __builtin_clz(x); }
bool B(int x,int i){return (x>>i)&1;}
const int MN = 100000;
int N;
vector<int> G[MN];
int dfs(int v,int p=-1){
	int b[20]={};
	for(int u:G[v]) if(u!=p){
		int tmp=dfs(u,v);
		rep(i,20) if(B(tmp,i)) b[i]++;
	}
	int ret=1e9;
	for(int i=19;i>=0;i--){
		if(b[i]>=2) break;
		if(b[i]==0){
			int x=0;
			for(int j=19;j>i;j--) if(b[j]) x|=1<<j;
			x|=1<<i;
			ret=x;
		}
	}
	return ret;
}
int main(){
	cin>>N;
	rep(i,N-1){
		int a,b;
		cin>>a>>b;
		a--,b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	int tmp=dfs(0);
	cout<<bsr(tmp)<<endl;
}

E:

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll dp[2001][2001];
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
int N,M,K;
int main(){
	cin>>N>>M>>K;
	int D=(N+M-1)/(K-1);
	dp[0][0]=1;
	ll ans=0;
	rep(d,D){
		rep(a,N+1){
			int b=(K-1)*d-a;
			if(!(0<=b&&b<=M)) continue;
			rep(k,K){			//K-1 (continue)
				int na=a+k,nb=b+(K-1-k);
				if(na>N||nb>M) continue;
				add(dp[na][nb],dp[a][b]);
			}
			rep1(k,K-1){			//K (end)
				int na=a+k,nb=b+(K-k);
				if(na<=N&&nb<=M&&(N-na)%(K-1)==0&&(M-nb)%(K-1)==0) add(ans,dp[a][b]);
			}
		}
	}
	cout<<ans<<endl;
}