risujirohさんJoe先輩とチームを組んで5位(オンサイト2位)でした。

最初はrisujirohさんとの2人チームだったんですが、僕がJSC2019の予選で橙から黄に転落したことで、3人でチームを組めることに。会場でもう1人拾うかとなった時にJoe先輩が加入してくれました。

戦略

というとオーバーですが、開幕はrisujirohさんがBDF、Joe先輩がACEを担当し、僕がG以降の問題を読んでました。AからFはコンテストのなかで一番簡単な問題だということが事前に公表されていたので、僕よりも速解きが得意な2人に担当してもらうのが良さそうということになりました。

G以降の所見の感想

G:これは解けるタイプの10^9+7だなぁ。
H:問題分が長いW
I:なんだこれ。制約がでかい数学はやめてくれ。
J:操作が謎すぎる。数学だし飛ばし。
K:AGCっぽさを感じた。解けるかも。
L:構文解析はまだしも多項式に関する問題はNG
M:全ての根について求めるんだから全方位木DPじゃないですか。
N:問題文が長くてよく読みませんでした。でも後から見返すと無理数を使ってゲームをしていて無理を極めてる。
O:構築ということしか把握してなかった。

なので解けそうなGKMの中でもGは簡単そうだったので着手しました。

ABD
問題文を読んでいるうちになんか2人が爆速で通してました。

E
これも知らない間にJoe先輩が通してました。

C
Joe先輩に問題と実装内容を説明してもらったんですが、どうやらa_i<=Xを忘れていただけっぽかったです。そのままAC。
あと__builtin_clzの仕様(0を代入された時の挙動は未定義)でハマっていたっぽいんですが、オセロのbitboardを実装したこともあって偶然知っていたので、伝えられればよかったなぁとちょっぴり後悔しました。

I
risujirohさんがlogを2つつけたものを提出したんですがTLE。WAもあってよくわからない。ここで一旦Iから離れたのは英断だと思います。

G
どうやら本質的には3つの値しかなくて、K回の操作である回文を作れたら、その回文はK+1回でも作れることはわかって、あとは1つの値を固定してコンビネーション+累積和で通るなぁと思って実装したんですがサンプルが1つ合わない。そのサンプルを精査したところKが2未満の時はコーナーケースっぽいことがわかったのでそれを除いてAC。(しれっと1WA出しているのは内緒)

F
risujirohさんがわからんと言っていたので僕も見たんですがわからない。Joe先輩がひらめいて、risujirohさんと解法を共有してからACしてました。ここからチームプレイ感が高まってきます。

M
Gの次に解けそうなのがMだったので、risujirohさんにも読んでもらって相談しました。僕は全方位木DPでしかないと思ってたんですが、risujirohさんに「ここは一旦全方位木DPから離れて部分木に足したり引いたりすればできるのでは」と言われてからあぁ…なるほど…となりました。実装で複雑になりそうなところがあったのでJoe先輩に問題概要から説明することに。なんかうまく日本語がでなかったり説明が飛んでしまったりしたんですが、簡単な実装方法を教えてもらい書き始めました。書き終えるのにはそんな時間がかからなかったのですがサンプルが合わない。手計算でやっても出力結果と同じになったので、ここで解法が間違っていたことに気づきます。一瞬青ざめましたが少し修正するだけで済んだので良かったです。

O
risujirohさんがマジックナンバーが大量に入ったコードを書いててデバッグやばそうとなりましたが、すんなり通しててウケました。正確すぎる。

O，相当面倒なことをしてたっぽいなhttps://t.co/FbtyT9cJA5 pic.twitter.com/YUHBhMGsEe
— 自朗 (@risujiroh) August 31, 2019

ぱっと見てもロジックがわからなくててどうやって思いついたんだという感じです。

H
Joe先輩がsegtreeのモノイド付きpriority_queueで二分探索すればできるとか言ってて、流石にそんなヤバ問なわけがないだろうと思って読み始めたら本当にそうでした(絶望)でもJoe先輩がAdvent Calendarですごい二分平衡木を書いていたことは知っていたのでそれを使えば出来ないことはないだろうくらいに思っていたんですが、知らない間に実装完了していてそのままACしてました。すごすぎる。二分探索パートはその場で書いたと言っててそれもヤバイ。

K
あんまり通されていなかったんですが、残ったIJKLNはそもそもどの問題もAC数が少なかったので考え始めました。操作を末尾の要素を好きな要素と入れ替えてから、shiftすると言い換えられることはすぐわかって、もうちょっと考えると必要十分っぽい条件が生えました。実装はfftになりそうだし、実行時間が2.5sなのもそれっぽいなぁと思い、risujirohさんに説明した所、そもそも値が0or1なのでbitsetで行けそうとなりました。risujirohさんに実装してもらい提出した所順調にjudgeが進んでACになりました。

