スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ACPC 2012 Day2 (Online)

2012/10/20 13:00~18:00
lyoz さんと二人で参加。ちょうどいい難易度の問題がたくさんあって嬉しかった。

Tags : プログラミング UAPC 未解決

結果

8/9 問解いて 2 位だった。

コンテスト中

問題文を印刷しようとして失敗し、スロースタートだった。
A が書くだけらしいので、書いてもらっている間に B を考えた。

B はトーラス上のグリッドで二点間の最短路の個数を求める問題。最短距離を達成する方向が上下左右の四つありうる。四方向のうちいくつが最短距離を達成するかを求めて、( c 個として、) あとはふつうに H+W choose H みたいなのを求めて c 倍すれば答え。

脳内で解けたので C を読む。
原点から線がうにうにいくつも伸びる感じで、最大何マス覆えますか?という問題。わからん。考える。
原点からのマンハッタン距離が K であるマスは 4・K マスくらいしかない。この 4・K マスを全部埋めるようにうまく伸ばしていくのがよくて、4・K 個を超えた分の線はカウントしない、みたいなことをすればよさそうだと気付いた。

ここで A が書けたらしいので投げてもらう。WA。
印刷してデバッグしてもらってる間に C を書いて投げる。WA。ひどい。
とりあえず C は置いておいて B を書くことにした。B もサッと書いて投げる。AC。13:42。ちょっと安心する。

しばらくして A の凡ミスがみつかり、AC。13:51。
C を冷静に考えると実装が間違ってたのでちょこちょこ書き直して AC。14:16。

D は長さ 1500 の素数砂漠をみつける問題。
昔の練習会で解いた Phuket regional 2011 の Twin Apparent Primes!! に似ていたので、方針はすぐに立った。
( 1500 以下の素数の積 ) + 2 からはじまる 1500 個がひとつの解になる。もうちょっと考えると、5000 桁以下ならいいと書いてあったので、もっと甘く、1500! + 2 から 1500 個でいい。
多倍長なので Java で書いてもらう。一回 WA してびっくりしたけど、+2 を忘れてただけだった。AC。14:24。

D を書いてもらってる間に、正解状況からみて取り組みやすそうな H を考えていた。
H は、辺に重みがついた木が与えられたとき、すべての頂点対について、その頂点対を結ぶパスのボトルネック辺の重みの総和を求める問題。
どの辺がボトルネックになるかを全部調べようと考えて、とりあえず重みが小さい辺から順に調べることにした。今、辺 e がボトルネックになる頂点対の個数を知りたい。e より重い辺は使えないので、e より軽い辺のみからなる部分グラフ ( これは森 ) を見てやればよく、答えは ( e の両端の連結成分のサイズの積 ) 通りある。
森を Union-Find で管理して、辺を軽い順に追加していくようにすれば効率よくできる。
同じ重みの辺が複数ある場合に困る気がしたけど、ノートに絵を描いてみると同じアルゴリズムでなんかうまくいっていたのでラッキーだった。
H の位置にしては易しめな気がしていた。 ( 個人的には C の法がむずい。 )

D が通ったあとは H を実装して、さくっと AC。14:38。

僕が H をやっている間に F を考えてもらっていた。グラフとか最短路とかほぼはったりで、二次元平面上に点集合があって、ある長方形に含まれる点の個数を求めるクエリ処理らしい。
昔の練習会で領域木を書いた ( 書いてもらった ) ことがあったので、じゃあそれを貼りましょうということになって、気がついたら通っていた。15:25。

あと、それなりに解かれていたのは E と I の二問。
相談していると I が平方分割でいけそうだねって話になって、クエリ一つあたり O(√n log n) とかになるけど他にできることがなかったから書き始めた。
数列を長さ B のバケット ceil(n/B) 個にわけて、それぞれのバケットが数列自体を表す deque と、deque と同じ中身の multiset を持つようにした。
rotate クエリは deque で持っているので push_front とか pop_back とかでいい感じにできる。
multiset を使えば、値更新と最小値質問も高速にできる。
それなりの時間で書きあがって、投げてみたけど TLE。まぁはい。
手元で大きいテストケースを作って食わせてみたらやっぱり遅い。クエリにかかる時間が O(√n) じゃなくて今回みたいにバイアスがかかっているときは B=O(√n) ととるのは若干不利で、B を大きめにとる方がよい。それに multiset の log は重いし。( そういえば K2PC Hard E のオンライン解法をそれで強引に通したなぁとか思い出していた。) B の値を色々変えて時間を計ってみると、B が 8000 から 10000 くらいのときに一番速くなることがわかった。全然平方分割じゃなかった。
投げてみると 3.75 sec で AC。16:17。

残る E を二人で考えていたけど、僕は全然閃かなくて、lyoz さんが何か言って、それだ!ってなってた。( よく覚えてない )
グリッドに 1×2 のタイルを敷き詰める方法は何通りありますか?っていう蟻本にも載ってるアレと同じ感じの DP になる。
int dp[今見ている行番号][状態] = パズルの答えの総数。
状態は、「上の行から何本線が降りてるかと、今見ているマスの左から何本線が出ているか」で決まって、出ている戦の本数は問題文の制約から 2 本以下なので、
int dp[10][3^11]
くらいで収まってメモリに載る。
map でメモ化したら遅すぎたので 3 進数で整数にエンコードして配列でメモ化したら爆速だった。
実装はスムーズにできて AC。16:59。

G は最小費用流かなぁと思ったけど、サイコロが同じマスにいられないという制約がうまく扱えなくて無理ゲーになっていた。ソウルジェムゲームにちょっと似てるなぁとも思った。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。