Hatena::Grouptopcoder

zerokugi's contest memo

2015-06-26ICPC2015 国内予選参加記

ICPC2015 国内予選に参加しました

メンバーは @zerokugi @yuscarlet @Gyuuto の3人です

結果は ABCDE の5完で全体5位、大学別順位3位でした

分担は

A @Gyuuto

B @Gyuuto @yuscarlet

C @Gyuuto @yuscarlet

D @zerokugi @yuscarlet

E @zerokugi

以下、各問題について考えたこと/相談したことを書いていきます

コンテスト開始

問題刷って画面の左半分にA問題を表示してGyuuto君に読んでもらいながらテンプレを打つ

A問題 AC (0:08)

とくに問題なく通る

B問題 AC (0:15)

とくに問題なく通る

D問題 WA (0:42)

読んだ感じではとりあえず瞬殺できそうではなかった

愚直にやると、各硬貨の枚数を持ってDPする感じだけど、硬貨系だし多分そこらへんは貪欲で消せるんだろう

持つ小銭の数は常に500円未満になるようにしておくだけでよい?

ってところまで考えた時点でBが通った

Cがまだらしいのでとりあえず書いてみる

持ってる小銭の額を記憶して、支払う額をp[i]~p[i]+499円まで試すDPを書いたがサンプルが通らない

テストケース(250, 250, 1000)で落ちる

所持金500円までじゃないじゃん・・・

500円以上溜まってる時は次の買い物の時に500円に錬成できるから1000円未満で良い?

書き換えるとサンプルが通ったものの投げてみるとWA

C問題 AC (1:05)

考えなおしてたら通っていた

普通の式に書き直してから構文解析ライブラリに投げる感じで解いたらしい

D問題 AC (1:21)

もう一度考察をしなおしてみる

ある店で500円をもらう為には [(p[i]+500) % 1000, (p[i]+500) % 1000 + 500)円の小銭を払わないといけない

区間が500円分なので、小銭の内訳を気にする必要が無い

そうすると、小銭は多ければ多いほど良いので、500円を得られない場合は1000円札のみで支払えばよい

これで遷移がO(1)になったので持っている小銭の量を(100*500)円まで持てるから計算量は n*n*500 で間に合う

すごい不安だったけど投げてみたら通った

E問題 AC (2:01)

EとFの概要を聞く

Fを15分ぐらい考えるも解けそうにないのでEを考える

とりあえず各スレッドごとに任意のuの位置まで薦められるので、uで区切られた区間で分割してそのうち任意の命令列を10スレッドで動かす(重複有り)感じになるなと考える

そうするとアンロックが消えるので、ある二つの命令について、今ロックしているリソース(=命令列の今いる位置以前にあるリソース)の共通要素が空であるような位置のみ取りうるということが分かる

dp[i][j] = dp[ロック中のリソースの集合][次に取りたいリソース] = true or false;

とした時に、

if( (i & k) == 0 && (k & (1<<j) ) dp[i|k][l] |= dp[i][j] & dp[k][l];</ppp>

という感じで、二つの状態から新しい状態を生成できる

最終的に、jがiに含まれているような状態が作れた場合デッドロックを起こすことができる

2^10*10 の状態数に対して 2^10*10 の遷移を行うDPで解ける

(i & k) == 0 の条件があるので 3^10 * 10^2 にできるけど、まあicpcなので

F問題 no submit

全くとっかかりがつかなかった

以下考えたこと

・mが600までなの怪しくない?

・クラスカルベース、プリムベース両方考えたけど思いつかない

・そもそも可能か判定する方法すら分からない

・ある条件を決め打ちして最小全域木を作ることを何通りか試すみたいなことを考えるもダメ

・答えや使う辺のコストの上限を固定してやったりしてもいけそうにない

・片方の最小全域木を作る際に辺を使うか使わないかで分岐しながらスルーした本数でDP・・・連結状態を持てないのでダメ

・一本入れ替えても改善しないような全域木を考える→ごっそり入れ替えたら改善するケースが出てきそうでダメ

降参

G問題 no submit

残り1時間、Fが無理そうでHはヤバいんだろうなぁという感じだったのでGを頑張ることに

とりあえずGyuuto君に幾何ライブラリの写経をお願いしつつ解法を考える

二頂点の組み合わせを全列挙して二等分線で折って頂点数と周長を計算してmaxを取れば良いことは分かる

二等分線で多角形のカットして片方反射してやると二つの凸多角形(A, Bとする)の合成になることも分かる

頂点の数は (n + 2 - 折った後に一致する頂点数 - 多角形に内包される頂点数) になる (←これは嘘であることにあとで気づく)

AとBの共通部分(Cとする)も凸カットで求められて、それも凸多角形になる

Cに現れる辺は、「内部に隠れる」「A、B両方の辺に現れる」のどちらかなので、Aの周長+Bの周長-Cの周長で周長は求められる(多分本当)

ということで凸カットさえあれば通せそうなので書き始める(この時点で残り40分)

書き終わってあらかたバグもなくなったけどサンプルが通らない

確認してみると、折った後の頂点が重なった上で平行に辺が両側に伸びていくケース(サンプル5)で死んでいることが分かる

(丁寧に図まであるし見ておくべきだった…)

その他のケースが大丈夫かどうかは確認できていない

残り5分で書けそうな解決方法も思い浮かばず時間切れ

H問題 no submit

読めていない