Entries

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

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

The University of Aizu Programming Contest 2009 Spring (この記事を編集する[管理者用])

2009年03月29日13時から5時間,10問.
[ Link (Result) ] [ ALGORITHM NOTE ] [ aizuzia ]

ジャッジの皆様,お疲れ様でした.
日本ICPCみたいな探索とか構文解析とか含めながら,結構いろんなタイプの問題があって楽しかったです.
(日本ICPC大好きな幾何はなかったけど)

日本語の問題文があるので,わざわざ問題概要を書く必要があるのかが酷く謎.

A. Vampirish Night (日本語)
K種類の食べ物の在庫量が与えられる.
N人の人が食べるK種類の食べ物の量が与えられる.
全員食事できるかどうかを判定する問題.
NもKも100以下.

実際にN人の食べる量を在庫から引いて,最終的に在庫が全部非負であればYes.
何かが負になればNo.

B. Cleaning Robot (日本語)
3×3のマップにおいて,侵入できない場所,最初の場所,最後の場所が与えられる.
1回の移動では等確率で4方向を選んで移動する.
移動できないならば,現在の場所にとどまる.
最初の場所からtターン後に最後の場所にいる確率を求める問題.
tは15以下.

DP.
時間sにおいて,各場所にいる確率から時間s+1に各場所にいる確率を求めるというのを繰り返してお終い.

C. Emacs-like Editor (日本語)
最初のテキストと処理コマンド列が与えられるので,最終的なテキストを出力する問題.
コマンドはemacsぽいのがいくつか用意されている.

実装問題.やるだけ.

D. Indian Puzzle (日本語)
10個以下の穴が空いた盤面が与えられる.
穴の数に対応した入れる数字,演算子のリストが与えられるので,ちゃんと当てはまるものパターンが存在するかどうかを判定する問題.
3マス以上連なった場所は,等式を満たしていなければいけない.

探索 + 構文解析.
まず,全部埋まっている式が全部正しいかどうかチェックする.
後は,1つずつ当てはめていって,あてはめてできた数式が正しくないなら違うのを試す,的なバックトラック.
で解けるんだと思う,解いてないのでわからない.

E. Amazing Graze (日本語)
2種類の点がそれぞれ10万個以下ある.
それぞれの点の距離は2r以上離れていることが保証されている.
2種類の点のペアで点の距離が4r以下の数を求める問題.
座標の数値は0以上10000未満,rは1以上10以下.

本当に適当にやったら通ってしまったので,よくわからない.
参加記録で書いていた10万^2の計算量が必要になるケースは座標の取りうる値が小さいので作れないことに気づいたんだけど,
10000^2とかそのぐらいは普通に必要になる….

F. Cleaning Robot 2.0 (日本語)
N*Nのマップで,各マスが白か黒に塗られている.
前左右のうち,自分の場所と同じ色の場所が1個だけならばそっちに進むというロボットを何体でも置くことが気出る.
最終的にどの場所もロボットが訪れなくなるということがないような配置が存在する色の塗り方のうち,辞書順でK番目のものを求める問題.

G. Building Water Ways (日本語)
水源から各都市へと水を引きたい.
直感的に言うと,各水源からは線を1本しか伸ばすことができない.
2つの線が接してはいけない.
線の距離の最小値を求める問題.解が存在することは保証されている.

どうやら想定解法はiterative deepening + 頑張って枝刈り.
枝刈りとしては,ICPC 2006 YokohamaのManhattan Wiringと同じような感じでやれば良いのだろうか?
なんだけど,自明な枝刈りのみ + DFSで通ってしまった.

Manhattan Wiring : [ PKU ] [ Live Archive ] [ SPOJ ] Aizuは1270.
ちなみに,TimeLimitの厳しさは
 厳しい = SPOJ > LiveArchive > PKU > Aizu = 緩い
かな.

G. Hedro's Hexahedron (日本語)
奥幅は2,前後はn*nのサイズの直方体がある.それに高さ1の水を入れて,1周回す.
直方体は1*1のタイルで構成されている.
水に少しでも濡れるタイルの数を求める問題.
nは10^12以下.

非自明なのは前後の面のタイルで濡れる数.
濡れるタイルをL字型の図形で分解して,それぞれの数をちゃんと計算して足していけば良い.