J
最後の1時間risujirohさんと相談していましたが解けませんでした。畳み込みっぽい式が出てきてちょっといけるかもとなりましたが、解説を読んでみるとそもそも発想が間違っていました。残念。

スタバ
慰労会の後、会場の近くのスタバでChokudai Contest 004に参加しました。マラソンはおそらく初めてなのでなにをすれば良いのかわからず、めちゃめちゃな山登りを実装していました。全くスコアが伸びなかったので上のマスから順番に貪欲したものを提出したところ128万出て、あとはマスを埋める順番を変えてみたりしたんですが改善されませんでした。かなしぃ。

感想
うまくいって楽しかったです。risujirohさん、Joe先輩、慰労会で話してくれた人たち、運営さんありがとうございました。

2019-04-04

EDPC Y

DP Inclusion and Exclusion

https://atcoder.jp/contests/dp/tasks/dp_y

座標をpairに格納してソートしたものをPとする。訪れるマスのPのindexをa_1 < a_2 < a_3 <...< a_mとすると、a_1->a_2->a_3->...->a_mの順番でしか訪問できない。なので、最後に訪れる場所で場合分けできて包除できる。
包除の問題で集合ではなく個数でまとめて持てる場合は、向きをつけられるという特性があるからだと思いました。

int H, W, N;
pi P[MAX_N];
ll dp[MAX_N];

void solve() {
	cin >> H >> W >> N;
	H--; W--;
	rep(i, 0, N) {
		int a, b;
		cin >> a >> b; a--; b--;
		P[i] = pi(a, b);
	}
	sort(P, P + N + 1);
	C_init(H + W);

	rer(i, N + 1, 0) {
		int a = P[i].fst, b = P[i].sec;
		dp[i] = C(H - a + W - b, W - b);
		rep(j, i + 1, N + 1) {
			int c = P[j].fst, d = P[j].sec;
			ADD(dp[i], mod - dp[j] * C(c - a + d - b, d - b) % mod);
		}
		// debug(dp[i], a, b);
	}
	cout << dp[0] << "\n";
}

EDPC埋め完了。でもYが一番むずかしいと思う。

2019-04-02

SRM700Med

https://community.topcoder.com/stat?c=problem_statement&pm=14266

完全に知っているかどうかの問題ですが…

問題文がややこしいが、{1,2,...,n}から{1,2,...,n}への関数fを無限回適用したものをgとして、g(1),g(2),...,g(n)がk個の値を取る時のfの個数を求めよという問題になる。グラフに言い換えるとn頂点n辺のグラフになり、連結成分をみると、dfs+単純ループとなっている。なので単純ループに含まれる頂点数がkになるものを数え上げれば良い。
k頂点で単純ループを作る方法をdp[k]とすると、答えはdp[k]*C(n,k)*T(n,k)となる。ここでCはコンビネーション、T(n,k)=k*n^(n-k-1)。
C(n,k)はn頂点のうちどれを単純ループに含めるか、T(n,k)はn頂点k連結成分の森の数である。詳しくは
https://en.wikipedia.org/wiki/Cayley%27s_formula
を参照。
dp[i]の遷移はdp[i+j]にdp[i]*C(k-i-1,j-1)*(j-1)!を足し合わせれば良い。係数は取られていない頂点のうち番号最小のものでj頂点のループを作る方法の数である。よってO(K^2)で解けた。

ll dp[5010];

struct CrazyFunctions {
	int n;
	int k;
	int count(int _n, int _k) {
		n = _n, k = _k;
		C_init(n);
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		rep(i, 0, k) {
			rep(j, 1, k + 1) {
				if(i + j > k) continue;
				ADD(dp[i + j], dp[i] * C(k - i - 1, j - 1) % mod * fac[j - 1] % mod);
			}
		}
		ll res = dp[k];
		if(n != k) {
			MUL(res, C(n, k) * k % mod * mod_pow(n, n - k - 1) % mod);
		}
		return res;
	}
};

なんかO(N+K)で解いている人がいますが…よくわかりません…これが現実的な解法だと思います。

2018-12-19

AGC029

https://atcoder.jp/contests/agc029/tasks

冷えました…

