2016-09-12

JAG2016夏合宿

に参加しました

day1

補習に行って、なぜか自分のPC上の仮想環境(VMware)が立ち上がらなくなっていることに気づく。そこでいろいろやってたら遅刻した(ごめんなさい)。sugimさんがいないので自己紹介でsugimを名乗りかける。談話室でボドゲをやる。The Bossが初見だったけど面白かった。寝る。

day2

5:30くらいにクッソまぶしい朝の光が窓から刺さってきたので起きたら本当にパソコンが壊れていて焦る(windowsが起動しない)。とりあえず朝食を解いてふて寝した。コンテスト直前にカスタマーサービスに連絡したらどうやらwindows 10 anniversary updateの不具合だったらしくBIOSの設定をちょっと変えたらなおった。こわすぎ。

コンテスト1: 2完差でpoに負けて2位。やばすぎ。ていうかやるだけしか解けなかった・・・。うちのチームだとある程度の考察とある程度の実装みたいなのをなぎ倒すのが得意なのでこういうセットが一番相対順位上がるのかなあ(ダメ)

万豚記に行くのを談話室で待ってたらもう出発してたのでこの日は行かなかった。

day3

ちゃんとカーテンを閉めておいたのでゆっくり起きれた。移動してヒカリエに行く。景色が良かった。レゴブロックで遊べる場所があって、人々がレゴブロックが入っている穴をレゴブロックで蓋をして遊んでいた(最終的に完成していた)。
f:id:sigma425:20160912194153j:plain f:id:sigma425:20160912194206j:plain
めっちゃくつろげる空間で模擬地区。
わふれるかが寝坊して遅刻していた。

コンテスト2:Eでジャッジがバグっていたのとwafrelkaの遅刻で初動がうまくいかず、7完4位だった。取り組めば解けそうな問題が多くて良いセットだったと思うので残念(最後F,I,Kの3並列だったし流石にやばい)

AGC004があった。writerはsugim48(理由:4は偶数)だった。A~Dを倒した後E,Fが全くわからず48位。ほんとにクッソ良問セットでびっくりした。

コンテスト後談話室で駄弁る。「エセ芸術家」というゲームをやったがクッソ面白かった。全体的にみんなエセ芸術家の推理能力を過信しすぎていて、適当なのを書いてエセ芸術家が誰かわからなくなることが多かった。
皆もあててみてください(ほとんど無理だと思います) 記事の最後に答えを載せておきます。
f:id:sigma425:20160912192511j:plain f:id:sigma425:20160912192525j:plain f:id:sigma425:20160912192558j:plain f:id:sigma425:20160912192613j:plain f:id:sigma425:20160912192627j:plain f:id:sigma425:20160912192639j:plain

day4

ギリギリだったがルームメイトと朝飯を食っていったら本当にギリギリになった、すみません(提案したのは僕です)。
今回はSleepの残り二人は参加していなかったため、snukeを誘ってチームを組んだ。チーム名はigma425(いつもの)

コンテスト3: Open Cupの過去問。ICPC系面倒と考察をsnukeがやっていたため、残り時間を使って面倒DPの実装をしていたらコンテストが終わった。10完でその場では一位だった(が、virtualでやばい人がいっぱいいた 18位)

終わった後解散だったが、snukeとsugimさんと万豚記へ向かう。おいしかった。ずっとクソなぞなぞを生成していた。

まとめ

楽しかったです。JAGのセットも割と好きだったし、準備もお疲れ様でした。

お絵かきの答え

食べ物: たいやき
動物: アリクイ
ことわざ: 石の上にも三年
たてもの: 橋
機械: 掃除機
競技プログラマ: わふれるか

2016-08-25

CF AIM Tech Round 3 (Div. 1) (708)

A:場合分けはじめのaじゃないとこからaじゃないとこまでだけどaaa->aazに注意
B:場合分け 0がない時と1がない時とそれ以外で,それ以外だと0と1の数がわかるので全体と合ってることを確認した後は適切に0001111からずらす(計算して).
C:全方向木DP.dp[v]=v以下でN/2以下のサイズの部分木の内でもっとも大きい物をもつとvをcentroidにしたければvの子uのうちN/2よりでかいものからできるだけでかく(つまりdp[u])を切り取ってvとつなげばいいのでこれはdpを計算すればわかるあとは全方向にすれば終わり.
コンテスト後にすぬけが言ってたように,そもそも重心を根として木DPすれば,切るのは重心をまたいだ部分なので楽に実装できるっぽい.
D:min_cost_flow.
元々a->bにf流れていてmaxがcっていうのを,

		if(f<=c){
			sum+=f;
			add_edge(a,T,f,0);
			add_edge(S,b,f,0);
			add_edge(b,a,f,1);
			add_edge(a,b,c-f,1);
			add_edge(a,b,INF,2);
		}else{
			ans+=f-c;
			sum+=c;
			add_edge(a,T,c,0);
			add_edge(S,b,c,0);
			add_edge(b,a,c,1);
			add_edge(a,b,f-c,0);
			add_edge(a,b,INF,2);
		}