I. A Piece of Cake (日本語)
n個の数字に対して,すべてのペア(n-1)n/2個の和が与えられるので,もともとのn個の数字の和を求める問題.

それぞれの数字に対してn-1個相方がいるので,入力の和/(n-1)を出力するだけ.

J. ICPC: Ideal Coin Payment and Change (日本語)
日本の硬貨6種類のそれぞれの所持枚数が与えられる.それぞれ1000以下.
P円の買い物をするとき,自分の支払う硬貨の枚数+受け取る硬貨の枚数の最小値を求める問題.

まず,自分の持っている最大価値の硬貨を1枚使っても払いきれないなら,1枚使ってみる.
というのをとりあえず繰り返す,できっと大丈夫.
後はDPで適当に求める.
ちなみに,硬貨の総枚数をKとしたとき(種類数は定数),DPでP円以下それぞれのお金を支払うのに必要な最小枚数の硬貨の数は O(P log K) で計算可能,頑張れば O(P) で計算可能.

2009 TCO Algorithm Round 4 (この記事を編集する[管理者用])

2009年03月29日01時から.
120人 → 45人.
[ match overviws ] [ otinn.com summary (Japan) ]

EASY - CubeOfDice (250pt)
6面ダイスの各面に書かれた数字が与えられる.
それをサイズNの立方体状に積み重ねる.
その時,外から見える数字の和の最小値を求める問題.

3面見えるダイスの数がいくつか,2面見えるダイスの数がいくつか,1面見えるダイスの数がいくつかを(紙上)計算する.
後は,裏表の関係の面を同時に使うことができないという条件でそれぞれの最小値を求めて足すだけ.
N=1のときはコーナーケースで,小さい方から5つ足して終わり.

MEDIUM - ChuckContest (500pt)
ICPC方式のコンテストにおいて,時間をN個に分割する.
それぞれの時間区間が終わったのちでの,自分の成績の下限,上限が与えられるので,
それを満たすような最終的に一番良い成績を答える問題.
問題は自由にサブミットできるし,すべて既に答えを知っている.

DP.
ある時間区間が終了したときに,ペナルティの合計 mod 20の値が k となるような取りうる成績を列挙すると,ある範囲内の成績がすべて含まれることが証明できる.
なので,それを状態として持ちながらDPすれば良い.

HARD - ShadowArea (1000pt)
光源と障害物が与えられた時,光が当たらないエリアの面積を求める問題.

幾何.
実はライブラリが揃っている人ならば,そんなに難しくない問題だったのかもしれない.
光のあたるエリアを求めれば良い.
障害物のコーナーにあたる角度をすべて列挙して,ソートして,その間での光のあたるエリア(三角形)の面積を求めて全部足せば良い.

UVa 11591 - Bulb Inside a Grid (この記事を編集する[管理者用])

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

[ 問題概要 ]
サイズ10億以下の正方形の行列がある.
初期状態では,対角より右上が0,それ以外が1となっている.
50個以下の操作が与えられて,それぞれ長方形の範囲(端を跨ぐかもしれない)の0,1を反転させる.
最終状態での1の個数を求める問題.

[ 解法 ]
縮小座標を作って塗りつぶす.
縮小した後での1マスに対して,最初に含まれていた1の個数を計算するのが場合分けが必要で少し面倒.

UVa 11590 - Prefix Lookup (この記事を編集する[管理者用])

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

[ 問題概要 ]
プレフィックスの集合が与えられる.
長さM(64以下)の0,1からなる2^M通りの文字列が,それぞれマッチするプレフィックスと対応づけられる.
複数のプレフィックスとマッチするなら最も長いものと対応づけられる.
それぞれのプレフィックスに対応づけられる文字列の数を求める問題.
プレフィックスは20000個以下ぐらい.

[ 解法 ]
Ad-hoc.
 2^残りの長さ - 自分を含んでいて,自分より長いものとマッチする数
が自分とマッチする文字列の数.
後は,O(プレフィックスの種類^2)とかにならないように頑張って実装するだけ.
僕は,(漠然としすぎな説明だけど)プレフィックスをソートしておいて,2分探索とかを使いながらやってみた.

