antaの競技プログラミング練習日記

問題

いくつかの企業がある。それぞれの企業はデータを処理して独自形式のデータにする。
企業はそれぞれデータの処理数に上限がある。また、処理できるデータの形式にも制限がある。もちろん、データ処理の仕事の依頼にはコストがかかる。これは、処理するデータ量にかからわず、1データでも処理するなら定額のコストとなる。
i番目の企業の企業名を表すnames[i]、処理できるデータ形式の集合を表すprocess[i]、仕事依頼のコストを表すcost[i]、処理数の制限を表すamount[i]がそれぞれ与えられる。
さらに企業名company1とcompany2が与えられる。company1の形式のデータをcompany2の形式のデータに処理したい。処理できるデータ量はできるだけ多くしたい。その中でかかる合計のコストを少なくしたい。そのうちで辞書順最小の企業名のリストをvectorで求めよ。

2 ≦ |names| ≦ 12
0 ≦ cost[i] ≦ 1000000
1 ≦ amount[i] ≦ 1000000
company1 ≠ company2

解答

http://maximum-cup-2013.contest.atcoder.jp/

Problems

A

最初関節点？？？二重連結成分？？？とかよくわからなかった。
その後「まず最小の本数」なことをきちんと考え、「3頂点以上あれば、Hamiltonian cycleだな」と気づいた。
これは普通にbitDPすればよい。
しかしなぜか「2頂点の時は辺が1つ必要だな？」と勘違いしてWA。これはとても後になって気づいてなおしてACした。

B

入力の数が明記されてないがどうせ解けるくらいしかこないよな…と思いつつとりあえず素数列挙して試し割りするだけで通った。

C

線分交差判定するだけ。
幸い厳密な判定をするライブラリを書いてあったので簡単に通せた。

D

たぶん(G_i,G_j)の二等分線をG_kとの距離で制限した線分上のダイクストラだろうなーと最初に思った。
しかし幾何は苦手でEPSとか嫌だったので無視した。
最後に解こうかと思ったがどうも幾何は苦手でできなかった。
ちなみに上に書いてあるような線分の集合を「ボロノイ図」と言うらしい(名前は知ってたけどあんまり知らなかった)。

E

期待値の線形性でやるだけ？と。明らかに「のろのろウサギ*(N)」の節が怪しいのでClar飛ばして後に回す。でもClarでは「問題読んで下さい」としか言われなかった…
わからなかったのは「10枚目ごと」と書いてある、この初期オフセットというかなんというか。
たとえば「5,15,25…枚目に出る」となっていても問題文の条件を満たすように思えるのだけど…
まあ「10,20,30…枚目に出る」と仮定して解いた。
が、WA。と思ったらしょうもない所でミスっていた：

if(name.find("Alicia")) ...

直してAC。

F

Clar飛ばしたりしてた。
解法は割とすぐ浮かんだ。重み付き2部マッチング。
コストは(-魔力,距離)の辞書順順序のペアで持つようにすれば「魔力最大」の制約を満たす。ペアは適切なlong longで大きな基数を考えて持ってもよいし普通にペアを持って足し算・negate・比較を定義してもよい。
この優先順位のあるコストを直接大きな基数を考えたコストでやるテクニックは"SRM 433 DIV1 Hard BarbarianInvasion"でやったので思いつけた。
さて、WAった。よく考えるとMinimumCostMaximumFlowであるから、魔力0の人がいる場合にそれにマッチしようとしてしまうようだ。これは単に魔力0の人を無視すればよい。AC。

G

(階層,x,y,min(レベル,101))で持ってダイクストラやるだけ？と。とりえあず実装することに。
「階段の移動に1単位時間かかる」を見逃してデバッグしたりして、実装できて、提出。
さて、WA。
本当によくわからなかったが、最後のケースでだけ落ちているようなので基本的には問題ないはず。問題文をよく読むことに。
それなりに時間がたったのち、気づいた！思わず「あぁー！」と声を出してしまった。
今の地震の影響で現在いる階から下の階に下りられなくなっていることが判明しました！
…
現在いる階から下の階に下りられなくなっている！！！！！
つまり、90階のマップが与えられているとしても初期位置が95階であったら95階から94階に行くことはできない！
それに気づけたら後は簡単。数行直して提出。AC！

