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;
}

ドワンゴからの挑戦状 第三回 本戦

参加記 Programming

コンテストはひどい結果になりました。
懇親会ではなんとミスケンさんが来ていて、ぷよ通で対戦しました。めっちゃ貴重な体験ができて楽しかったです。(はじめ操作が難しかった)
ありがとうございました(dwango作のC問題も割ときれいな問題だったので良かったです) 運営の方々ありがとうございました。









コンテストについて:

今回に関しては反省点は一個だけで、Bでlogを落とす発想が遅れたのはまあ僕が悪いんですけど、それでもこんな問題を作るほうが悪いです(発想自体は面白いんだけど、こんなmoの定数倍もついたようなしかもありうる素因数の個数(6ですよ?)) 倍を改善させたものを区別するのなんて不可能に決まっていて、実際何も考えずにmoをしただけで通ってる人もいて、一方想定解のintを一要素のvectorをなめるふうにしただけでTLEする、マジでなんでこんな設定にしたのか理解不能.

D:
tenka1-2016-qualb.contest.atcoder.jp
典型

A:典型区間DP

C:円の中にあるかどうかになるから,円の内部の点から三方向ににぶたんして境界を3つ見つければ外心が得られる.円の内部の点ははじめに長さ10^5の正方形(をふくむ半径10^5の円)で埋め尽くせば絶対100回で得られる.(ほんとはsqrt(2)倍くらいとれるから8^2=64でとれる)

B:mo+定数倍 sqrtまでの小さい素因数に関しては全て累積和を持っておくことでmoでのmerge次に見る値を1つにすることができる

__int128

Programming

は僕の環境だと使えないんですけど、(gccのバージョンではなくハードの問題なんですかね)AtCoderでは使えます(使う問題なんてほぼ出ないだろうけど). Ideoneだと使えないです.
演算はだいたい大丈夫だけどcin,coutは自分で書きましょう.
気づいたんですが負数と0に対応してなかった.ごめん.

#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 __int128 ll;
istream& operator>>(istream& i, ll& x){
	x=0;
	string s;
	i>>s;
	int N=s.size(),it=0;
	if(s[0]=='-') it++;
	for(;it<N;it++) x=(x*10+s[it]-'0');
	if(s[0]=='-') x=-x;
	return i;
}
ostream& operator<<(ostream& o, const ll& x){
	ll tmp=x;
	if(tmp==0) return o<<0;
	if(tmp<0) o<<'-',tmp=-tmp;
	vector<int> ds;
	while(tmp) ds.pb(tmp%10),tmp/=10;
	reverse(all(ds));
	for(int d:ds) o<<d;
	return o;
}
int main(){
	while(true){
		ll x;
		cin>>x;
		if(x==114514) break;
		cout<<x+1<<endl;
	}
}

JOI春

JOI Programming

問題一覧 - 情報オリンピック 問題と解説
2012年 日本情報オリンピック春合宿OJ - 2012年 日本情報オリンピック春合宿OJ | AtCoder
2013年 日本情報オリンピック春合宿 1日目 - 2013年 日本情報オリンピック春合宿 1日目 | AtCoder
2014年 日本情報オリンピック春合宿 オンラインジャッジ - 2014年 日本情報オリンピック春合宿 オンラインジャッジ | AtCoder
(2013だけURLが違う)

やります

2012

building2

データ構造をマージする一般的なテク.今となっては典型.マージテクで参照してる場所 をちゃんと持たないとバグります.

fish

まず2倍がどうこう、というのを見てmaximalな区間たちに落とす、次に高次元なので時間軸として一次元処理する、のこりの二次元の面積を求められればいいので、これは階段状の点を持って処理する. P(inf,0)とP(0,inf)を始めに入れとくと楽.

joi_flag

動的segtreeみたいに、非自明な計算が必要なとこだけ計算する.

broadcasting

output only 知らない. こういうのは各outputをvisualizeしてから考えるといいらしい.Kruskalとか,中心集合を適当に取る→貪欲→それらの中心を取る を繰り返すとかかなあ.

constellation

まず適当な例を考えると、どう考えてもDPの状態として持ちようがないつなぎ方をするしかないような例が作れて、まあだから実は簡単な条件で書けるんだろうという察しがつく. 凸包上でoxoxみたいになってたらアウトだなあ→それ以外ならできそう

rotate