UVa 11588 - Image Coding (この記事を編集する[管理者用])

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

[ 問題概要 ]
20×20以下のグリッドにAからZまでの文字が書かれている.
一番多い数の文字(複数の種類があるかもしれない)に対して1文字ごとのコスト,
それ以外の文字に対して1文字ごとのコストが与えられるのでコストの合計値を求める問題.

[ 解法 ]
やるだけ.
World Finals 2009 Warmup Iで唯一簡単な問題.

UVa 11587 - Brick Game (この記事を編集する[管理者用])

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

[ 問題概要 ]
石取りゲーム.
初期の石の数が1~100以下のとき,先手必勝か後手必勝かが与えられる.
1回に取ることができる個数は {1, 2, ... , 20} のサブセットだとして,1回に取ることができる石の個数の集合を求める問題.
解は存在することが保証されている.
解が複数存在するなら,集合の要素数が小さいもの,その次に辞書順最小のものを出力する.

[ 解法 ]
2^20通りの可能性を全部確かめても多少の枝刈りを入れれば通った.(制限時間2秒,実行時間0.3秒程度)
よくよく考えれば,DPするときのことを考えて,LからLに移れてはいけない,WからLには移れなければいけない,というので,
Lに移れるWを覚えつつバックトラックで求めると速いのかもしれない.

2009 TCO Algorithm Round 4 (参戦記録) (この記事を編集する[管理者用])

2009年03月29日01時から.

Assignment
 部屋にtarget(rate 3000以上,赤の中に白丸)の人が5人もいるよー.
 Petr先生もいるよー.
 そして観戦者もたくさんいるよー.

EASY
 ダイスの隣り合う面は同じ数字じゃないと駄目とか,なにか制約ないのかと疑って無駄に問題文を読み直す.
 ない.計算するだけっぽい.
 {1,2,3} 面外に触れるダイスの数は….
 後は,小さい方から外に触れさせれば良い.
 サブミット.

MEDIUM
 問題文長い.頑張って読む.
 DPくさい.
 問題数×時間=60*100000ぐらいの状態数でDPすれば良いのか?
 メモリは足りる.
 でも計算時間が恐ろしいことになるじゃないか….

EASY
 急に思い出す.
 小さい方から順番に外に触れさせることなんてできないよ!
 真後ろの面と同時には使えないという制約をつけて真面目に計算.
 resubmit.110点….

HARD
 とりあえずなんとなく開いてみる.幾何だ.
 幾何は変なコーナーケースとかで落ちてなかなか通らないイメージ → MEDIUMのDPっぽい方がマシでは….

MEDIUM
 ….
 ぴかーん,閃いた.
 好きなようにペナルティは食らうことができるから,状態を問題数×20で,それぞれ最小達成ペナルティを記録しておけば良いんじゃないか.
 一気に計算量減った.余裕だ.
 実装…,バグ入れたりして手間取る.
 できた,サブミット.

 ….
 よーく考えてみる.
 好きなようにペナルティ食らえるといっても,そのためには問題をサブミットしなければならない….
 サブミットしたコードじゃ駄目だ.

 ….
 じゃあ,最小達成ペナルティじゃなくて,達成できるペナルティの範囲を覚えておけばどうか.
 良さそうだ.かきかき.
 バグいれて手間取る.
 できた,サブミット.150点….

 残り6分ぐらい.
 最小しか記憶してない人用に,チャレンジケースでも作ろう.
 自分が撃墜された.残り5分.修正できるか?
 printf書いて,アリーナで実行して結果を見てデバッグ….
 残り1分でサンプルと自分のチャレンジケースは通るようになった.とりあえずサブミット.

Intermission
 上位45人通過で45位ぐらいだった気がする.
 今回もチャレンジは多い気がする.
 500は最後ぐだぐだで通るわけがない.250は110点しかない.
 チャレンジで稼ぐしかない.

Challenge
 250も500もそれなりに複雑でソースコードが読みにくい.
 …,500で範囲を記憶してないよね,でチャレンジして2失敗.
 ( 後で失敗した理由がコピペミスだったことが判明… )
 …,なんかやけになって250にチャレンジ失敗.
 合計-75点.おわた.