こうする.(add_edgeはfrom,to,capacity,cost)
SとTっていう新たな頂点を追加して,

f≤c の時

すでにf流してあるというのは, a->TとS->bにf流さなければいけないという設定にして,f* ≤ f の時, (fを減らす) コスト1でb->aに流し戻せる(ただしfまで)
f* > f の時, (fを増やす) cまで(つまり新たなグラフでc-fまで)はコスト1で増やせて,それ以降はfとcを共に増やす必要が有るためコスト2になる.

f>c の時

まず絶対にf-cのコストは掛かるため,これを答えに足しあわせておく.そして今c流してるという設定にしておく.前述のf-cのコストの範囲で,c流す~f流すまでは自由にできる(cを減らし,fを増やすことで)ので,f-c分はコスト0で流せる.さらに追加分はコスト2.fを減らすのはコスト1でcまで減らせる.
sumでS->Tに流さねばならない分を計算していて,これでS->Tにsum流す必要があって,それとは別に0からN-1に自由に流して良くて,これはN-1から0へ辺を貼ればOK.その後min_cost_flow(S,T,sum)を呼べばおわり.

E:dp[i][l][r]=i段目が[l,r]でまだ連結な期待値みたいなのを持つと更新をうまくやればO(W^2 * H)でできる.更新をうまくやるのにlsum[i][l]=sigma dp[i][x][l] みたいなのを持つんだけど,実はdpはいらずにlsum,rsumだけ持って更新ができて,この更新もO(1)でできるためO(HW)になり終了っぽいけど面倒だし実装してない.

コンテスト:
C開いたらモロ全方向木DPで笑ってしまった(ついこないだ書いたばっかり) やる→Bで1WA→Aやる→E考える→順位表見る→Dが結構通されている→D通すみたいな感じだった.
Bが落ちてキレた.

A:Submission #20123051 - Codeforces
B:Submission #20134838 - Codeforces
C:Submission #20116938 - Codeforces
D:Submission #20131523 - Codeforces

2016-08-25

TreeDistance (TCO14 Round 3B d1 hard)

問題:N頂点の木Tが与えられます.「辺を一つ除いて,新たに付け加えて木にする」という操作をK回以下出来るとき何種類の木が出来るでしょう?N,K≤50

