ICPC2018国内予選参加記

ニャ

先日開催されたICPC国内予選に参加してきました。その感想などを書きたいと思います。 チーム名はTigerzet、チームメンバーは

etonagisa(@eto_nagisa)
nikutto(@nikutto_)
gazelle(@gzlcp)

チーム名はメンバーの名前から少しずつとって作りました。そうは見えないでしょうけども。

戦略

基本的に考察はnikuttoが最強なので、gazelleとぼくでABCを解いている間にD,Eあたりをnikuttoに考察してもらうという作戦でやっていっています。 しかし今回は実験室のプリンターが使えず、問題を同時にせいぜい2つぐらいしか読めなかったので作戦が破綻しました(チーン)

できごと

開始直後

nikuttoにテンプレートを書いてもらいつつ、A問題を読む。やるだけなので実装方針を考えつつテンプレートの完成を待つ。double嫌いマンなのでn*v[i]<=sumで比較しましたね。

(3:57)

A問題AC。
Aを書いている間にgazelleにBを読んでもらっていた。こーれは大変そうだと思いつつ、しばらくBを任せる。その間にCを読んでいた。

(7:00ぐらい)

アーこれは√bまで累積和をとるだけですねハイ(嘘)と言ってBに戻る。戻ってすぐnikuttoが方針を提案してくれた。可能なフロアの長さの最大値は√bぐらいなのでこれを全探索して判定問題にすればよいといわれる。確かにこれでよさそう。紙コーディングしつつBを見る。 Bは計算量はなんとでもなるのできれいな方針で実装するだけのやつだとわかる。折る旅にあたらしい配列を用意して、折り目から折り目と垂直にたどって新しい配列に足していくという方針を提案、これが受け入れられ実装をしてもらう。これが結構大変だった。

(37:41)

B問題AC。

(43:44)

Cは方針も実装も固まっていたので一瞬で書けた。 C問題AC。
Cを書いてnikuttoに進捗どうですかをすると、Dは枝刈り全探索するだけだという。確かにサンプルに最大ケースがあり、計算回数がこれで抑えられそうであるので、それでいいですといいペアプロに入る。ぼくは隣で些細なミスを指摘するだけで終わり、一瞬でDが書きあがる。天才か?

(58:05)

D問題AC。
F,G,Hを読んで考えていたgazelleと一緒に考察を進める。その間にnikuttoがEを書くというので任せる。Fの知見が少し生まれたり、Gを考えたりHがフローっぽいな~~~って言っていた。

(1:29:28)

そうこうしているうちにEのサンプルが合わなかったり合ったりした。提出。通った。nikutto天才か????
E問題AC。
この時点で順位表を見たところ4位だったので盛り上がっていた。 Fは我々には解けませんとなったのでGを頑張ることにした。

(2:00ごろ)

gazelleからGの完全な考察がわいてきた。曰く、カッコの途中で文字列を打ち切ることは許されないので、カッコを使う場合はカッコ内全体をすべて使う必要がある。すると、カッコは定数と見なせるので、定数と+と*からなる式で、計算結果がnになる部分文字列を見つければよいという問題になった。式の値は広義単調増加であるので、これはしゃくとり法でできる。カッコ内についても部分問題を解くことで答えが求まる。これで合っていると確信。ただし実装がクソ重いことがわかっていた。 nikuttoはHを解いていたが、諦めて3人全員でGに取り組むことにした。

(2:50ごろ)

Gがかけた。実行!!どんなケースでも0が返ってくる!!(これは間に合わんな・・という雰囲気になった)がまあしばらく頑張ってみる。

(3:00)

Gは無理でした。

結果

5完8位、学内では3位。まず、ここまでの高順位をとれるとは思っていませんでした。5完早解きセットで早解きができたことが大きいのかなと思います。 それと今年はKUが強い・・。KUの上位は6位、7位、8位、11位となって、11位のチームが予選落ちしそうというまさかの結果になってしまいました・・かわいそう

今回はnikuttoにだいぶ活躍してもらいました。アジア予選横浜大会ではもっとチームの力になりたいですね。

部分集合内を1回ずつ見るビットdpを高速に計算する

まえがき

CSA Round #74 5問目 Good Permutation を解きました。コンテスト中には考察はほぼできていたのですが、ある部分での高速化ができず通すことができませんでした。その部分についての知見を頂いたので、記事にして残しておこうと思います。 なんかそれっぽい部分は2進数だと思って読んでください。