System Test
 250も500も通った….あのぐだぐだでよく通った….
 結局500は10人しか通してない,1000は提出した人はだいたい通ってたと思う.
 結果的にはチャレンジしてなければ楽に通過できてた.2回までチャレンジミスって-50点でも通過できてた.頭悪い.

The University of Aizu Programming Contest 2009 Spring (参戦記録) (この記事を編集する[管理者用])

2009年03月29日13時から5時間,10問.

最近はいつも,全部問題眺めてから解き始めることが多いんだけど,ICPC形式だし,久しぶりに読んだ問題からアタックしていくことにする.
風船(statistics)見ながら頑張ろう.
そして,いつも通り最初は逆順に問題を読んでいくかもしれない.

Problem J: ICPC: Ideal Coin Payment and Change
 支払う金額は,高々666000ぐらいか?
 DPするだけじゃないか.上限がどこまでとれば良いかわからないので,ちょっと多めに取る.
 TLE.タイムリミット1秒のところを4秒ぐらいかかってる.
 上限高くしすぎたね.
 TLE.タイムリミット1秒のところ,1.1秒ぐらい….もどかしすぎる.
 …,コインの種類固定.しかもAd-hocに使える日本のコインだよね….
 支払う金額がとても多い間は,持ってるコインの中で一番高価なのを使って,その後DPしよう.
 通った.なんか凄く駄目な通し方だけど.

 やっぱり問題全部みて,落ち着いてからやらないと駄目な人間かもしれない.

Problem I: A Piece of Cake
 む,問題文,日本語もあるじゃないか.
 やったー,読みやすい.
 全部足して割るだけ…,Accept.

 この辺から,statistics見て簡単な問題からやろう.
 普通にA問題 → B問題の流れかな….

Problem A: Vampirish Night
 やるだけだ.Accept.

Problem B: Cleaning Robot
 DPまわすだけだ.Accept.

Problem C: Emacs-like Editor
 シミュレーション.それほど面倒ではないような気がするけど少し面倒.
 次の問題読む.

Problem D: Indian Puzzle
 探索 + 構文解析….
 これは書きたくない,パス.

Problem E: Amazing Graze
 これは…,平面走査…か…,これ系無理.
 いや,Rは10以下だから,弾のハッシュ計算しておいて,
 すべての戦闘機に対して,半径2R以上4R以下の点にいる弾の数を足していく.
 2R以上4R以下に該当する座標はそんなに多くないのでは?
  → まぁ,TLEだった.手元で最大ケースで13秒とかかかる.
 該当する座標は5000個近くあるぞ…,そりゃTLEだわな.
 後回し.

Problem C: Emacs-like Editor
 まぁ,実装問題書くか.本当に問題文に書かれている通りに実装するだけだ.さくさくさくさく.
 …WA.通らない.
 kの「下に行があれば」ってのはどこまでかかっているんだ?
 「カーソルの位置にバッファの内容を挿入する。」カーソルの位置って何だ?カーソルは文字を指しているのだけど….
 kについてはclar来た.
 普通に行数増えたときに行数++を書き忘れているだけだったorz Accept.

Problem E: Amazing Graze
 あっさり通している人がいるので嘘平面走査でも書いてみる.
 x座標でソートして….
 最悪計算量O(10万^2)だし,すぐそんなテストケース作れるけどサブミット.Accept.……….

 残りの問題全部読む.
 F…,まったく解法想像できない.しかもkが2^63だと….DP系?
 G…,探索臭しかしない.
 H…,制約が10^12とか意味深なので数学をごちゃごちゃすればO(√n)になるんだろうか.

Problem H: Hedro's Hexahedron
 しばらく考えて,L字の形を足していけば良いよね,後で何倍かしたり,いくらか足したりもするけど.
 L字の長さをどうやって求めるのか….
 なんとなく,こんな感じじゃないかな,ってので送ってみるもWA.
 ちゃんと計算してみた.微分とかもした.結果Accept.

Problem G: Building Water Ways
 マップのサイズも8*8以下ととても小さいので,とりあえず適当にDFSするだけのプログラムを書いてみるか.
 あっさりAccept.枝刈りもほとんどしてないのに.こんなんで良いのか….

 だいたい3時間経過.残り2時間.8問解いてる状態.

