Entries

スポンサーサイト (この記事を編集する[管理者用])

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

SRM438 DIV1 (この記事を編集する[管理者用])

2009年04月20日01時から.
[ overview ] [ summary of Japan (otinn.com) ]

EASY - UnluckyIntervals (300pt)
自然数が50個以下与えられる.
区間[A, B]のうちで与えられた自然数を含まないものの全体をSとする.
ただしAとBは正整数でA < Bを満たす.

正整数全体を,S内に自分を含む区間の数の小さいもの順にソートしたとき,最初の100項以下を求める問題.
区間の数が等しい場合は,自然数の値の小さいものが先に来る.

最初の100項になりうる候補は与えられた自然数の周辺100個ぐらいだけなので,それらに対して区間の数を計算してソートする.
計算量的に最適ではないけど,これで十分.
とりあえず,計算量的に大丈夫なら全部調べておけ,というのは名言だと思った.

MEDIUM - EndlessStringMachine (500pt)
programとして50文字以下の文字列が与えられる.最初の1文字は$.
初期文字列をinputとし,s回(10億以下)だけ次の操作を行う.
 programに現れる$をすべてinputに置き換えた文字列をinputとする
最終的なinputの先頭から10億文字目以下の場所から100文字以下求める問題.

100文字分求めなくちゃいけなくても1文字ずつ求める.高々100回なので.
$が1個しかなければ,単純な計算で求まる.
$が2個以上あれば,sが高々30回ちょっとでinputの文字数が10億を超えるのでsが大きいと50ぐらいにしても良い.
後は,該当する文字がs-1回目のinputの何文字目かを調べて再帰的に計算する.

HARD - FeudaliasWar (1000pt)
ミサイルを撃って,敵の基地を全部壊すまでにかかる必要最小時間を求める問題.
ミサイル格納庫からミサイルを撃つことができる.
まずミサイルが飛び立つまで一定時間がかかり,そのあと,目的基地までの距離 / ミサイルのスピードの時間がかかる.
同じミサイル格納庫から2発目以降ミサイルを撃つ場合,ミサイルが飛び立ってから一定時間の準備時間が必要.
敵の基地,ミサイル格納庫はそれぞれ50個以下.

2分探索 + 2部マッチング.
2部グラフの片方は敵の基地(ノード数50以下),もう片方はミサイル格納庫×何発目のミサイルか.
敵の基地の数以上ミサイルを撃つことはないので,後者のノード数は50×50で2500以下.

SRM438 DIV1 (参戦記録) (この記事を編集する[管理者用])

2009年04月20日01時から.
本来は19日01時からだったはずなんだけど,久しぶりのトラブル発生で1日延びた.

Assignment
 なんか平和そうな部屋だなー,久しぶりだ.
 昨日のAssignmentバグの恐ろしく凶悪な部屋も楽しそうだったけど.

 ちなみに,久しぶりにプログラミングコンテスト中にかけているBGMを変更してみた.
 新しい気分で頑張るぞー.でも少しそわそわ.

EASY (300pt)
 なんか面倒そうな問題だ.
 とりあえず,与えられた数列の要素に関しては,区間の数は0.
 後は,与えられた数列の隣接2要素の間の数字のみを考えると,端にあるほど区間の数は少ない.
 じゃあ,与えられた数列をとりあえず一番に優先度付きキューに突っ込んで,出てきた順に答えに加えていく.
 で,処理した数字の前後プラスマイナス1の数字をキューに突っ込む.
 できた.
 サンプル通らない.1を加えないといけない場合がある…,そりゃそうか.
 アドホックに,前後の数字を加えるときに1もキューに加えよう.(これが失敗のもと)
 できた.サンプル通った.サブミット.

 でも,なんか区間の数出力してみるとサンプルの解説より1多かったような…?
 区間[A,B]は厳密にAよりBの方が大きくないといけなかったのかー.
 まぁ,そんなの影響ないでしょ.

 …!!!?
 影響あるよ!
 例えば,入力がN-1, N+1だったとき,Nも区間の数が0だから,N+1より優先的に答えに入れてあげなきゃ!
 アドホックに入力配列がin[i]+2==in[i+1]だったら,in[i]+1も最初にキューに突っ込む.
 これで大丈夫でしょ,リサブミット.
 結構時間かけてしまったのであせって500へ.

MEDIUM (500pt)
 なんだか,面倒そうな問題だ.
 うーん…,$の数が0個と1個と2個以上で場合分けするのか…?
 とりあえず0個をサクッと書く.
 1個のときもサクッと書く…と思ったら結構面倒じゃないか?
 あれ?programの最初は絶対$なのか,それだと簡単じゃないか,1個の場合かけた.
 2個以上は…どうするんだ?
 最初は$なんだから,programの実行回数sって実際すごい小さい範囲で確定してしまうよね.
 がんばって再帰的に呼び出せば良いだけじゃないか?
 …
 バグ入れた.
 …
 バグわからない.
 …
 いらない等号が1か所入ってた….
 できた.サブミット.
 残り25分.