似たようで簡単な問題

次のようなビットDPを計算することを考えます。ビットを集合としてみる場合、ビットが立っているとき対応する要素が集合に含まれているものとみなします。またsub(i)をiを集合としてみたときの部分集合の集合とします。(ex. sub(101)={101,100,001,000})
ビット長はnとします。
A:長さ2^nの配列が与えられて、
dp[i]=max{k∈sub(i)}(A[k]))
これはi=0から初めて、iの立っている各ビットを1つずつ0にしたもの全てとmaxをとる遷移をすればよいです。以下のようなコードで実現できます。

for (int i = 0; i < (1LL << n); ++i)dp[i] = A[i];

for (int i = 0; i < (1 << n); ++i) {
  for (int j = 0; j < n; ++j) {
		if (i&(1 << j)) {//iのjビット目が立っているなら
			dp[i] += dp[i ^ (1 << j)];
		}
	}
}

本題

次のようなビットDPを計算します。
A:長さの2^nの配列  
dp[i]=\sum_{k∈sub(i)}^{}A[k]
前の節でのdpの定義のmaxの部分がsumに変わっただけですね。しかしこれは先程と同じようにして解くことはできません。具体例を用いて理由を説明します。 先程の問題でdpを計算する場合、dp[101]=dp[100]+dp[001]+A[101]=dp[000]+A[100]+dp[000]+A[001]+A[101]=2*A[000]+A[001]+A[100]+A[101]となり、A[000]が2回足されてしまいます。iに立っているビットが複数ある場合に、どのビットから0にしていくかの順序が変わると別の遷移ができてしまい、複数回足されることになってしまいます。(例えば 101→100→000と101→001→000) 前の問題では演算がmaxで、max(a,a)=aであったために問題はなかったのですがsum(a,a)!=aではないため、各A[i]が複数回足されると困ってしまいます。
まず愚直な解法として、毎回部分集合を列挙して足す方法を考えてみます。これは以下のようなコードになります。
(配列名をdpのままにしているけれどこの解法はdpではないです)

for (int i = 0; i < (1<<n); ++i) {
	for (int j = i;; j = (j - 1)&i) {
		dp[i] += a[j];
		if (j <= 0)break;
	}
}

内側のループは、iの部分集合を列挙しています。iの部分集合の数は2^{popcnt(i)}個あるので、内側のループはpopcnt(i)回回ります。
従って全体でのループ回数は \sum_{i=0}^{2^n} 2^{popcnt(i)}です。
popcnt(i)==kとなるiは_n C _k個あるので、これは\sum_{k=0}^{n} {_n C _k 2^k}と等しいです。
さらにこれは (1+2)^nを展開した形になっているので、全体のループ回数は3^nであることが分かります。
少し遅いですね。n=20が通らないぐらいでしょうか。

実はこのdpは O(n*2^n)で計算することができます。
結論から述べますが、これは以下のようなc++のコードで実現できます。

for (int i = 0; i < (1LL << n); ++i)dp[i] = A[i];

for (int i = 0; i < n; ++i) {
	for (int j = 0; j < (1 << n); ++j) {
		if (j&(1 << i)) {//jのiビット目が立っているなら
			dp[j] += dp[j ^ (1 << i)];
		}
	}
}

コードを見ると、iとjのループの順番が入れ替わっているだけです。これでうまくいくことの証明を帰納法で行います。

証明

f(j,i)=jの右からiビット(1-indexed)はjの部分集合になっていてかつjの左からn-iビットはjと等しいような整数全体の集合
とします。 (ex.f(1011,2)={1011,1010,1001,1000})
示すべき性質は、
「外側のループがi回終わったとき、dp[j]の値は、全てのk∈f(j,i)についてA[k]の和をとったものと等しい」です。この性質をPと呼びます。
i=nのときPが成り立てば、このアルゴリズムの正当性が示せます。

i=0の場合

f(j,0)={j}であり、ループに入る前はdp[j]=A[j]であるため、i=0のときはPは成立します。

i=mのとき成立することを仮定し、i=m+1のとき

(1)jのm+1ビット目が0のとき
まず、f(j,m)=f(j,m+1)が成り立つことがわかります。
さらにjのm+1ビット目が0である場合、m+1回目のループではdp[j]の値は変わらないことがわかります。従って仮定よりPが満たされることが示せます