Problem F: Cleaning Robot 2.0
 Dは頑張って書くだけっぽい気もするんだけど,書きたくないのでこっちを考えてみよう.
 ….
 うーん,実は2^63とかブラフで決められたパターンしかありえないのでは?
 nが奇数なら存在しない.
 nが偶数でも8パターンぐらいしかない.
  → そんなわけなくてWA.
 あ,こういうパターンもあるとか追加して送ってWAを繰り返す.
 サイズが2の倍数の小さな正方形に区切って,鏡像反転して繋げたりしても作れるぞ!
 やっぱり,作れる数は組み合わせ的に爆発するのでは…?
 残り時間10分,無理,白旗.

G線上の魔王 (この記事を編集する[管理者用])

ネタバレを含むかもしれないので続く.

続きを読む

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

cafelierさんにならって,コンテスト中に考えてたことを書き連ねてみるテスト.

EASY
 問題名がTheSwap…嫌な予感がする.
 とりあえず何も考えずに例外処理として,0じゃない数字が1個しかなければ即座に-1を返す…というコードを書く.
 一番大きい数字を一番上の桁に持ってくるという作業を繰り返すだけか?
 とりあえず書く.
 swap回数が余ったら,一番影響が少ないのをswapする.
 → 同じ数字の桁があればそれらを,そうでなければ下2桁をswapすれば良いよね.
 サンプルが通らない.
 同じ数字が2つ以上あれば,もっとも下位の数字とswapするべきだよね,たぶん.
 サンプル通った.サブミットした.

MEDIUM
 問題名がTheInteger.しかも整数が一番美しいとかEASYにも書いてあった気がするぞ.
 writerはVasyl(alphacom)だ,間違いない!
 (前回も3問とも4と7はラッキーな数字だとかいってたはず.)
 この人の問題苦手なんだよなー,簡単なはずなんだけどいつも解けない.

 問題を読んだ.
 nと同じ桁の数字が存在するならそれを求めて,そうじゃなければ適当に配置しておしまい,という方針はすぐ思いつく.
 どうだろう18桁ぐらいならAd-hocに枝刈りを入れつつ全探索で良いんじゃないかな…?
 上の桁から決定していくとして,枝刈りは…
  1) nの影響がない状況下では,今まで使った数字の中で一番小さいの,今までつかってなかった数字のなかで一番小さいのの2択.
  2) nの影響があれば,一番小さいのと含めて3択.
  3) 使った数字の種類と,まだ残っている桁数で枝を刈る
 1) 2) があるから,計算量的には2^18程度…全然大丈夫だ.
 書いた.サンプル通った.
 nと同じ桁で見つからない場合のテストをしてたら1個ミスってるのを発見.修正.あぶないあぶない.
 サブミット.

HARD
 方針が何も思いつかない.
 後40分もある.
 でも頭の中真っ白.

MEDIUM
 ふと枝刈りをちゃんと書いてなかった気がした.
 1) 2)の枝刈りするために必要な変数の計算とかしてるのに,枝刈りしてない!
 最悪テストケースは何だ?よくわからない.
 いくつか試して0.01秒以内には終わるから大丈夫か?放置!

HARD
 方針がまったく思いつかない.
 メモ付全探索?メモリ足りるわけない.TLEもする.
 summary見ると提出数が少ない.
 EASYもMEDIUMも通るかどうか怪しいし,HARD捨てて見直しすることにする.

EASY
 本当にswapする候補が複数あるとき,下位の桁とswapすれば良いのか?
 反例を考えてみよう….
 あった! n=6577, k=2.
 6577 → 7576 → 7756,駄目じゃん.
 後10分.EASYなんだから適切に解けば10分あれば解けるはずだ!

 でも焦ってる.どんな方針でも通れば良い.
 全てのpermutationを列挙してそれらがk回のswapで移れるかどうか考えてみよう.
 最小swap回数は…,巡回置換の積に書き直して,それぞれの要素-1を足していけば求まるのかな?
 でも同じ要素があることもあるし,ややこしくないか….
 そこまでやるならBFSして全部計算しちゃえばよろしい.
 ノードの数の最大値はいくらだ…,6!=720.そんなに少なかったのか!
 BFS書いた.サンプル通った.サブミット.最小点である75点….
 テストをしてみる. n=901,k=1.返ってきた答えは109.残り2分.
 1箇所,一番上の桁が0だったら…というのが一番下の桁が0だったらになってた.
 ギリギリで直してもう1回サブミット.