とりあえず一次元でreverseだと面倒なクエリごとにlogNの平衡二分木があるけど、そんな感じのが想定解だったらΩ＼ζ°)ﾁｰﾝなので,各クエリでO(N^2)よりましなものを考える.縦横がどれにつながってるかだけなら境界のO(N)だけ変えればいいので出来そうという気持ちになる.実際どこにいるかを取得するのが難しい気がしたのでまずはじめに考えたのがクエリ平方分割で、各クエリブロックごとに、「いまXにいるのは誰ですか?をクエリの逆演算をして求める」というのをやった、これをするとO(NQsqrt(N))とかになるんですけど定数倍がかなり重いのでTLEした. 冷静に考えると、つながり方はcyclicな向きを保って持てるので、端っこから調べるとO(N)で境界を見つけられる.全体でO(NQ).
TLEだったけどクエリ平方分割をあまり実装したことがないので練習になった(結局「答えを求める」をB回やって、各ブロックではクエリiにクエリj(<i)が影響を及ぼす というのを全ペアに対して考慮してもO(sqrt(Q)^2)で大丈夫、というのが重要.いやそれはそう.
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～に書いてあるように、もとからreverseしたものを複製しておいてswap(つなぎかえる) というのが便利.

fortune_telling

典型遅延評価segtree

kangaroo

数え上げ,簡単だけど面白い(575)
集合から候補を選んで取っていく形で、集合が単調に出来る場合(この例だと,Cand_i = {j|Aj < Bi})はその集合が小さい順に考えると個数しか持たなくていい、っていう一般的なテク.
今回は、操作ができるまで繰り返す という条件を考えると、「最後にbに何も入れなかった時の残り」が何個今残ってるか というのを持てばいいことがわかる. 区間として考えたほうが良かったかもしれない.

sokoban

面倒 of 面倒 二重辺連結成分だとわかりやすく木に分解できるが、二重頂点でも同様のことが出来る.

chinese

自明 実はsetだけでいける

copypaste

invitation

ICPCつくば2016

参加記

が10/15,16にあったんですが、参加記を書いていなかったので書きます。
今年もsleep 18000 (sigma,wafrelka,wo) で参加していました

10/14

消費期限切れの牛乳を持ってないことを確認する

10/15

早起きしたけどライブラリ印刷したりしてたらギリギリの時間になって、今年も到着が遅れてしまった、けど今年はチームメイトが外で待たされていなかったのでよかった。
パーティーには色んな人が来ていて懐かしかった(特にI社の人とか)
ARCのwriterをやっていたのでめっちゃ参加を呼びかけたけど結構みんな風呂に入っていて悲C(僕も入ったけど).結構重いセットだったようで全完は少なかった.良問を作るのは難しいね.流石に寝る.

10/16

眠かったがなんとか起きて会場に行く.コンテスト開始まではうろちょろしていた.

コンテスト

つくばは基本難易度順なので,3人の強さの近いsleepは前半から3人がバラバラに解いていく.
A(sigma) やるだけ→WA→は? (この時結構大きい声を出してしまったらしく中心から角まで聞こえたっぽくて申し訳ない(あとでsugimさんに言われた))→AC(ごめん)
B(wo) やるだけ→AC
C(waf) 面倒やるだけ→AC
D(wo) vectorもつとやばいけどhashでいいかなあという話をしてええんちゃうみたいなことを僕が言ったら普通にTLEしそうだったのでもうちょっといい方針を考えることに
E(sigma) やることはすぐわかったのである程度詰めた後Gを読み始める
F(waf) むずいね みたいなことを言っていて,Hを読み始める
G(sigma) どう考えてもEより簡単なのでこっちをやり始める→AC
D(wo) woがいい感じの方針を考えていたっぽく書いてAC
H(waf) どのタイミングか忘れたけど書いていてTLE 冷静に考えてウニで死ぬことに気づいていた
E(sigma) 書き始める→鬱病→AC (1h以上かかっている・・・?(途中Hとか書いていたかも))
ここらへんで後半をだいたい読むと、H:これ全方位木DPでは? I:なんか適当に削れば良さそう J:hoge K:無理そう となっていたが、まだFが残っているので必死に考える
F(wo) TLEしそうな解法を思いつく→TLE
I(sigma) 嘘を書く→WA
H(waf) バグらせる→WA
F(wo) 64で割ったら?と言ったら割っていた、何度かバグらせたがギリギリAC.
コンテスト終了
悲しいね

10/16 つづき

悲しみに明け暮れていた.114514とは3完差だったし、いくらなんでも実力が足りなさすぎるなあ・・・
それはそうとパーティーはいろんな会社がブースを置いていて面白かった.Preferred Networksでiwiさんから話を聞いた,かなり面白そうだった.Indeedの出していた対戦ゲームが普通にSRMとかに出ててもおかしくないくらい良問でおもしろかった.あと5位はいろんな賞にあたっていたらしく色々もらった.
ダベってから帰る.
帰ってからAOJでやったらIのジャッジがなかった

11/17

参加記を書いたのでICPCつくば終了です.(日付が連続しているように見えるがこれは罠で、遅れてごめんなさい)

まとめ

JAGやボランティアやスポンサーの方々ありがとうございました、負けて残念でしたが今年も楽しかったです.
精進したいけどCPU実験が・・・