(2)jのm+1ビット目が1の場合
f(j,m+1)は、f(j,m)全体と、∀ k∈f(j,m)のm+1ビット目を0に
したもの全体の集合の合併となるから、
f[j,m+1)=f(j,m)∪f(j^2^m,m)が成り立ちます。ここで^は排他的論理和です。
さらに、f(j,m)とf(j^2^m,m)は排反です。これは、f(j,m)の任意の要素のm+1ビット目は1であり、f(j^2^m,m)の任意の要素のm+1ビット目は0であることから分かります。
一方、m+1回目のループではdp[j]の値にdp[j^2^m]のみが加算されています。j^2^mのm+1ビット目は0であることを考えると、dp[j^2^m]は∀ k∈f(j^2^m,m)についてのA[k]の和と等しく、dp[j]は∀k∈f(j,m)についてのA[k]の和と等しいです。
したがって、m+1回目のループ終了時ではdp[j]は∀k∈f(j,m+1)についてのA[k]の和と等しいので、i=m+1のときもPが成立することが分かります。

以上から、数学的帰納法より∀i 1<=i<=nについてPが成り立つことが分かります。
つまりこのアルゴリズムの正当性も示せました。

おわりに

競プロ的には通るnの範囲がn<=18ぐらいからn<=25ぐらいに広がるぐらいの差ですが、実際にこの差で通らなかったので意義はあると思い記事にしました。実はもっと早くなったり、間違いがあった場合は教えてくださるとうれしーです。

KUPC2017に参加しました

KUPC2017に参加しました

参加記を書くまでがコンテストですよね、もう数日たってますけれども。

KUPCは今回が初参加でした。京都オンサイトで参加し、6完して京都で3位、全体で33位だったので結構満足しています。

以下各問題の感想を書いていきます

A Credits

大きいほうからとっていけばよい

B Comphor Tree

Tを2で割っていってSに到達すればok。その前に0になってしまうとだめ

数字が大きいほうに向かうときは二通りあるけど小さいほうに行こうと思ったら1本ってところがポイントっぽい

結構好き

C Best Password

辞書順最大のものかつ長さを短くしたいので、詰められるだけ左に詰めていくことをします(これはO(n))

ただしこれだとaazみたいなケースで死ぬので、更新されなくなるまで無限ループさせてAC(は?)

合計のorderはたぶんO(n^2)

D Sanmoku

1時間半ぐらいこの問題にかけた。

とりあえずn<3のときは1色で塗れるしn>=3のときは2色で塗れることが分かったので、あとは何通りかを試していくのですが・・

ずーっとn=4のケースをこねくりまわして法則を探そうとしていて、いったん別の問題にうつった後帰ってきてから大きいケースで試したところ8通りしかなくね?と気づきAC。

n=3のときは全探索するコードを書いたのですが、n=5のときもこれで試せばよかったです。(少なくとも8通りはあることはそのときにすでに気づいていたので)

E Treasure  Hunt

まずn+m頂点のグラフを用意します。

鍵iが宝箱x_iとy_iを開けられるとき、i+nとx_i,i+nとy_iの間に辺を張ります。

こうしてできたグラフの連結成分ごとに考えていきます。

まず連結成分内の鍵の個数と宝箱の個数を比べ、鍵の個数>=宝箱の個数であればその宝箱は全て開けることができます。

また、鍵の個数<宝箱の個数の場合でも、鍵と同じ個数で、任意の組み合わせの宝箱を開けることができます。

(証明は読者への課題とさせていただこう)

よって各連結成分ごとに貪欲的にとっていけば答えが求まります。

よい問題だと思いました

F 575

ウーン難しい。提出状況を見てこれはやべーと思ってあんまり考えていませんでした。

解説を見てもこれをコンテスト中に解くのはつらいなあとか思ってました。

G encode/decode 2017

発想はそこまで時間がかからなかったけれども実装がつらいつらい

方針としては長さ63の鎖を用意し、根からi番目の頂点が整数xのiビット目に対応していて、頂点iの次数が3ならそのビットは1,2なら0という定義です(つまり子が1つなら0、2つなら1)。

これを二分木の形で表現しようとすると最大で63*2の頂点が必要となり少し100をオーバーしてしまいます。そこで1つゴミ頂点を用意し、i番目のビットが立っているならそのゴミ頂点と結ぶという実装をしました。これにより頂点数は65ぐらいで収まります。