Intermission
 絶対みんな250点解けてないはずだ.今回はチャレンジ大会になるはずだ.
 500もたくさんチャレンジポイントあるしなぁ.
 250のResubmitは痛いので,誰よりも早くチャレンジして点数を稼ぐ.
 とりあえず,250でk回ループ回しているやつには問答無用でチャレンジすれば良いよね!
 チャレンジケース用意OK.

Challenge
 250ですぐさまチャレンジ.失敗.
 k回シミュレーションして全列挙してやがる….賢すぎる.てか皆そんな方針だ….
 でも,やっぱりGreedyの人いたー,突撃.成功.
 後はがむしゃらにチャレンジして合計3成功4失敗で+50点.500点問題のコードをじっくり読む時間はなかった.
 DIV1なんだし,あんまり馬鹿やる人はいないよね…,無差別に突撃するのはあんまり良くないな….

System Test
 EASY落ちた…なんで?
 10000とかだと0と0をswapすれば良いので-1ではないのだ!やられた.
 MEDIUM通った.良かったー.
 Rateは少し落ちた.まぁ仕方ない.

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

2009年03月25日00時から.
[ match overviws ] [ otinn.com summary (Japan) ]

EASY - TheSwap (250pt)
nは1000000以下の自然数.
i桁目とj桁目(i != j)をスワップするという操作を厳密にk回行った後,できる数字を最大化する問題.
途中で先頭に0がくるようなのは駄目.
kは10以下.

全通り試してみて,できる数字を全部覚えておけば良い.
それで十分なんだけど,計算量を減らすなら,BFSして,各数字への最短スワップ回数を求めた後,同じ数字の桁がなければ,
 (k-最短スワップ回数) mod 2 == 0
でなければいけないという条件を貸した後,最大のものを調べる.

MEDIUM - TheInteger (500pt)
10進数で現れる数字の種類が厳密にk種類であるような,n以上の最小の自然数を求める問題.

まず,nと同じ桁数でk種類の文字がでてくるものが存在するかどうかを探す.
それは,上の桁からなぞってDPする.今使った文字の種類と,今何桁目か,nより大きな数字を1回でも使ったか,なんてものを状態にもつ.
存在しなければ,10000234なんて感じにGreedyにおけば良い.
DPじゃなくても,どの桁からnと別のものにするかを全パターン試すとか,Greedyっぽい方法でも十分解ける.

HARD - TheSum (1000pt)
1000000000以下の自然数a,b,cが与えられたとき,a,b,cを適当な操作を加えて
 a+b=c
を満たすようにする最小のコストを求める問題.
操作は,1文字を変更する,1文字付け加える,1文字消すの3種類で,それぞれにコストが設定されている.

適当に,下の桁からなぞって,a,b,cがそれぞれ後何桁残っているか,繰り上がりがあるかどうか,などを状態に持ちながらDPすれば良い…はず.

2009 TCO Algorithm Round 3 (この記事を編集する[管理者用])

2009年03月22日01時から.
Linkは後で追加します.
[ match overviws ] [ otinn.com summary (Japan) ]

チャレンジ苦手なせいで,チャレンジで点数稼ぐのは邪道だと信じ込んでたのだけど,
Round2もRound3もチャレンジに助けられている….

EASY - SaveTheTrees (250pt)
木を切る数を最小化する問題.
残す木を全部囲むように,x軸,y軸に平行に長方形で柵を作らなければいけない.
柵は切った木を用いて作る,高い木ほど得られる資源が大きい.
木の数の上限は40.

O(n^5)のループで解く.
フェンスの場所をO(n^4)通り試すのだけど,フェンスの外の木は全部切る.
材料が足りてなければ,高い木から切っていく.

MEDIUM - CampaignTrail (500pt)
地区ごとで順番に選挙して,地区ごとに重みが設定されていて,過半数の地区で勝てば良い.
勝つ確率を最大化する問題.
地区の数は50個以下で,選挙がおこなわれる順番は固定されている.
n地区以下だけ実際に訪れることができて,各地区に対して訪れた場合,訪れなかった場合のその地区での勝率が与えられる.

