2018-11-18

CODE FESTIVAL 2018 に参加しました

CODE FESTIVAL 2018 に参加しました。
昨年は予選 C のギリギリで引っかかって通過したのですが、今度は予選 A で決められてよかった。

本選前

会場近くをうろうろしてました。
ちょうど同時期に開催されたきらら展の様子。

#code_festival pic.twitter.com/J0TDR5KAPM
— bwKVUbxF0G3 (@gzlcp) November 16, 2018

昨年と同じだったため、会場には迷わず行けました。
OP 映像に、昨年は見つけられなかった自分のハンドルネームを見つけて満足。

AtCoder ID じゃなくて twitter ID が載ってた
— bwKVUbxF0G3 (@gzlcp) November 17, 2018

本戦

A

beta.atcoder.jp
いきなり難しそうな見た目をしている。
300 点であることを信じて制約に目を向けると、辺長の下限が大きいため条件を満たすには a と b、b と c が隣接する必要があると分かります。このような 3 頂点の数え上げでは、真ん中（ここでは b）を固定すると見通しがよくなることを思い出すと、解くことができます（4:08）。

B

beta.atcoder.jp
普段あんまり見ない設定の問題。
300 点なので 5, 6 分考えれば解けるはずと思ったのですが、分からなかったため一旦飛ばして C をやりました。
G まで解いてから戻ってきて再び考察したところ、まず単調な条件での最小化なので二分探索が使えそう。さらに分母を適宜適量払いながら計算するとオーバー / アンダーフローを回避できることに気づき AC（151:16）。
実際には、式の両辺の対数をとって積を和に変換するのがいいらしい。たしかに、そっちのほうが汎用性がありそう。

C

beta.atcoder.jp
今回のコンテストの 300 点問題 3 つ中だと、一番競技プログラミングっぽい気がする。
まず問題文中に、目を引く強い仮定（全てのプラン i に対して、通話時間が A_i 分の場合には他のどのプランよりも通話料金が 1 円以上安くなることが保証されます。）があることに気づきます。これをなんとか活かしたい。
ある人に注目すると、その人の通話時間より A が大きいプランに関しては、かかる金額は B です。よって、そのようなプランの中で一番得なプランは簡単に見つけられます。通話時間より A が小さいプランに関しては、上述の仮定がなければいろいろな情報を考慮しなければならないのですが、仮定のおかげで A が大きいものほど得であると分かります。よって前者の最適値を適当な前処理やデータ構造で見つけ、後者の最適値を二分探索で見つけ、そのうちの小さい方が答えになります（20:51）。

D

beta.atcoder.jp
600 点の E より難しいと話題になっていた D。
略称の候補それぞれについて、いくつの文字列に採用できるか数える O(52^3 * N ≒ 4.2 * 10^9) でも通ってしまいます。
自分は O(52^2 * N) で解いた気になっていたのですが、今見たら O(52^3 * N) でした。
52 の指数を 2 に減らせるらしいのですが、よく分かりません。難問（56:28）。

E

beta.atcoder.jp
どこか（蟻本）で見たような問題ですが、微妙に設定が違います。ただ、基本的なアイデアは似てると思います。
いろいろと解法があるらしい。
自分の場合、水を注いでもらうだけなら無料、飲むときにお金が発生すると考えて、基本的に常に水を K 本持ち歩きつつ、今の街でもらえる水よりコストがかかる水は全て捨て、そのあともらえるだけ水をもらう、という貪欲なアルゴリズムを考えました。
これは deque を使えばうまく実装できます（75:53）。
提出コード
beta.atcoder.jp

F

beta.atcoder.jp
E と同じく、とりあえず全て食べて、あとで都合が悪くなったら美味しさの小さいものからなかったことにすればいいのでは、と貪欲に考えたのですが WA を出してしまう。一旦パスして G と B を解きました。
考察に戻り、コンテスト終了 10 分前にようやく、それだと不都合があることに気づけたのですが、満足に考察する時間はなく未着手。難問。

G