HARD (1000pt)
 引数多いよ.面倒そうだよ.(問題読む前の感想)
 問題読んだ.
 グラフっぽい…?二分探索?フロー?
 でも,ミサイルをどこに向かって打つかで,次に打てる時間が変わるし,どうやるんだ?(問題解釈間違え)
 いや,飛んで行ったら,即座に準備できるんだから向かう先は関係ないじゃん.
 だったら2分探索 + 最大流でいけるような気がする.
 でも,グラフのサイズが左側の節点が最大2500,右側50だぞ…,そんなので2分探索して間に合う気がしないぞ?
 残り時間10分.
 まぁ,いいや,書いちゃえ.
 書けた.残り4分.サンプル合わない.
 離陸時間だけ単位が違う!60で割らなきゃ.
 サンプルあった.通る気がしないけどサブミットしてやれ.誰かに50点プレゼント.

Intermission
 EASYの撃墜用ケースでも作ろう.
 {9, 7, 5, 2, 19, 21, 1000000}, 100
 む…,自分のプログラム最初に1を吐かない…,これは落ちるorz

Challenge
 やっぱり300で配列の要素を優先的に入れてるのがたくさんあったみたい.
 2人は撃墜できたけど,3人目のコード読んでるうちに,6~7人ぐらい誰かに撃墜されてて,気づけば獲物が残っていなかった.
 まぁ,100点稼げば満足するか.

System Test
 予想通り300と1000落ちた.
 でも,1000はTLEじゃない?
 2分探索の範囲の上限値を返してる…,上限は高めに設定したつもりなんだけど….
 なんか,バグ入れたのかな…,よくわからない.

 これだけ駄目駄目な成績でもRateは微増.

(2009/04/20 03:27追記) わかった.HARDはメモリ確保してる量がおかしいんだ….

LiveArchive 3814 - Self-divisible Numbers (この記事を編集する[管理者用])

Oceania - South Pacific - 2007/2008
[ Link ]

何度テストしてもAcceptもらえなかったので,ジャッジデータが間違っているに違いないとかBBSに書き込んだらRejudgeされた.
Thanks Carlos.

[ 問題概要 ]
self-divisible numberというのは,全てのkに対して頭からk文字取ってできる数字は頭からk文字目の数字で割り切れるもの.
たとえば213.
 2 mod 2 = 0
 21 mod 1 = 0
 213 mod 3 = 0
だから.
400桁以下の数字が2つ与えられた時,その間にあるself-divisible numberの数を求める問題.
ただし,答えは1000000以下になることが保証されている.

[ 解法 ]
答えは1000000以下なので,全探索しても終わらないわけではないがテストケースの数もそこそこ多いらしくTLE.
0以上n以下に含まれるself-divisible numberの数を求める関数f作って
 f(b) - f(a-1)
とかを答える方針.
それをカウントする方法はDPで,状態としては
 現在何桁目を処理しているか(後何桁残っているか),その桁より上位の桁からなる数字%2520
で,それを満たすself-divisible numberの数を記憶しておいて,それを使う.
ちなみに,2520 = lcm(1,2,...,10).
一時的に場合の数はオーバーフローするけど,答えは1000000以下なので,最後に引き算したら正しい答えが出てくるはず.

今更だけども (この記事を編集する[管理者用])

Studio e.goどうなるんだろう.
というか,キャッスルファンタジアの新作はー?

World Finals Warmup II (この記事を編集する[管理者用])

World Finals 2009 Warmup 2.
2009年04月05日17時から5時間または24時間,9問.
[ Link ]

寝坊して途中参戦だけど,僕なんかが正味5時間以内に全部解けるとかFinals Warmupらしくない問題セット.
Accept数が少ない問題は探索系なのだけど,ICPC日本Regionalに慣れてる人なら楽に解けるはず…,っていうか全然難しくないのだけど.
実際にこれ書いているのは午前3時ごろ.

A. Convex Orthogonal Polygon
全ての辺がx軸かy軸に平行で「窪んでない」多角形を考える.
それを1回拡張すると,図3のようになる.
拡張前の面積,n回拡張後の面積,もともとのバウンディングボックスの面積が与えられた時,
nとしてありうる値をすべて求める問題.

バウンディングボックスの面積から,縦横それぞれの長さの考えうる値を全部考える.
k回目の拡張は
 (縦の長さ+横の長さ)*2 + 4*k