単純なDP.頑張らないとMLEするのかと思ってたけど,そんなことはなかった….
250点問題より簡単.

HARD - YetAnotherStonesGame (1000pt)
50マス以下のサイクルのマップが与えられる.いくつかのマスにはマークが付いている.
最初にマークの付いていないいくつかの場所に石をおく.
{1,2,3,4,5,6}のサブセットが与えられて,1回の移動では時計回りにそのセットの要素から1個選んでその数だけ移動できる.
移動先はマークがついていないマスじゃないとダメで,移動したらマークをつける.
石が最初自分のいたマスに戻ると,その石はマップから取り除かれる.
すべてのマスにマークを付けて石をない状態にするには,最小でいくつの石を最初におけばよいか,もしくは不可能かを答える問題.

移動最大可能距離が6なので,最初の6マスのうち,マークがついてないマスに対して最初に石を置くかどうか,最大2^6通りに対して,全部マークすることができるかどうか試せば良い.
全部マークできるかどうかを試すのはDPで.
ちなみに,「自分」のいた場所に戻らなければいけない,なんてことはちょっと考えれば必要ないことがわかる.
石Aが石Bの最初の場所に戻って,石Bが石Aの最初のマスに戻れるなら,石は1個でそれら全部まわれるので.
ということで,石を区別する必要はない.

(2009/03/25 12:00 EDIT) Linkと問題名を追加.

(2009/03/25 12:00 追記) HARDは石を区別してDPして,別の場所に戻ってきたやつを考慮して使った石の数をカウントしなければうまくDPできない….