beta.atcoder.jp
適当にひよこの振り分け方を 1 つとります。その振り分けにおいて、あるかご x にはかご y より多くのひよこがいるとします。このとき、もしかご x に、かご y のいずれかのひよこより大きいひよこがいたとすると、この振り分け方は最適ではありません。なぜならば、そのようなひよこ同士をスワップすることで、ストレスの総和を小さくできるからです。
このことに気づくと、適切なひよこの振り分け方は、小さいひよこから何匹かを 1 つのかごに、残ったひよこのうち、小さいひよこから何匹かを 1 つのかごに、といったものと分かります。また、このようにして作られていくかごに含まれるひよこの数は、単調非増加とも分かります。
前者の性質のみを使うと、愚直計算量 O(N^3) の DP を作ることができます。後者の性質も鑑みると、一度にあまりたくさんひよこを含むかごを作る必要がなくなります（たくさん含みすぎると、今まで作ったかごにそれより真にひよこの少ないものがあることになる）。よって、DP[i][j] := 小さい方から i 番目のひよこまでで j 個のかごを作るときのストレスの総和の最小値、とすると、このテーブルの二次元目を埋める計算時間が O(NlogN) に落ちるため、全体で O(N^2logN) で解くことができます（130:34）。

H 以降

読んでません。

結果

自分の予想を大きく上回る？ 22 位で終わることができました。賞金は全く狙っていなかったのですが、もうちょっとでもらえたと思うと少し悔しい。パーカーも無事手に入れることができました。

提出直後20位だったので30分間サーバー壊れてたら賞金もらえる
— bwKVUbxF0G3 (@gzlcp) November 17, 2018

チームリレー

恒例のチームリレーです。本戦の順位が思いの外よかったため、図らずも難しい問題を担当することになりました。

ゼッケン付けたまま帰宅する人が多いと話題のチームリレー
— bwKVUbxF0G3 (@gzlcp) November 17, 2018

我々のチームの基本戦略は、前半の問題はペアで取り組み確実に解く、残った後半の問題は臨機応変に解いていく、というものでした。
自分はペアとしては C を考え、H を考察・実装する役割でした。
C 問題については、自分が計算量の見積もりを間違えるも（すいません）全探索で行けそうと分かり、チームメンバーに実装をお願いし AC。
C が終わってからは H 問題を考えました。なんか高速ゼータ変換（確認したら高速メビウス変換だった）的なあれで高速化をすればなんかうまく数え上げれそうな気がすると気づくも、実装が重そうな上実装キューも詰まっていたため、他の問題も見てみたり、デバッグに加わろうと試みたりしていました。そのままコンテストは終了。上位 3 チームのみ口にできる高級牛肉は味わえませんでしたが、代わりに（？）ピザや寿司を食べました。

まとめ

本戦もチームリレーも、昨年の反省を活かし（？）、少しはよく立ち回れたような気がしました。
来年も参加したいか問題なのですが、競技プログラミングの競技レベルが爆発的に上昇してる現状もあるので、謙虚にコツコツ予選突破を目標にしてやっていこうと思います。

2018-02-13

JOI 17 本選-定期券

問題

https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf

考察

重要な性質として、ある定期券のもとでの $U$ から $V$ への最短経路は、

$U$ $\rightarrow$ [定期券に含まれない区間] $\rightarrow$ [定期券に含まれる区間] $\rightarrow$ [定期券に含まれない区間] $\rightarrow$ $V$

のような構成になると言えます（各区間は $∅$ も認める）。
なぜなら、仮に [定期券に含まれる区間] が複数に分かれて存在している場合、その最初の区間の最初の駅、および最後の区間の最後の駅を定期券に含まれる区間のみで繋ぐことでより運賃が安くできるからです。
$N \leq 300$ の部分点については、[定期券に含まれる区間] の始点と終点を全探索することで解けます（ある 2 つの駅 $a$ と $b$ をこの順に通る $S$ から $T$ への最短経路、つまり適切な定期券が存在するかは、 $d_{ij}$ を $i$ と $j$ の距離として $d_{Sa} + d_{ab} + d_{bT} = d_{ST}$ となるかを見ることで判定できます）。
動的計画法を利用すると、さらに計算量を小さくすることができます。
$U$ からいくつかの駅を経由して定期券の区間に合流し、そのまま $S$ から遠ざかるように進んで適当なところで分かれ $V$ を目指すケースの最適値をまず考えます。逆（定期券の区間に合流したあと、 $S$ に近づくように進む場合）も同様に計算できます。
以下、 $j$ を含むような $S$ から $i$ への最短経路が存在するとき、 $j$ を $i$ の 上流の駅 と呼びます。 $i$ の上流の駅全体を集合 $K_i$ とします。

$dp_{0i} := min_{j \in K_i}\{d_{Uj}\}$
$dp_{1i} := min_{j \in K_i}\{$ $j$ で定期券区間を分離して $V$ を目指したときの（合流するまでも含む）運賃の最小 $\}$