A
結局はWを動かす操作です。
B
面白い。1,2,3,....2^30のグラフを考えると、明らかに木です。問題のグラフは明らかにこのグラフの部分グラフなので森です。
あとはgreedyに取っていけばいいです。ただし2^nは注意。
C
重めのO(NlogNlogmaxA)書いたら落ちてかなしい。ちゃんとO(NlogmaxA)にしてAC。てか最初からstackで良いことにきづけないの良くない。
D
めっちゃ解かれてて焦ったけど誤読してた。高橋くんは常に動かさないといけなくて、青木くんはブロック上に来たら横移動をやめます。
E
1を根とした木の上に行きたい気分なので、後はsimulationすれば解けるかなあとは思いました。
F
全然つっかえなかったので成長だと思う。うまく問題を分析して妥当な予想を立てながら解けてキモチイ。

頂点vを取る操作はだいたい点集合からvを削除する操作に言い換えられます。(細かい条件はあるが)
全ての点集合について一つ点を削除することができれば成功で、これは二部マッチング問題です。

2018-12-19

Codeforces Round #527 (Div. 3)

https://codeforces.com/contest/1092

だいぶ調子良かった。

A
WA on test1やったw
B
sort
C
長さN-1の文字列がほぼ答え。
D1
解いてないけど偶奇は見えた。
D2
一番短いものからやっていって、連結サイズが奇数になったらダメ。
E
これとけたのいいねえ。ある一つの点にすべての木をつなげればいいことがわかります。つなげるのは中心同士です。
F
一応全方位木DPなのか...?

Eが非自明感あったけど解けてよかったね。

2018-12-17

2018-2019 Russia Open High School Programming Contest, J: Two Prefixes

String

https://codeforces.com/contest/1090/problem/J

考察有りライブラリ使いまくりで楽しい。
まず文字数を固定します。するとTを少しずつずらした時何通り同じ文字列があるかみたいな問題になります。
こんな感じです。

Tを1文字shift
S:aadaa   |
T: aaaaaba|
文字列はaaaaaaba
↓
Tを2文字shift
S:aadaa   |
T:  aaaaab|a
文字列はaaaaaaab

i文字shiftした時の文字列をDiとしてDiとDjが同じ場合は辺を張るようにしてグラフを作ります。
i < jとして、DiからつながっているDjを考えたいです。するとj-i = lずれた先でも同じということは文字列Tがcyclicになっていることを表します。
よってDiがDjと繋がる条件はTがl周期の文字列でありかつS[i,i+l]=T[0,l]となります。
するとDiとつながっているDjのうちjが最小のものをjmin、jmin-i=lminとすれば、Diはj=i+lmin,i+2*lmin,i+3*lmin...としかつながりません。
さらに、S[i,i+l]=T[0,l]の条件も合わせて考えれば、Diから辺を貼るのはDjminのみで良いことがわかります。
こうして作ったグラフは木なので結局(グラフの頂点数-辺の数)で異なる文字列の数がわかります。
あとは文字数で固定するのではなくshiftの文字数で固定してiterationを回せばできます。
高速化ですが、S[i,i+l]=T[0,l]を判定するのはSuffix array, cyclicになっているかはMP法を使えばいいです。計算量は全体でO(NlogN)で済みます。

int N, M;
string S, T;

int fd(const vi& vec, int a) {
	return upper_bound(all(vec), a) - vec.begin();
}

void solve() {
	cin >> S >> T;
	vi vt = MP(T);
	int N = sz(S), M = sz(T);

	SA sa; 
	vi vs;
	rep(i, 0, N) vs.pb(S[i] - 'a');
	vs.pb(26);
	rep(i, 0, M) vs.pb(T[i] - 'a');
	sa.init(vs, 27);

	vi vec;
	rep(i, 1, M + 1) {
		if(vt[i]) {
			vec.pb(i - vt[i]);
		}
	}
	ll res = 1ll * N * M;
	rep(i, 1, N) {
		int d = sa.common(i, N + 1);
		res -= fd(vec, d);
	}
	cout << res << "\n";
}

2018-12-08

SRM埋め(4)

わりとeasyうまくなってきたし、easyとmediamともに残っているセットを残しておきたいので、mediam練習します。

SRM 732 mediam, hard
2問ともsurreal numberとかいう競プロではあまり馴染みのない道具を使う。知ってる人は一瞬だけど知らない人は絶対解けない。さらにテストケースが弱かったらしく、hardで嘘解法が通ったらしい。ひどいね。topcoderさんこういうのだけはやめてください。

SRM 731 med
勉強になった。式が出てきてなかなかO(K^3)から改善できなかったんですが、うまく期待値に言い換えなおすと出来ました。出てきたものを精査するのは基本中の基本ですができてなかったね。

SRM 730 med
完全にごり押してしまった…。それっぽい辺張ってdp復元。もっとうまい方針でやりたかった。

SRM 726 med
よくあるやつ。重心(2つあるならどっちでも良い)からtourして最後に重心と隣の点で終わればいいです。

omochan's diary

TTPC2019参加記