SPOJ 4060 - A game with probability [KPGAME] (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
N個の石があって最後の石を取った人が勝ちという2人で行う石取りゲーム.
各ターンでは,コインを投げて表が出れば1つ石を取る.
先手,後手はそれぞれ,コインを狙った向きを出せる確率が与えられる.
両者とも最適にプレイした場合,先手が勝つ確率はいくらか,という問題.
石の数は1億未満.

[ 解法 ]
残りの石の数がn個で先手のターンという状況下で先手の勝つ確率をA[n],
残りの石の数がn個で後手のターンという状況下で先手の勝つ確率をB[n]とする.
ちょっと考えてみれば
 nが偶数 ⇒ A[n] < B[b]
 nが奇数 ⇒ A[n] > B[b]
であることが示せる.なので,最適戦略は確定.後は
 A[0]=0, B[0]=1
から出発して漸化式をたてて逐次計算していく…と1億回計算が必要になっちゃうので,
漸化式をベクトル形式で書いて遷移行列のべき乗を求めるといういつもの方針で解く.

2009 TCO Algorithm Round 2 (この記事を編集する[管理者用])

2009年03月15日01時から.
[ match overviws ] [ otinn.com summary (Japan) ]

EASYしか通せなかった.問題の難易度がちょっと不思議なバランスなセット.

EASY - PlaneFractal (250pt)
再帰的に定義される図形の,ある部分を求める問題.
やるだけ.

MEDIUM - ExtendableTriangles (600pt)
50×50以下のグリッドが3色に塗り分けられている.
異なる色の3点を選んで三角形(面積0も可能)を作るのだけど,2点を止めたまま残りの点を動かして面積が大きくできる三角形をextendableと呼ぶ.
extendableな三角形の数を求める問題.

 全ての三角形の数 - extendableでない三角形の数
を求めれば良い.
全ての三角形を1回なぞりながら面積を計算して,任意の2点に対して,それを使う三角形の面積の最大値を覚えておけば,もう1回なぞれば答えは求まる.
ただし,それだと最悪計算量は (2500/3)^3 程度になっちゃうのでTLE.

extendableでない三角形の候補は,それぞれの色の頂点からなる集合の凸包を求めて,その凸包の外周部にある頂点だけ調べれば良い.
これだと最悪計算量は 200^3 程度になってなんとかなる.

HARD - ConnectingAirports (900pt)
2部グラフで,次数が与えられた時,その隣接行列の辞書順最小のものを求める問題.
ノードの数は両側とも50以下,同じノード間に2本以上の枝は張れない.

何も考えずに,一番最初の組み合わせから,その枝を使わなくても大丈夫かどうかを判定して確定していった.
判定はmax-flowを流した.
ノード数50+50でいくつか試して150msとかだったのでいけると思ったのだけどTLEもらえた.
この方針で通っている人もたくさんいるみたい.落ちてる人もたくさんいるみたいだけど.

じゃあ,どうすれば良いかというと,max-flowで毎回1から流すのではなくて,前の結果を利用して…という方針もあるみたいだけど,
よくよく考えれば,max-flowなんて使う必要無くて,対応する隣接行列が存在するかどうかはGreedyに枝を張って判定すればよい.

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

2009年03月11日20時から.
[ match overviws ] [ otinn.com summary (Japan) ]

EASY - BestView (250pt)
ビルの屋上から見える,ビルの屋上の数の最大値を求める問題.
ビルは50個以下,ビルは線分で表されていて,屋上と屋上を結ぶ線分上に他のビルの一部(端点を含む)があれば見えない.

全探索.計算してやるだけ.誤差が怖いので整数だけでやってみた.

MEDIUM - DoNotTurn (500pt)
迷路.上下左右に動ける.
一番左上から右下へ行くのに,何回左右に曲がらなければいけないか,最小値を求める問題.

BFSやるだけ.

HARD - CircularShifts (1000pt)
長さ60000以下の数列が2つ与えられる.
適当にシフトして,内積の最大値を求める問題.

片方を反転して,もう一方をサイクリックに長くして,多倍長整数みたく思って積を取ると,各桁に内積がでてくる.
なので,FFTすればよろしい,という問題だった.
全く気づかなかったし,気づいてもFFTをすんなり書けなかったと思う.

問題名,リンクは(多分)後で追加します.

(2009/03/13 12:20 EDIT) 問題名とLinkの追加.

2009 TCO Algorithm Round 1 (この記事を編集する[管理者用])

2009年03月08日02時から.
まだ問題の難易度はDIV2レベルか,それよりちょっと難しめかぐらい.

[ match overviws ] [ otinn.com summary (Japan) ]

EASY - SequenceSums (250pt)
入力は自然数NとL.
Nを連続したL個以上の非負整数の和に分割する.
そのような分割の仕方で,要素数最小のものを求める問題.
ただし,長さ100以下で存在しなければ,存在しないと返す.

全ての長さごとに,実際に分割できるか試してみる.

MEDIUM - KthProbableElement (500pt)
[LOW,HIGH]の自然数を独立にランダムにM個取ってくる(重複を許す).
そのM個の自然数のうち,K番目に小さい数字がNとなる確率を求める問題.

Nより小さいグループ,Nぴったり,Nより大きいグループ,それぞれが何個選ばれるかというのを全パターン確率を求めて,条件に合うのを足すだけ.
やたら大きな数字とか,小さな数字とか出てくるので,精度の問題とか心配になったけど,
問題の規模的にオーバーフローもアンダーフローもしないことだけ確認して,後は減算はないので桁落ちもなく全然問題ない.
別解としてはDPでも解けるみたい.

HARD - Unicorn (1000pt)
300×300の升目にアルファベットが書かれている.
1ステップで進める範囲が与えられた駒があるので,それを升目上を移動させて,軌跡として与えられた文字列を作るやり方は何通りあるか.
mod いくつかで求める問題.

(250や500と比べると少し実装が面倒な)単純なDP.ミスなく落ち着いて実装できますかという問題…,僕はできなくて悶絶した.
O(升目の数×文字列の長さ)で解くために,何を前計算しておくと良いかは,移動範囲を図示すれば簡単に分かる.
全マスのパターンの和と,各行,各列の和を計算しておけば良い.

C++以外の人(?)は定数倍最適化が必要になった場合があるみたい.
何も考えずに書いて,最大サイズのテストケースで500~600msぐらいだったので,少しタイムリミット厳しいのかなと思った.

Lv.185 / Vit.178347 / Att.23529 / Def.2790 (この記事を編集する[管理者用])

ハードモードでエンディング達成(だいぶ前に).

レベル186から雑魚敵の経験値が減っていくらしいのでレベル185で一旦止め.
一向に狂王に勝てる気がしない….時々一撃死は免れるようになったけど.

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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