のように定めます。また駅 $i$ と接する駅のなかで

$d_{Sj} + d_{ji} = d_{Si}$

を満たす $j$ を、 $i$ の すぐ上の駅 と呼ぶことにします。逆に、任意の $S$ から $i$ への最短経路は、上の式のように適当なすぐ上の駅を経由する形に分解できます。
そして $i$ の上流の駅は、それ自身を除けば何らかのすぐ上の駅の上流の駅でもあります。
これを踏まえると、 $dp_{0i}$ および $dp_{1i}$ は、 $i$ のすぐ上の駅全体の集合を $L_i$ とすると、

$dp_{0i} = min(d_{Ui},\,min_{j \in L_i}\{dp_{0j}\})$
$dp_{1i} = min(dp_{0i} + d_{iV},\,min_{j \in L_i}\{dp_{1j}\})$

のように更新ができます。配列の更新は $S$ に近い駅から行っていくことで、うまく動きます。以上より最適値は $dp_{1T}$ となる……ように見えますが、実はこの動的計画法では、定期券の区間に一度も合流しないケース（入力例 2 のようなケース）を考慮していないため、 $min(dp_{1T},\,d_{UV})$ が本当の求める値になります。

コード

ll N,M,S,T,U,V;
vector<P> graph[100010];
ll fromU[100010];
ll fromV[100010];
P dp1[100010];
P dp2[100010];

void dijkstra(ll s, vector<ll>& d) {
	REP(i,N) d[i]=INF*INF;
	d[s]=0;
	priority_queue<P,vector<P>,greater<P>> q;
	q.push(P(0,s));
	while(!q.empty()) {
		ll cost=q.top().first;
		ll p=q.top().second;
		q.pop();
		if(d[p]!=cost) continue;
		REP(i,(ll)graph[p].size()) {
			ll adj=graph[p][i].first;
			if(d[adj]>d[p]+graph[p][i].second) {
				d[adj]=d[p]+graph[p][i].second;
				q.push(P(d[adj],adj));
			}
		}
	}
	return;
}

ll dp() {
	vector<ll> d(N);
	REP(i,N) d[i]=INF*INF;
	d[S]=0;
	priority_queue<P,vector<P>,greater<P>> q;
	q.push(P(0,S));
	while(!q.empty()) {
		ll cost=q.top().first;
		ll p=q.top().second;
		q.pop();
		if(d[p]!=cost) continue;
		REP(i,(ll)graph[p].size()) {
			ll adj=graph[p][i].first;
			if(d[adj]+graph[p][i].second==d[p]) {
				dp1[p].first=min(dp1[adj].first,dp1[p].first);
				dp2[p].first=min(dp2[adj].first,dp2[p].first);
			}
		}
		dp1[p].second=dp1[p].first+fromV[p];
		dp2[p].second=dp2[p].first+fromU[p];
		REP(i,(ll)graph[p].size()) {
			ll adj=graph[p][i].first;
			if(d[adj]+graph[p][i].second==d[p]) {
				dp1[p].second=min(dp1[adj].second,dp1[p].second);
				dp2[p].second=min(dp2[adj].second,dp2[p].second);
			}
			if(d[adj]>d[p]+graph[p][i].second) {
				d[adj]=d[p]+graph[p][i].second;
				q.push(P(d[adj],adj));
			}
		}
	}
	ll ret=min(dp1[T].second,dp2[T].second);
	return ret;
}

int main() {
	cin>>N>>M>>S>>T>>U>>V;
	S--; T--; U--; V--;
	graph.resize(N); dp1.resize(N); dp2.resize(N);
	fromU.resize(N); fromV.resize(N);
	REP(i,M) {
		ll A,B,C;
		cin>>A>>B>>C;
		A--; B--;
		graph[A].pb(P(B,C));
		graph[B].pb(P(A,C));
	}
	dijkstra(U,fromU); dijkstra(V,fromV);
	REP(i,N) {
		dp1[i].first=fromU[i];
		dp2[i].first=fromV[i];
	}
	cout<<min(fromU[V],dp())<<endl;
}

2018-02-13

JOI 17 本選-団子職人

問題

https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf

考察

一つの串団子と、それに含まれる緑色の団子は一対一に対応します。
よって各緑色の団子について、「それを使って串団子を作るか？　作るなら縦と横どちらの向きに作るか？」を考えることにします。
分けては考えられない、つまり「片方の去就によって、もう片方のとれる道が少なくなる」ような緑色の団子の組はどんなものになるでしょうか？
実験をしてみると、ある 2 つの団子が／の向きに隣り合っている場合、それぞれ影響しあう可能性があると分かります。逆に、そのように隣り合っていなければ、互いが影響を及ぼすことはありません。
よって各緑色の団子は、