のですが、最初の木にある辺を使ってはいけない、多重辺は禁止、自己辺の禁止ということでいろいろと大変な実装をすることになり、40分ぐらいひたすらコードを書いていました。

最初の木はなくてもよかったんではと思います。

H以降

ここまでのf以外の6問を通した時点で残り10分だったので、ほとんど考えていません。

焼肉

おいしかった

最後に

初めてのオンサイトコンテストで緊張していましたがなんとかやれました。

人見知りゆえあまり交流できなかったのが悲しいですね・・人と話すことは嫌いではないんですがなんともまあ(´・ω・`)

来年は運営側に回りそうです。よろしくお願いします

SRM716 div1

前回初参加した結果おかしなレーティングになったためdiv1に放り込まれました。

結果は一完。かなしい

 

easy

bc>=ab>=caと仮定します。

このときA='1..1'(max(ab,ca)個)、B='1...1'(ab個),C='1...1'(ca個)とすると、AとB,BとCについては条件が満たされています。あとはBとCの条件を満たすようにすればよいのですが、この状態からBとCの末尾に0を追加してもAとB、AとCのLCSは変わらないことがわかります。したがってBの末尾にbc-ab個の0,Cの末尾にbc-ca個の0を追加することで、BとCのLCSは1..10..0(min(ab,bc)個の1,bc-min(ab,ca)個の0)となり、この長さはbcです。以上の操作によって得られた文字列が答えです。あとはab,bc,caの大小について場合分けをして頑張ると通ります。

 

medium

時間内には通せませんでした。

 

まず根からSに含まれる距離の移動のみを行ってたどり着ける頂点を列挙できたとします。この頂点がたどり着ける頂点のすべてであり、逆にこの頂点集合内での任意の2頂点間での移動は全てSに含まれる距離の移動のみで可能であることがわかります。したがってこの頂点集合内で2重ループを回して2頂点間の距離を列挙し、その集合にSが含まれればPossible、そうでなければImpossibleです。

 

根からたどり着ける頂点の列挙ですが、僕は深さに関する(01でない)ナップサック問題のようにして実装しましたが、何か別の方法はないですかね。

また2頂点間の距離を予め計算しておく必要がありますが、これは単純にn回bfsをする方法と、LCAを用いる方法があります。前者では計算にO(n^2),クエリにO(1)かかり、後者では実装によりますが僕の場合は計算にO(nlogn),クエリにO(logn)かかります。今回はO(n^2)回2頂点間の距離を取得するので、前者であれば全体の計算量はO(n^2),後者はO(n^2logn)となります。僕のLCAライブラリが貧弱なため、後者ではTLEが発生しました。

hard

わからん(´・ω・`)

あとがき

レーティングは1765から1741に下がりました。下がるのは当然ですが全然下がってませんね・・topcoderレーティングはよくわかりません。

SRM715 div2

先日のSRMに出ました

SRMに出るのは初めてでいろいろ戸惑った・・

 

easy

4重ループをかくとACする

medium

+-+とか-+-とかいうのは明らかに無駄でやらないほうがマシなのでありえるのは

--..+++か++..----のみだけどこれは片方だけやっても最大-最小は変わってないので

どちらかのみを実行するとしてよいから

結局+と-の個数を数えて大きいほうが答え

hard

a1[0]は必ず木の根になる(これをrとおく)

a2の要素のうち、rがあるindexより左の要素は、根の左の部分木

同様にrがあるindexより右の要素は根の右の部分木

これにより根の左と右の部分木のサイズが分かるので、a1,a3を分割できる

この時点で整合性がとれていない場合はImpossible(setにぶちこんで==とかでかくにんすればいいかな)

あとは再帰関数で左と右の部分木に対してチェックしていく

このとき{s[0],s[2],s[4]},{s[1],s[3],s[5]}は{"pre","in","post"}に等しいという謎に見える制約が効いてきて、6つのvectorを頑張って並び替えて同じ関数を呼ぶだけでよくなる

後は左の部分木と右の部分木が両方PossibleだったらPossible,そうでなければImpossibleを返すようにすればよい

ただし、空のvectorが渡されてきた場合はPossibleを返すようにしないと根を確保しようとする時点でout of rangeで落ちる

 

div2で2位になってレートが1765になった(レーティングシステムなんとかして)

次はdiv1でぼっこぼこにされてきます