まず, TからK回以下で木Xに出来る⇔TとXの両方に含まれる辺がN-1-K本以上(→は自明,左はいつかのこどふぉEに構成する問題が出た(
CF345 - sigma425のブログ).

Tの辺集合をEとして,Eのsubset Sに対して,SがTとXの両方に含まれるようなものの個数を考えると,Sの連結成分の個数をC個,その大きさをn1,n2,..nCとすると,N^(C-2) * Πni になる.
これは非自明なんだけど,Prufer Sequenceと木との対応を知っていれば,そこからCayleyの式N^(N-2)が出てくることとの一般化として,これがわかる(sequenceに出てくる回数+1が次数で,連結成分ciとつなぐときはつなぎ方がni通りあるため,結局因数分解すると(n1+n2+...)^(C-2) * (+1回分の係数) となる.)

なので後は木DPで,dp[v][x][n]=v以下でx本を明確には固定せずに,今連結成分の大きさがn とやって,あとは包除.

#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++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll mod=1e9+7;
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
ll C[51][51];
vector<int> G[50];
int N;
int sz[50];
ll dp[50][51][51];
ll tmp[51][51][51];
void dfs(int v){
	sz[v]=1;
	for(int u:G[v]) dfs(u),sz[v]+=sz[u];
	rep(k,G[v].size()+1) rep(i,51) rep(j,51) tmp[k][i][j]=0;
	tmp[0][0][1]=1;
	int S=1;
	int K=G[v].size();
	rep(i,K){
		int u=G[v][i];
		rep(x,S) rep(n,S+1) if(tmp[i][x][n]){
			rep(ax,sz[u]+1) rep(an,sz[u]+1) add(tmp[i+1][x+ax][n+an],tmp[i][x][n]*dp[u][ax][an]);
		}
		S+=sz[u];
	}
	rep(x,S) rep1(n,S){
		dp[v][x][n]=tmp[K][x][n];
		add(dp[v][x+1][0],tmp[K][x][n]*n);
	}
//	rep(x,S+1) rep(n,S+1) printf("dp[%d][%d][%d]=%lld\n",v,x,n,dp[v][x][n]);
}
ll Co(int x,int y){
	if(x==y) return 1;
	return C[x][y];
}
ll ex(ll x,int p){
	if(p==-1){
		ll a=1;
		rep(i,x+1){
			if(a%N==0){
				a/=N;
				break;
			}
			a+=mod;
		}
		return a;
	}
	ll a=1;
	while(p){
		if(p%2) a=a*x%mod;
		x=x*x%mod;
		p/=2;
	}
	return a;
}
class TreeDistance{
	public:
	int countTrees(vector <int> p, int K){
		rep(i,51){
			C[i][0]=C[i][i]=1;
			for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
		N=p.size()+1;
		rep(i,N-1) G[p[i]].pb(i+1);
		dfs(0);
		K=max(0,N-1-K);
		ll ans=0;
		for(int i=K;i<=N-1;i++){
			ll ad=dp[0][N-i][0]*ex(N,N-i-2)%mod*Co(i-1,K-1)%mod;
			if((i-K)%2==1) ad=mod-ad;
			add(ans,ad);
		}
		return ans;
	}
};

2016-08-24

包除

Programming

a1,a2,..aNのうち,K個以上を満たす物の数は,

${ \displaystyle \sum_{i=K}^{N} (i個固定) * C(i-1,K-1) * (2|(i-K) ? 1:-1) }$

一々計算するのが面倒なので(ちなみに,K=0の時はC(-1,-1)=1だけ生き残る)

ちょうどK個は,まあ差をとればいいや.

2016-08-15

Mr. Kitayuta vs. Bamboos (CF286 C)

CF Programming

Problem - C - Codeforces

クッソ良問.CFのCに置かれて虐殺が起こった.

問題:竹がN本あり,はじめ高さはそれぞれh[i]である. 1日で起こることは,「 (竹を選んで"ハンマーで叩く")をK回以下 → それぞれの竹がa[i]伸びる」ここで,高さhの竹をハンマーで叩くと,高さはmax(h-p,0)になる(竹が消えるわけではなく、高さが0になる).K回の操作で同じ竹を複数回選んでも良い. M日後の竹の高さのうち最大のものを最小化せよ.(N,M,K,p,h,aがgiven) N<=10^5 M<=5000 K<=10 他<=10^9

以下解法なので自分で考えたい人は見ないでください.

2016-08-02

Typical DP Contest (TDPC)

Atcoder Programming

Typical DP Contestとは,りんごさんが作ったDPの問題で典型的すぎて一般的なコンテストに出せないと(りんごさんが)判断した,DPの練習問題を集めたものですが,十分難しい難易度のものもあります.

2013/8/31に開催されたんですがようやく全問解いたのでメモ.(もう昔解いた問題は忘却してそう)

良問揃いなので,まだ解いてない人は是非自分で考えてみてください.

A:dp[i][j]=i問目まででj点を取れるか
B:dp[i][j]=左からi個,右からj個取った時最大で残り何点取れるかもらうDP
C:dp[i][j]=iラウンド目でjが勝っている確率
D:dp[i][a][b][c]=i回振った積に2がa個,3がb個,5がd個出てる確率
E:dp[i][j][k]=i桁の数字で,桁和modDがjでk=0なら上i桁と完全一致,1なら上i桁未満の場合の数
F:dp[i]=i駅目までの止まり方(i駅目に止まらなくても良い) dp[i]からdp[i+1]への遷移は,基本i+1に止まるか止まらないかで2倍だが,直近K-1駅全て止まってる場合はとまっちゃダメで,その場合の数はdp[i-K]と一致する.答えは最後止まる必要があるのでdp[N]-dp[N-1] (最後止まらないようなものはdp[N-1]と一対一対応するので)
G:dp[i]:後ろからi文字の部分文字列は何通りあるかが,「新たに付け加えた文字を使わなくても元々出来ていた文字列」の数が,その付け加えた文字の種類のうち直近に出てきたとこ(その文字自体は含まない)までの部分文字列の数と等しいことを考えると計算できる.あとは辞書順で行けるかどうか判定.
H:先に色でソートしておく,dp[i][j][k][l]=i個まで見てj色使って重さがKでl:(今見ている色を既に使ったか)
I:dp[l][r]:s[l,r)を完全に取り除けるか? あるkがあってs[l,k)とs[k,r)が完全に取り除ける場合というのと, s[l]=s[r-1]='i'であって,あるkがあってs[k]='w'でs[l,k)とs[k+1,r)が完全に取り除けるという遷移の二通り考えればOK.
J:bitDP. dp[i]=iが残ってる時に倒すまでの期待値. 自己ループが発生するので移項して係数かける.
K:冷静に考えるとただのLIS.dp[i]=長さiの列の最後の最小でにぶたんO(NlogN)
L:dp[i][j]:i匹置いてi匹目と距離1以内にいるうち最も左の猫がj の時のうれしみのmax. i+1を置くとき,j以降に関しては自由に入るかどうか選べる.
M:セールスマン的なbitDP dp[i][j][k]="i->jでsubset kを通る" +行列累乗.
N:dp[v][i]=頂点v以下の部分木で,vとvの親が個の中でi番目に繋がれる場合の数というのを計算した気がするのだが,iをもたなくてもrootを全部試してrootからやっていけばいいことに気づいた.
O:挿入dp. dp[i][j]=i種類目の文字までを並べた時に同じ文字が隣り合ってる箇所がj箇所の場合の数. 挿入するときにj箇所中何箇所を切断するかとi文字目を何グループに分けるかを全部試すと遷移が出来る.
P:dp[i][j][k]=iの部分木でj本書いてて,iから下にはk本生えてる(k=0,1,2). 各頂点での更新も個数数えるdp.
Q:一番最後に解いた問題.(S,Rが2015/11とかだったので半年以上あいてる) dp[i][s][b]=i文字目まで見て最後の8文字がsで,"x文字後ろから削ったものも作れる(x=1~7)"のbitがb の時の場合の数. 更新を書く文字列に対してクッソ頑張ってたんだけど,冷静に考えると一文字ずつ増やしていけることがわかる.
R:慣れてたら最小費用流の方が簡単かも.まず強連結成分分解.あとはDAGで頂点重み付きだと思えて,2回の操作を同時に行うと思って,dp[v][u]=点v,uにいくまでのうれしみのmax なのだが,ここで遷移を適当にすると二回通った頂点を重複してカウントしてしまうことがある.vがuの先祖 or uがvの先祖の時こういうことが起こるのだが,よく考えると,v=uと,vはuの先祖でない∧uはvの〃の場合の二通りに制限しても任意の操作を表す遷移が可能であることがわかる.
S:各横マスの連結状態を持つ面倒なdp.ベル数はまあまあ小さい.正規化が面倒なので遷移が面倒.あと1行一気に塗るんじゃなくて一マスずつ塗ると楽だし計算量も落ちる.
T:きたまさ法と呼ばれる奴.n-ボナッチ行列の累乗をするとO(K^3logN)でダメ.a_iをa_0~a_{K-1}の線形和で表すことを考えると,a_iの表示からa_{i+1}とa_{2i}の表示がO(K^2)で求まるので,全体でO(K^2logN)になる. みさわさんが言ってた,(Z/pZ[x])/(x^K-x^(K-1)-...-1)という環でのべき乗だと思うというのが数学よりの人にはわかりやすいと思う.

コード載せたら爆発炎上するのでおわり.

今だと典型DPにはさらに色んな物が含まれそう.思いついたのを上げると,segtree高速化,convex hull trick,monge,誤差による状態量減らし,xの範囲がクソでかくてdp[x]=vになるxの集合がいい感じの性質を持つとき,dp[性質]=xたちみたいにするとかかなあ

2016-08-01

AGC002

Atcoder Programming

ほんとうに最下位だった

A:OK
B:OK
C:最後の一個が出来る二本があるならできるし,そうでないならできない.
D:永続UFかと思ったけど,クエリを同時ににぶたんするのにlog幅回走査する方法がある.知らなかった.
E:終了20sec後とかに通った.図形まではすぐに落とせたけどそっからがadhocすぎる・・・(あとななめが一緒って気づいてからも結構実装に戸惑った)
F:dp[i][j]=0をi個おいて,j色使ったという状態に関してj色目までをどこに置くかは全て決めておいたとして全部で何通りか
挿入ではなくて,先にどこに置くか決めるというタイプ始めてみた気がする(こうやって置けるものがどんどん増えていくパターンだと挿入が,"これまででこの種類はここまでに置いた"みたいな情報が必要になるので無理で,そうするとこういう発想になるしか無いっぽい)

良セットだった・・・sugimすごすぎむ