f:id:gzlku:20180213194010p:plain

こんな感じで、それぞれ独立に考えていい、いくつかのグループに分けることができます。
各グループ内で作れる串団子の最大数は、例えば左下のほうから、

1. 縦方向に串団子を作る
2. 横方向に串団子を作る
3. 串団子を作らない

の場合分けをしつつ、DP の要領で計算していけばいいです。

コード

ll n,m;
char g[3000][3000];
ll dfs(P p, ll x, ll y, ll z) {
        // x: 縦に団子をとる y: 横に団子をとる z: 団子をとらない
	if(p.first<0||p.second>=m
            ||g[p.first][p.second]!='G') {
		return max(max(x,y),z);
	}
	g[p.first][p.second]='#';
	ll nx=0,ny=0,nz=0;
	nz=max(max(x,y),z);
	if(p.first-1>=0&&p.first+1<n&&
	   g[p.first-1][p.second]=='R'&&g[p.first+1][p.second]=='W') {
		nx=max(x,z)+1;
	}
	if(p.second-1>=0&&p.second+1<m&&
	   g[p.first][p.second-1]=='R'&&g[p.first][p.second+1]=='W') {
		ny=max(y,z)+1;
	}
	p.first--; p.second++;
	return dfs(p,nx,ny,nz);
}

int main() {
	cin>>n>>m;
	REP(i,n) REP(j,m) cin>>g[i][j];
	ll ans=0;
	for(ll i=n-1; i>=0; i--) for(ll j=m-1; j>=0; j--) {
			if(g[i][j]=='G') ans+=dfs(P(i,j),0,0,0);
	}
	cout<<ans<<endl;
}

2018-02-13

JOI 17 本選-美術展

問題

https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf

考察

展示する最大の美術品と最小の美術品がどちらも不定だと考えづらいので、片方を固定してみます。ここでは最大を固定するとします。
まず、同じ大きさの美術品がない場合を考えます。
あらかじめ、美術品を大きさに関して昇順にソートしておきます。また、このもとでの価値についての累積和を保存する配列を $ACM$ とします。
美術品 i が大きさ最大になる展示方法の評価値は、

$S - (A_i - A_{min})$

です。仮に最小の大きさを与える美術品が $j (j < i)$ であるとすると、これは、

$(ACM_i - ACM_j + B_j) - (A_i - A_j)$
$= (ACM_i - A_i) - (ACM_j - B_j - A_j)$

と書けます（最大値と最小値の間の大きさの美術品は全て展示したほうがいいので）。
つまり、

$C_j = ACM_j - B_j - A_j$

とおけば、評価値は $ACM_i - A_i$ から $C_j$ を引いたものになるわけです。 $C_j$ は「美術品 j の最小としての不適当さ」みたいなものです。
よって $j < i$ の中での $C_j$ の最小値が分かれば、最大を固定した上での最適値が分かります。
全ての美術品にわたる上記の最適値の max が答えであり、これは美術品を小さい方から走査していくことで O(N) で計算ができます。
最大値や最小値と同じ大きさの美術品は全て展示した方がいいことをふまえると、このアルゴリズムは重さが distinct でなくても正しく動きます。

コード

上書きして消えた

2018-02-13

JOI 17 本選-ストーブ

問題

https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf

考察

まず分かることとして、K 個あるマッチは使い切ってしまったほうがお得です。
また、マッチを付けるのは来客の直前、そして消すのは客が帰った直後にしたほうがいいのも明らかです。
これらをふまえて、始めの客が来てから最後の客が帰るまでのストーブの様子を考えてみると、付いている期間と消えている期間は交互にあり、付いている期間の合計は K 個（それらに挟まれる消えている期間の合計は K-1 個）、といった感じになっているはずです。また、消えている間に来客を迎えることはできないので、1 つの消えている期間は、ある客が帰ってから次の客が来るまでの谷間の時間にあたっているはずです。
結局のところ、始めの客が来てから最後の客が帰るまでの間でストーブを消すことができるのは、N-1 個ある来客の谷間のうちの高々 K-1 個と分かります。
各谷間の長さを計算し、大きい順に K-1 個和をとって全体から引けば正解できます。

コード

上書きして消えた