だけ面積が増えるので二次方程式を解けばnが求まる.
縦横それぞれの長さから,拡張前の面積が不正な場合は処理しないように.

B. Spanning Subtrees
nが偶数.
ノード数nの完全グラフにおいて,k個の全域木がお互いに枝を共有していない.
そのようなkの最大値を求める問題.

k_max = n/2.

C. Optimal Segments
32個以下の数列を16個以下の部分に区切る.
各部分には0が書かれた場所を1か所は含まなければ行けない.
区切り方のうち,各部分の和を求めて,その最大値 - 最小値を最小化する問題.
最大値 - 最小値が一定以上ならoverflowと出力する.

探索,DFS.
自明な枝刈りしかしなくても,0.03sで通った.タイムリミットは5s.

D. Triangle and Polynomial
図のような関係でdとxが与えられる.
n次式でxを根に持つような多項式を求める問題.
nは4以上10以下.多項式の係数は絶対値が10^9以下の整数で,定数項は0であってはいけない.

解法はよくわからない.というか問題がよくわかってない.
しかし,サンプルinput/outputが全て.
n=4のときは,サンプルをスケール変換すれば答えは全て求まるし,nがもっと大きいときはn=4の結果に(x+1)とか適当な多項式をかけておけば良い.
これは新しいタイプの問題だった.

E. Masud Rana
ノード数nは30以下.完全グラフ.
道はいくつか使えない状態.一度通った道は使えるようになる.
最初ノード0にいて,後はランダムウォークする場合,全部のノードが連結になるような平均ステップ数を求める問題.

確率 + DP.
連結なノード数と,今いるノードはどの連結成分にいるか,というのが状態なので,状態数は高々30の分割数 * 30程度.

F. Avoiding Overlaps
200×200程度のグリッドで10000個以下の長方形を塗る.
ただし,以前塗った長方形とオーバーラップする場合は全く塗らない.
最終的に塗った面積を求める問題.

一応2D Fenwick Treeを使って,オーバーラップするかどうかの判定はO( (log 200)^2 ) ぐらいでできるようにしてみた.

G. SMS for Blinds
文字列とそれを打つコストの合計が与えられるので,それを満たすように
19種類の文字に対して,それぞれ打つコストを1から19まで1つずつ割り当て方を求める問題.

任意のテストケースに対して,完璧に求めるアルゴリズムを考えるのは難しいので,テストケースはランダムに作られていること,と注意書きがある.
また,テストケースは1200程度だけど,そのうち間違えた数が10個以下ならばAccept扱いになる.

探索,DFS.
一応最初にソートしておいて,簡単な枝刈りぐらいはしてみた.
別に全てのテストケースに対して完璧に探索しても0.07sで通った.タイムリミット3s.

H. Its all about the Bandwidth
Warmup I の問題Hの逆問題.
無向グラフにおいて,各節点対に対するmax-flowの値が与えられる.
考えうる最小枝数の無向グラフを求める問題.存在しないならそれを指摘する.

まず,存在するかどうかは,Gomory-Hu's Treeを考えてみると,
ワーシャルフロイドっぽく O(n^3) で判定可能.
後は,Gomory-Hu's Treeを実際に構成する.
具体的には,フローの大きい順に,まだ連結でなければ枝をつなげるだけ.

I. General Sultan
0,1からなる20文字以下の文字列が100個以下与えられる.
0,1からなる文字列で,与えられた文字列に分解する仕方が2通り以上存在するものが存在するかどうかを判定する問題.

BFSまたはDFS.
よくある問題だと思う.説明するのは面倒.そこまで簡単でもない.

UVa 11593 - Fractions (この記事を編集する[管理者用])

World Finals 2009 Warmup I,問題G.
[ Link ]

[ 問題概要 ]
有効数字7桁以下の小数が入力.小数は0と1の間の数字.
四捨五入すればその小数となるような分数 a/b の数を求める問題.
aとbは1000000000以下.

[ 解法 ]
aとbの範囲を平面上に図示すると,頂点が格子点上の三角形となる.
後は,その三角形の各辺上の格子点の数をGCDなどを用いて求めて,三角形の面積から,該当するa,bの組の数をピックの定理を用いて計算する.

UVa 11594 - All Pairs Maximum Flow (この記事を編集する[管理者用])

World Finals 2009 Warmup I,問題H.
[ Link ]

[ 問題概要 ]
ノード数200以下の無向グラフが入力.
各枝に最大流量が与えられている.
すべての節点対に対してその2点間のmax-flowを求める問題.

[ 解法 ]
n^2回のmax-flowはもちろんTLE.
Gomory-Hu's Treeというものを考えることでn-1回のmax-flowで求めることができる.
詳しくはTopCoderのForumを参照.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。