H

2分探索でacyclic判定するだけ？と。
座標圧縮でp[i]∪l[i]∪r[i]だけ考えればいい。なぜなら、まず辺が張られない場所は矛盾と関係ない。次に、辺が包含関係にあるならその辺の少ないほうは無視しても同じ。だから。
速度が気になったが提出。AC。

I

最後に開いた問題。
さて、ハミルトン路。
色々考えると、へびの胴体の状態は別に保存しなくても良いことがわかった。なぜなら胴体の番号をxとすると、(x-1)ステップ以上経った後なら「この胴体は既に訪れた場所にある」、つまり「明示的に胴体を避けなくても訪れたかどうかだけ判定すれば良い」ことがわかり、(x-1)ステップ未満では「この胴体は最初に配置されている番号(x-ステップ)の胴体の場所にいる」ことがわかるので、つまり「ステップ数だけで判定できる」、また「ステップ数は既に訪れた場所の数で計算できる」。
さて、枝刈り全探索＋メモ化でもするか、と。
状態は(頭x,頭y,壁または通った場所のbit mask)。
とりあえずdx,dyの順番をランダムに試すようにしたけれどこれは関係あるかはわからない。
枝刈りとして、「連結成分が2つ以上になったらもう達成できない」をやった。さらに連結成分の個数が2つ以上かどうかは(壁または通った場所のbit mask)だけで判定できるので、それを別個にメモした。
dx,dyをrandom_shuffleするところでグローバルのdx,dyを書き換えてしまうというバグで1WAして時間をつかったが、直して提出。
TLE,MLEが気になったが案外52ms/1936KBでAC。

J

明らかに座標圧縮して2次元クエリやるだけ。WaveletMatrixでもいいかなと思ったが入力数が明記されていない以上TLEが怖く、できる限り高速なFenwick木を動的に使うテクでやることにした。
実際にはインデックスを左から見ていき、a[index-k]の場所に1を足す、ということをすればよい。
あっさりAC。だが565msだったのでWaveletMatrixではTLEしていたかもしれない。
単にRMQ・あるいは単に右端もしくは左端からの最大値を単に計算などの解法で簡単にできるようだ。

結果

A: +100 (-1) (180:56)
B: +100 (22:30)
C: +100 (29:13)
E: +100 (-1) (61:21)
F: +100 (-2) (92:17)
G: +100 (-1) (147:20)
H: +100 (160:11)
I: +100 (-1) (288:47)
J: +100 (408:47)
Total: 900 (-6) (408:47)
Rank: 2/84 (正の点数のうち)

まあ良かったかな。ただ幾何の苦手さは良くないよね。それさえ上手くやれば全完行けたかもしれないわけだし。
アルゴリズムが思い浮かんだのはよかった。だがまあ難易度は比較的低めであるので全部わかるのが当たり前なのかもしれないが。
WAも全体から見たら少なめだが、深くはまらなかっただけでWA自体は6つもあるわけで。WAは本当になくしたい。

コード

antaの競技プログラミング練習日記

SRM 404 DIV1 Hard SoftwareCompanies

問題

解答

SRM 403 DIV1 Hard TheLuckySum

問題

解答

SRM 402 DIV1 Hard IncreasingSequence

問題

解答

SRM 401 DIV1 Hard NCool

問題

解答

SRM 400 DIV1 Hard CollectingBonuses

問題

解答

SRM400〜500のDIV1Hardを読み、77問を解いた

Maximum-Cup 2013 本番

Problems

A

B

C

D

E

F

G

H

I

J

結果

コメント

コード