Entries

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

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

模擬ICPCアジア地区予選2010 関西オンサイト (この記事を編集する[管理者用])

2010年12月04日11時から5時間,10問.(大阪大学豊中キャンパス)
[ LINK ]

ICPCの参加権がないのに,何故かチーム「京大4」としてソロチームで参加.
まぁ,オンサイトで人に合う機会が基本的にないので,とにかく,楽しかったです.
8問解いた.以下本番での行動順.

入力がファイルからということでfreopenを書く.
 引数の順番がわからない
 全探索してコンパイラに怒られないのを探そう….
  "A.txt"と"r"って逆でもコンパイラ怒ってくれなくないか?
  ちゃんと試そう.
  うまくいかない….
  …
  fopenしてfscanfで読み込むよ!
A問題をのんびり読む.
 読んでる間にもう解いてるチームは解いてるなぁ…,すげー.
 ふむふむ.やるだけ.O(NQ)でクエリごとに入力全部なぞればいいよね.
 まぁ,書くかな.
 書いた.サンプル合った.提出しない.
B問題をのんびり読む.
 さっそくのDP臭.
 同じ場所を2度連続で踏んではいけないのか,ふんふん.(読み間違え)
 右足と左足の位置でvalidかどうかの配列を最初につくって適当にDPすればいいや.
 100000*9*9*9?
 あれ?間に合わなくないか?
 違うや,次に置く場所は与えられるんだから100000*9*9か,右足と左足で2倍だけど,まぁ誤差.
 微妙だけど時間制限20秒とか書いてるし間に合うだろう.
 書く.
 サンプル1個だけ合わない.
 えー.
 あ,同じ場所を連続して同じ足で踏むのはありなのか.
 あれ,じゃ,9×9の状態とか要らなくないか?まぁいいや.
 サンプル通る.提出しない.
C問題をのんびり読む.
 どこからどこへ行くとかじゃなくて,ルートが与えられてるのか.
 態々ダンジョンマップで与えられるとか誰得….
 まぁ,やるだけか.
 使ったポーションの組と,今何歩あるいたか,残りHP,を状態にしてその状態に辿りつけるかどうかBFS….
 いや,状態数多いし.
 残りHPって,今まで受けたダメージと使ったポーションの組から回復量分かるし,状態に含めなくてよろしい.
  嘘!
  オーバー回復すると計算が合わない.
 うーん.
 あれ,単純に,使ったポーションの組と,何歩歩いたかを状態にして,残りHPの最大値を記録しておけばいいだけでは.
 良い.
 書く.
 サンプル合った.提出しない.
D問題をのんびり読む.
 めんどそう.
 取り敢えず次の問題を読もうか.
E問題を読む.
 図と雰囲気から無理ゲーの香り.逃げよう.
H問題を読む.
 問題タイトルと,入出力形式から,これは解けそうな気もする,と思ったから.
 単に,最短路に含まれうる枝を求めて,各ノードに入っていく枝で最もコストの小さいのを使うだけ.
 簡単.書く.
 ダイクストラなので,ライブラリ使えないし,しょうがないけどC++で書く.priority_queue便利だね.
 サンプル通る.なんとなく送ってみる.通った.
自分の席の前の方で,C問題の入力間違えてる疑惑などが囁かれている.
 じゃあ,C問題送ってみましょうか?
  送る.通る.
I問題を読む.
 えっと,オペレーターの最小値.
 オペレーターは最適な対応をする.(と読み間違えた)
 ふむふむ.
 DAGのパス被覆みたいな感じで最大流か何かに落ちる…?
 わからん.
J問題を読む.
 どうみてもDAGのパス被覆.
 じゃあI問題は全く違う方法で解くのかー.
 最大流書くのめんどい.
 しかし,Jが一番楽だよなぁ….
 書く.サンプル通る.サブミットしない.
F問題を読む.
 幾何.だがシミュレーションするだけで難しくないのでは.
 どうやって転がる? 円運動かな? そうっぽい.
 まぁ,適当に書く.
 めんどい.普段はライブラリに頼ってるからなぁ.ライブラリは偉大.
 うーん,流石に,2次元の点の構造体ぐらいは作ったほうが楽っぽいなぁ,書き書き.
 答えが合わない.
 あ,ここ,符号逆っぽい? 逆にする.サンプル合った.
 提出.コンパイルエラー.えー.
 cosとかsin使ってるので怒られてるっぽい?
 前回も同じ怒られ方して,clar投げて,-lm付けてもらったはずなのに….
 ヘルプを頼む.
 C++で提出してくださいとか言われたー.えーw
 C++で提出.WA.
 うーん,合ってそうなんだけどなぁ.
 あ,半径が0の時,回転角が0/0でNaNになってるのか.
 修正.通った.
D問題を書くかー.面倒だけど.
 うーん,どうせ答えって,たかだか4か5ぐらいだよね.
 適当にIterative deepeningでいいや.
 書く.回転の対応をハードコーディング.がりがり.
 書いた.実行.止まらない.
 間違ってた.サンプル通った.サブミット.WA.
 添字違った.サブミット.WA.
 まだ違った.サブミット.通った.
残り問題は無理ゲーに見える.
 E問題とG問題は実装ゲー.書ける気がしない.
 I問題は方針がわからない.
 残り1時間.
 貯めてた問題をそろそろサブミット.
 A問題・C問題・J問題を提出.通った×3.
I問題でも考えようか.
 ん,あれ.
 あ,電話かけてる人の中で一番IDが若い人から処理するのか.
 じゃ,シミュレーションするだけでね?
 2分探索して,O(N^2 log N)ぐらい.
 本当に2分探索して大丈夫? 計算量的にこうだろ.
 書く.
 サンプル合わない.
 2分探索したらダメらしい.
 えー.
 O(N^3)は無理っぽ.
 でも提出.TLE.
 ちょっとコード整理して枝刈りして提出.WA.え?
 書け直すタイミングが1間隔の時,処理ができてなかった.通った.ええええ.
終了.

ソースコード 問題A (C言語)

続きを読む

ACM/ICPC Japan Domestic 2009 (ぼやき) (この記事を編集する[管理者用])

昨日でした.参加者の皆様お疲れさまでした.

難易度的には
 (簡単) A = B < D = E < C <<<< F (難しい)
だったのかな….

去年と比べて,Bが簡単になったなぁ.
今年もDはダイクストラのD.
Eはまさかのマッチング.知らないと解けない.
今年の最終防衛問題Fは幾何.

実行時間制限がないのでCは愚直に書いてもOKだったみたいだけど,結構時間がかかるらしい.
ある程度最初に,各文字の使える数字を選別しておいて,探索は下の桁から決めていって枝刈りバックトラックするぐらいかなぁ….

North America - East Central - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先はLiveArchive.
[ Link ]

A. Bordering on Madness
読んでない.

B. Jack of All Trades
物々交換.
自分が出すものと自分が欲しいものが与えられる.
また,50人以下の人が出すもの,欲しいもの,その交換比率が与えられる.
9回以下の交換で,自分が欲しいもの1個当たりに,何個出すものを差し出せばよいか,最小値を求める問題.
また,そのレートを達成できる交換手順の数も求める.

基本的にはやるだけ.
出力の形式が有効数字5桁で出力せよというのが意外と面倒.

C. LCR
シミュレーション.
10人以下のプレイヤーが輪になってゲームをする.
皆,最初コインを3枚持っている.
順番にサイコロを3つずつ振る.
サイコロはCとLとRと.の4種類が書いてあって,Cが出ると自分のコインを中央の捨て場に捨てる.
L,Rが出るとそれぞれ自分の左,右の人にコインを1枚あげる.
ただし,コインを持ってる数が3枚より少なければ,持っているコインの数だけサイコロを振る.
1人を除いて誰もコインを所持していない状態になればゲーム終了で,コインを持っている人が勝者.

サイコロの出目が与えられたとき,ゲームをシミュレーションして最終状態を求める問題.
やるだけ.

D. Party Party Party
ある日に行われたパーティーの時間が与えられる.
パーティーの数は100個以下で,X時からY時まで開催したという形式で与えられる.
パーティーにいくと必ず30分は滞在しないといけない.
移動時間が0のとき,最大で何個のパーティーに参加できるかを求める問題.

Greedyにやればできると思うけど,問題サイズが小さいし,何も考えずに最大流した.

E. Su-Su-Sudoku
数独でまだ埋まっていないところが5箇所あるので数独を完成させてくださいという問題.
答えが存在しない場合はそれを指摘する.答えは存在するなら必ず1通りに定まる.

9^5通り全探索すれば良い.
プログラミングコンテスト系で良く見かけるし,数独解くライブラリでも作っておいても良いのかもしれない….

F. Tanks a Lot
円周上のサーキットがある.
いくつかの場所に燃料が落ちている.燃料の持てる量は無限.
最初燃料が全く無い場合,時計回り,反時計回り,それぞれに対して1周回ることができる初期位置を全部求める問題.

UVaで同じ問題があったような気がする….因みに当時出くわしたときは解けなかった.
燃料の落ちている位置をソートしておく.
後,適当に始点を決めておく.
1回燃料が落ちている位置をなぞって,始点からそれぞれ燃料が落ちている地点に行くためには,始点で幾ら燃料があれば良いかを求めておく.
今度は逆順になぞって,始点に燃料切れをおこさずに辿り着けるか,始点に辿りついたときに,さっき計算した自分の位置に戻ってこれるだけの燃料がたまっているかを判定する.

G. The Worm Turns
m*nのグリッドが与えられる.m*nは625以下.
グリッドの上には食べ物が落ちているグリッドがある.

あるグリッドから初めて,ある方向に食べ物が落ちている限り直進して食べる.
自分の前のグリッドに食べ物が無いなら左右どちらかに曲がる.
ということを繰り返して,食べることができる食べ物の数を最大化したい.
食べることができる食べ物の数の最大値,それを達成できる初期位置と方向を求める問題.
初期位置,方向はたくさんあれば辞書順最小のものを求める.

H. You'll be Working on the Railroad
枝数が50以下のグラフで,ある地点からある地点に辿り着くまでの最小コストの単純な路を求める問題.
ただし,最大2つまで通った枝のコストを0にすることができるが,最低1つの枝は正規のコストを払って通らなくてはいけない.
最小コストの路が2通り以上ある場合は,通るノードの数を最小にして,それでも複数あるなら辞書順最小のものを求める.
枝のコストは正.

適当にノードを分裂させてグラフを作ってやろうと思ったんだけど,それだと単純な路にならなかったりしてうまくいかなかった.
例えば
3
0 2 100
2 1 100
2 3 1
とかで
答えは0 2 1,cost 100のところを,0 2 3 2 1,cost 2としてしまったら駄目.

枝が高々50しかないので,O(枝数^2)のループを回して,どの枝をコスト0にするかを決めて,それぞれのグラフでダイクストラする.
ただし,コストが0になったら採用しないという風にすれば上手くいく.
1つのみ枝のコストを0にする場合とか,1つも枝のコストを0にしない場合とかを忘れてはいけない.

North America - Rocky Mountain - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先は基本的にLiveArchive.
[ Link ]
[ Official website ] : Judgeデータなど

A. Combination Lock
North America - Mid Atlantic - 2008/2009の問題Fと殆ど同じ問題.
ただし,最悪の場合ではなくて,初期値がランダムのときの平均値を求める.
やるだけ.

B. Lawrence of Arabia
North America - Mid Atlantic - 2008/2009の問題Dと同じ.

C. Close Enough Computations
North America - Mid Atlantic - 2008/2009の問題Aと同じ.

D. Walk in the Park
2次元平面上にN本の木とM本の道が与えられる.
木は点で道はx軸またはy軸に平行な直線.
道から見ることができる木の数を求める問題.
ただし,道からは上下左右の4方向しか見ることができなくて,間に木があると向こうの木は見えない.
NとMはそれぞれ10万以下.

やり方は色々ありそうだけど,例えば縮小座標に落として,x座標ごとにソートしてなぞっていって,y座標ごとにソートしてもう1回なぞっていく感じ.
とりあえず頑張って O( (N+M) log(N+M) ) 程度でやれば良いはず.

E. Dance
文字列処理実装問題,やるだけ.
与えられた文字列が,問題文で与えられた条件を満たしているかどうかを調べる問題.

F. Trucking
union + ダイクストラ.
ノード数1000以下の無向グラフが入力.
枝には,距離と通れる車高制限がある.車高制限のない枝もある.
出発地と目的地が与えられるので,最大で車高いくらの車が目的地に辿り着けるかを求めて,
更に,その車高の車が目的地に辿り着く最短距離を求める問題.
ただ,車高は制限があってそれ以上の車高の車は考えなくて良い.
(ここで書いてる説明は適当なので詳細は問題文を読むべし)

まず,車高制限のゆるい枝を付け加えていって出発地と目的地が連結になる最初の枝の車高制限が1つ目の答え.(クラスカルみたいな感じ)
後は,それよりゆるい枝のみを使ってダイクストラして最短距離を求める.
注意点は,道の車高制限が,最後に与えられる考える車高制限を超えてる場合もあって,最後に与えられる車高制限を越える値を出力しないように注意.

G. When
読んでない.

H. Prime Bases
素数進数みたいな感じの形式が問題文で定義されているので,10進数で与えられた数字をその形式に直す問題.
やるだけ.

Asia - Manila, Singapore - 2008/2009 (この記事を編集する[管理者用])

10問.
Jakarta.
Link先はLiveArchive.
[ Link ]

A. Anti Brute Force Lock
4桁の数字を1桁ずつ回転させて目的の数字に一致させることを考える.
最初は0000で,目標の数字は500個以下.
目標の数字に一致させる順番は任意でよくて,一度でも一致させたならその数字には回転無しで戻すことができる.

ちょっと考えれば,答えは0000から一番近い数字までの距離 + 最小木の重みの和になる.

B. Bonus Treasure
文字列を以下のように定義する:
 S[1]=(),S[k]=(S[1]S[2]...S[k-1])
S[N]のK文字目からM文字を出力する問題.
Nは31以下,Mは10000以下.
やるだけ.

C. Panda Land 7: Casino Island
ディーラーは1~Nまでの数字を並び替える.
各参加者iはディーラーの数字の最初からM_i個を予想する.
予想が当たっていたら参加者はお金をC[M_i]だけもらえる.

支払金C[1], C[2], ..., C[N]と各参加者の予想が与えられたとき,支払う金を最小とするようなpermutationを求める問題.
ただし,答えが複数あるならば辞書順で最初のものを求める.
Nは30以下,参加者の数は100000以下.

D. Disjoint Paths
ノードが60以下の木が与えられる.枝には距離が定義されている.
同じノードを2回以上使わずに,K個以下のパスを取ってきて,そのパスの長さの和を最大化する問題.

E. Expert Enough?
各自動車メーカーが過去に販売した車の最小金額と最大金額が与えられる.
今,販売価格の分かっている車が1000台以下あるので,それらを作っているメーカーを求める問題.
ただし,該当メーカーがない場合,2つ以上あって特定できない場合はその旨を出力する.
自動車メーカーの数は10000以下,車の価格は100万以下.

Fenwick Tree.

F. Free Parentheses
非負整数とその間に+か-の演算子が与えられる.
適当に括弧をつけて良いとき,得られる結果は何通り考えられるか.
項の数は30以下,各数字は100以下.

(プラスの後に括弧があっても意味無くて)マイナスの後に括弧があると思って,
 今何項目,今まで出てきた括弧で閉じてないものの数,今までの和
を状態としてメモ付探索というかDPというか.
状態数は最大で30*30*6000だけど,全ての状態に辿りつけるわけじゃないので,そこまで大きくないはず.

G. Greatest K-Palindrome Substring
与えられた文字列をまず最初にK文字以下変更しても良い.
その結果,文字列に含まれる回文の長さを最大化する問題.

全探索.
まず回文の中心を決めて,それから左右に1文字ずつ見ていって違う文字だったら片方を変更したと思って,最大長を求める.

H. Hyper-Mod
問題文で定義されている関数を mod M で計算する問題.
アッカーマン関数みたいなの.

I. ICPC Team Strategy
ICPC.(3人1チームで問題数Pのプログラミングコンテストに参加する)
各メンバーが各問題を解くのに必要な時間が与えられる.
制限時間280分で最大で何問解けるかを求める問題.
ただし,同じ人が2回連続で問題を解くことはできない.
Pは12以下.

ノード数3*2^Pのグラフを作って何も考えずにダイクストラした.

J. Jollybee Tournament
2^N人でトーナメント戦を行う.Nは10以下.
第1回戦で最初に現れなかった人のリストが与えられるので,不戦勝が起こる試合の数を求める問題.
シミュレーションするだけ.

North America - Greater New York - 2008/2009 (この記事を編集する[管理者用])

9問.
Link先は基本的にLiveArchive.
[ Link ]
[ official site (problems) ] ジャッジ解答,ジャッジ入出力など.

A. Sixth Grade Math
GCDとLCMを求める問題.
GCDはユークリッドの互除法,LCM=a*b/GCD.

B. Cryptoquote
AをGに置き換えて…系の1文字を別の1文字に置き換える暗号をデコードする問題.
書くだけ.

C. Binary Clock
何時何分何秒を2進数表示して縦や横に並べてたらどうなるかを求める問題(問題文参照).
書くだけ.

D. Recursively Palindromic Partitions
1000以下の自然数が入力.それの再帰的回文分割の数を求める問題.
27の回文分割とは例えば27=1+3+19+3+1のようなもの.
再帰的回文分割は,回文分割で,分割に含まれている自然数の,その左半分だけみても再帰的回文分割の形をしているもの(もしくは27=27みたいに1つのみからなる).
例えば27=1+3+1+17+1+3+1みたいなもの.1+3+1も再帰的回文分割.
もしくは,16=2+4+2+2+4+2みたいなもの.2+4+2も再帰的回文分割.

単純にO(n^2)のDPでもOKだけど,うまく考えるとO(n)のDPでも解ける.

E. Text Messaging Improvement?
各アルファベットの出現頻度が与えられたとき,携帯の文字の割り当てを変更して,1文字を入力するのに必要なボタンを押す数の平均を最小化する問題.
ただし,1つのボタンには1個以上8個以下の文字を割り当てなければいけない.

DPで良いと思うのだけども….
公式のジャッジ入力はとりあえず壊れているっぽい.出現頻度を足すと101%とかなる.

F. Extended Normal Order Sort
文字列処理 + 実装問題.
直感的なソートを実装したいので,2つの文字列の大小を比較せよという問題.
アルファベットは全て大文字に置き換えて考える.
数字っぽいところは数字だと思ってソートする.
数字は全ての1文字よりも小さい.
数字の定義は0~9の文字の連続.ただし,先頭に1つの+か-の符号がつくかもしれない.
ただし,+や-の前に数字があるならそれは符号ではない.

G. Area of Polycubes
3次元上に1個ずつ1*1*1の立方体を配置していく.(100個以下)
連結の定義は面で接していること.(中心間のマンハッタン距離が1)
もし,連結でなくなるときがあるなら,それが起こるときを指摘する.
もしくは,既に配置した場所に配置した場合もそれを指摘する.

最終的にできた物体の表面積を求める問題.
6nから接した面の数を引いていけば良い.

H. The Two Note Rag
2^Pで10進数で下R桁が1か2のみからなる最小のPを求める問題.
Rは20以下.

下1桁が2となるのは周期4で起こる.( 1→2→4→8→6→2→4→8→… )
なので,Rが2以上のとき,4飛ばしで調べていけば良い.
下2桁が1と2のみとなるのは周期20で起こるので20飛ばしで調べていけば良い…,
下3桁だと周期100,以下周期は5倍5倍になっていくらしい.
詳しくはofficial siteからリンクが張られている論文(pdf)を参照.

I. Joe's Triangular Gardens
読んでない.

North America - Mid Atlantic - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先はLiveArchive.
[ Link ]

A. Close Enough Computations
ある食品に含まれる脂肪,炭水化物,たんぱく質,カロリーが四捨五入した状態で与えられるので,矛盾がないか調べる問題.
脂肪は1グラム9カロリー,その他は1グラム4カロリー.
単に,考えられる区間を計算するだけ.

B. I-Soar
区間[x1,x2]に障害物があるといったような情報が与えられるので,区間[0,L]の間に障害物がない部分の長さの合計を計算する問題.
計算量は障害物の数の2乗オーダーで十分通る.なのでやるだけ.

C. Trie, Trie Again
読んでない.

D. Lawrence of Arabia
DP + 枝刈り.
一直線に1000個以下(n)の1以上5以下の数字が並んでいる.
1000回以下(m),並んでいる数字を区切ることができる.
各ブロックのスコアは,ブロックから2つの数字を選んでその積の和.
最終的にスコアを最小化する問題.

単純にDPすると O(m*n^2) となるのでTLE.
数字が1から5までしかないのと,ブロックのサイズが増えれば,そのブロックのスコアが飛躍的に上がるので,適当に等分割に分けてもそれほど悪い解ではないはず.
なので,そのGreedyに分けた場合のスコアを用いて適当に枝刈りすれば通った.

E. Series / Parallel Resistor Circuits
各点の間にある電気抵抗が与えられる.点の数は26以下.
2つの電気抵抗は,直列だと足し算,並列だと逆数の和の逆数の1つの抵抗と等価である.
それのみを利用してある2点間の抵抗を求める問題.
それだけでは求めれない場合や,そもそも連結でなかったりする場合はそれを指摘する.

以下の処理を繰り返すだけ.
 まず並列な部分を問答無用で処理する.
 後は,始点と終点以外で,2つの抵抗と繋がっているところを直列の式で直していく.

F. Combination Lock
金庫みたいな鍵で数字が何々になるまで回して回してを繰り返すタイプの鍵.
最悪ケースで,いくら回転させれば鍵が開くかを求める問題.
やるだけ.

G. Stems Sell
読んでない.
文字列置換実装問題?

H. Signal Strength
単純DP.
ノード数1000以下のDAGが与えられる.枝は数字の小さいノードから大きいノードにしか張られていない.
ノード0からノードn-1まで移動するのだけど,各ノードを通過するごとにノードごとに設定された定数倍されて,枝を通るごとに枝ごとに設定された定数倍される.
最初ノード0で1だったらノードn-1で最大で幾つになるか,求める問題.
たどり着けないなら0を返す.

Oceania - South Pacific - 2008/2009 (この記事を編集する[管理者用])

9問.
Link先はLiveArchive.(同じコンテストの問題番号は連番だと良いのになぁ…)
[ Link ]

A. Being Late
授業の正式な終了時間と実際の終了時間のログが与えられるので,平均でいくら延長しているかを求める問題.
早めに終了した授業については延長時間0で計算する.
やるだけ.

B. Money Lesson
移動後の各人が持っている5円玉,10円玉,20円玉の枚数が与えられる.
最初みんな同じ金額をもっていたけど,先生が1枚だけ移動させた(同じ場所に戻すのも含む).
さて,今もっている額は全員同じか,そうでなければ一番多い金額を持っている人,少ない金額を持っている人の名前を出力する問題.
やるだけ.

C. Explorer's Diary
文字列処理.
縦書きで1単語ごとに列を変えながら書いたので,元の文章を復元する問題.

D. Pattern Finder
100*100以下のサイズの升目に整数が書かれている.
最小の整数が書かれている升目のどれかから,最大の整数が書かれている升目のどれかにたどり着きたい.
上下左右に動けるけど,各ステップでの増分は一定値でなければいけない.

どの方向から辿り着いたかを記憶しておけば公差はわかるので,升目の数*4程度のノードのグラフ上でBFSするだけ.

E. Takeshi Castle
竜神池.
2次元平面上に石が50個以下あるので,最初の石から最後の石まで飛び移る.
挑戦者は30000人以下でそれぞれジャンプできる最大距離が与えられている.
風雲たけし城は難しくなきゃ風雲たけし城じゃないので,挑戦者のうち半分以上はクリアできないで欲しい.
ちゃんと,半分以上の人はクリアできませんか,判定する問題.

クリアに必要な最大ジャンプ距離を求めて,挑戦者をなぞる.
必要最大ジャンプ距離を求めるのは,Kruskalの要領で求めた.

F. Balanced Races
レースに参加したい人の実力と,1回のレースで参加できる最大人数(100以下),レース回数の最大数(100以下)が与えられるので,
同じレースに参加する実力差が最も大きい人の実力差を最小化する問題.

DPで何とかなったりするのかもしれないけど,素直に2分探索 + Greedyで良いと思う.

G. Smoker's Walk
サイズ100*100以下の2次元の升目上をある場所からある場所まで移動する.
そのとき,障害物(500個以下)があって,障害物に接触することはできず,移動したパスと障害物との距離の和を最大となるようなパスを選択したい.
距離はマンハッタン距離.
最大値を求めてください,という問題.

H. P2P Currency Service
300個以下のトレード要求がある.要求は自分が出すもの,自分が欲しいものといった形式.
自分が出すものが相手は欲しくて,自分が欲しいものが相手の出すものならばトレードできる.
ただし,自分自身とはトレードできず,各人トレードは1回しかできない.
考えうるトレードの最大回数はいくらか?

最大マッチング.

I. Currency Shopping
100種類以下の通貨の両替の際のレートが与えられる.
ある通貨をある通過に両替したいとき,他の通貨を経由しても良いので,最大でいくらのレートで両替できるかを求める問題.
ただし,無限に大きくできる場合は,それを指摘する.

Warshall-Floydみたいにやるだけ.
表示は小数点以下4桁を切り捨てで表示してくださいと書いてあるように見えるんだけど,それだとWAで普通に四捨五入したら通った.

Africa and the Middle East - Africa and Arab - 2008/2009 (この記事を編集する[管理者用])

Alexandria (Egypt) 2008/2009.
10問.
Link先はLiveArchive.

[ Link ]

A. Tobo or not Tobo
パズル.1から9までの数字が3*3の升目に書かれている.
1ステップで任意の2*2の正方形の部分を90度回転させることができる.
揃えるまでに必要なステップ数を求める問題.
ただし,9以下の上限が与えられて,それよりステップ数が必要なら-1を返す.

BFS.1回だけ最終状態から計算しておけば全てのクエリに答えられる.

B. Adding Sevens
7セグメント文字を光っている光っていないで7桁の2進数の数字にエンコードする.
エンコードされたA+B=という形の式が与えられるのでA+B=Cという形を出力する.
やるだけ.

C. Match Maker
*は偶数桁の任意の文字列,#は奇数桁の任意の文字列にマッチする.
与えられたパターンが,与えられた文字列にマッチするかどうかを判定する問題.
文字列の長さは100000以下.

D. Adding up Triangles
問題の図のような三角形が与えられたとき,内部の和が最大となるような三角形を求める問題.
数字のみ出せばよい,サイズは400段以下.

E. Relax! It's just a game
書くだけ.
サッカーとかのゲームで2チームの得点がA,Bである.
AとBは0以上10以下.
得点の入った順番がA+B通りかどうかを判定する問題.

F. Einbahnstrasse
文字列処理 + ダイクストラ + 逆グラフ作ってもう1回ダイクストラ.
有向グラフと目的地が与えられる.
始点から目的地に行って帰るのに必要な最小時間を求める問題.
ただし,目的地が複数与えられて,全て独立に行って帰る時間の和を求める.

G. Think I'll Buy Me a Football Team
1000個以下の銀行のそれぞれの銀行への借金が与えられる.
問題1は何も考えずに借金を返す場合,いくらお金が動くか.
問題2は,AがB,BがCに借金してるならAはCに返せばよい…等といった整理を行ったら,最小でいくらお金が動けば良いか.

問題1は足すだけ.
問題2は最終的にはDAGにまで落ちるので,各銀行の 貸してる額 - 借りてる額 が正ならばその数字を足していくだけ.

H. Musical Chairs
捻りも何もないヨセフス数DP.

I. I Speak Whales
2^n次の正方行列W[n]を
 W[0] = [ 1 ]
 W[n] = [ [ W[n-1], W[n-1] ], [ W[n-1], -W[n-1] ] ]
で定義する(問題文参照).
ある1つ行のある範囲の要素の和を求める問題.範囲は10000以下で,nは60以下.

10000 * nぐらいの計算量なら平気かと思ったけどそれだとTLE.
ちゃんと端だけ計算して,1行目は全て1,各ブロックの各行の和は0 (2行目以降) であることを利用すればO(n)で解ける.
だったら最初から範囲を10000以下にせずに,2^60以下で良いのに….

J. A Day at the Races
文字列処理 + ソート + 実装問題.
F1のレースの結果が与えられるので,レーサーとチームが獲得したポイントとともに順位順に出力する問題.

Asia - Amritapuri (India) - 2008/2009 (この記事を編集する[管理者用])

9問.
Link先はLiveArchive.
[ Link ]

A. Blocks for kids
遷移行列のべき乗を求める問題.
縦2,横nのサイズのグリッドを4種類のタイルで敷き詰めるやり方は何通りあるか.
ただし,グリッドを縦に切って最初に2つに分けて別々の人が敷き詰めるので,その切り方も考慮しなければいけない.

B. Paper Presentation
全探索 + DP.
学会の発表会.午前中の発表者がM人,午後の発表者がM人.(Mは8以下)
発表者は別の発表を引用していることがあるので,その場合は引用している発表は自分より前に発表してなければならない.
ただし,午前中の発表内容は午後には忘れている.
さて,発表の順番として考えられるのは何通りあるか?

C. Gold Digging
100箇所以下に金が埋まっている.
各場所ごとに,最初に金が埋まっている量,1回で掘り出せる量の割合,1回の掘り出し行為で機械が壊れる確率.
ある場所に対して金を掘り出そうとすると,一定確率で機械が壊れ,それ以上金を掘ることができなくなる.
機械が壊れなければ,現在金が埋まっている量に対してある割合だけ金が獲得できる.
さて,最適戦略で掘り出せる金の量の平均値は幾らか?

1回の行為で機械が壊れる確率は1%以上.

D. Minesweeper
やるだけ.
現在のマインスイーパーのマップが与えられる.
既にマインスイーパーが解かれているかどうかを判定する問題.
既に解かれているというのは,マップ上の数字が辻褄が合っていて,地雷が埋まっていない可能性がある場所は全て数字が書かれていること.

E. Palindromic paths
DP.
node数nのDAGで,全てのノード間に枝がある.枝にはアルファベットがつけられている.
最初のノードから最後のノードに行くパスのうち,最も長い回文ができるものを求める問題.
複数解があれば辞書順最小のものを返す.

F. Pile it down
2人でWythoff's gameをする.
2人とも一定回数だけパスすることができる.
勝つ人は最短手で勝とうとする,負ける人は最長にしようとする.
勝利者と必要ターンを返す問題.

G. Dice Poker
2人A,Bでサイコロを5個振ってポーカーっぽいことをする.
最初に振ったときの手が与えられるので,その後,それぞれ最適に振りなおしたときAが勝つ確率を求める問題.
最適とは,Aは勝つ確率を最大にする,Bは負けない確率を最大にする.

H. Advise National Security!
DP.
2人でN*M個のカメラを壊すのに必要な最短時間を求める問題.
ただし,それぞれのカメラは互いを監視しあってて,壊せるのは全ての壊れてないカメラから見えない場所にあるカメラだけ.
単位時間当たり1人当たり1つのカメラを壊すことができる.

カメラは一直線上に並んでいて,X番目のカメラはY(Y<X)番目のカメラは絶対に見えない.
X番目のカメラはX+N+1番目以降のカメラは全部見ることができる.

Mは15以下,Nは20以下.
素直にDPすると O(N^3 M 2^N)とかになってしまうので,どうしましょうか,ということを考える問題.
通したけど,その解法の正当性が証明できてないので書かない(なんとなく正しい気がするのだが).

I. Find Terrorists
やるだけ.
Bは10000以下で,[A, B]の範囲にある約数の数が素数個である自然数を列挙する問題.

Europe - Southeastern - 2008/2009 (この記事を編集する[管理者用])

Bucharest (Romania).
9問.
Link先はLiveArchive.
[ Link ]

A. Stock Exchange
最長増加列の長さを求める問題.
ライブラリコピペで終了.

B. Sky Code
10000個以下の10000以下の自然数の数列が与えられる.
その中から4個選んで,そのGCDが1になるような選び方は何通りあるか?

C. Perfect Election
N人の立候補者の中から何人か選ぶ.
M個の制約があって,それらを全て満たすような選び方は存在するか.
それぞれ制約は,誰々が選ばれる,誰々が選ばれない等といった条件が2つ与えられ,少なくても1つを満たしていれば良い.

D. Lucky cities
ノード,エッジ数がそれぞれ100000以下のグラフが与えられる.
3以上の奇数の長さの閉路に含まれるノードの数を求める問題.

E. Build Your Home
単純多角形の面積を求める問題.
ライブラリコピペで終了その2.

F. Quick answer
2つの集合をくっつけたり,集合の中から1つだけ要素を独立させるコマンド列が与えられる.
また,その途中途中で与えられた2要素が同じ集合に含まれているかどうか判定するクエリが与えられる.

G. Lucky numbers
ラッキーナンバーとは(10進数で)各桁が4または7だけからなる数字であって,
スーパーラッキーナンバーとは1つ以上のラッキーナンバーの積で書ける数字.
区間[a, b]の中にスーパーラッキーナンバーが何個あるかを求める問題.
a,b は高々 10^12 程度.

10^12以下のスーパーラッキーナンバーは数十万個しかないので,まずは全列挙して,後はクエリごとにバイナリサーチして個数を求める.

H. GCD Determinant
1000個以下の数列 {x_i} が与えられる.
i, j要素が gcd(x_i, x_j) なる行列の行列式を mod 1000000007 で求める問題.

I. Internet Service Providers
非負整数 N, C が与えられたとき,
 TN(C-TN)
を最大化する非負整数Tの中で最も小さいものを求める問題.
N=0の時は例外処理して,後は微分してT=C/2Nの周辺を調べる.

(2008/12/16 17:30追記) Gに関して記事を書いた.( Link )

North America - Mid Central - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先はLiveArchive.
[ Link ]

A. Parity
やるだけ.
{0, 1} からなる文字列と奇数か偶数かが与えられるので,1の数が奇数か偶数になるように最後に1文字追加する問題.
ここまで簡単な地区予選問題も珍しい気がする.

B. Lampyridae Teleportae
お手軽2次元幾何シミュレーション.
各ターンは
 蛍が光り,その光った方向に直線で移動する
ということを繰り返す.
各ターンに光る場所が与えられるので,いつ蛍を捕まえることができるか?
蛍が光ってから次に光るまでに,光った場所の距離1以内に行くことができれば捕まえれる.

C. Hex Tile Equations
探索.
6角形グリッドを一筆書きで全て通る.
グリッドには数字,または演算子と = が書いてあって,式が成り立つようにしたい.
そういう式はユニークに定まるのでそれを求めてください,という問題.

D. The Bridges of San Mochti
シミュレーション.
何個か橋が連続してある.
各橋は1グループしか同時にわたることはできない.
各橋ごとに同時に乗ってよい人数と,渡るのにかかる時間が与えられる.
橋の前に待機している人がいて,橋の上に人がいなければ即座に渡れるだけの人を1グループとして渡り始める.
全ての人が全ての橋を渡り終わるのにかかる時間は幾らか?

E. Bulletin Board
縮小座標作って塗りつぶし.
長方形の掲示板に長方形のポスターが100個以下貼ってある.
何も貼られていない面積,最も多くのポスターが重なっている枚数,最も多くのポスターが重なっている場所の面積を求める問題.

F. Serial Numbers
縮小座標作ってシミュレーション.
ある区間のIDを書き換える操作を100回以下行う.
最終的なIDを求める問題.

G. Line & Circle Maze
線分と円からグラフを作る.
グラフのノードは線分の端点,および交点.
2ノード間の最短距離が最も長くなるものを求める問題.

H. Steganography
文字列操作.
連続するスペースの数が偶数か奇数かで {0, 1} の列を作り,それを2進数だと思って該当する文字に置き換えていくだけ.

Asia - Hefei (China) - 2008/2009 (この記事を編集する[管理者用])

8問.
Link先はLiveArchive.
[ Link ]

難しいと思う….

A. A Simple Game
与えられた整数集合から2回独立に数字を選んだとき,その積がある数字を超える確率を求める問題.
符号について場合わけしながら尺取メソッドすれば良い.

B. Discrete Square Roots
 r^2 = x mod N
を満たす,(r,x,N)の組が与えられるので,
 y^2 = x mod N
を満たすyを全て求めよ,という問題.

C. Necklace
グラフがNecklaceがどうかを判定する問題.
定義は問題文参照.

D. Polynomial-time Reductions
有向グラフが入力.
2つの有向グラフが同値とは,あるノードからあるノードにたどり着けるかどうかが同じこととする.
入力と同値な有向グラフのうち,もっとも枝が少ないものの枝はいくつか?

E. Post Offices
10000個以下の都市が一直線上に並んでいる.
100個以下の都市に対してポストオフィスを建てる.
各都市に対して,そのポストオフィスで賄える都市の範囲,その都市にポストオフィスを建てるのに必要な金額が与えられる.
また,各都市ごとに賄えるポストオフィスが存在しない場合に必要な経費も与えられる.
費用を最小化せよ.

F. Programmers
1000人以下がメッセにログインしてる時間の範囲が与えられる.
その中から何人か選んで,その中では任意の2人がコンタクトを取れるようにしたい.
最大何人選べますか?という問題.
コンタクトを取ることができるというのは,同時にログインしてる時間が存在すること.

G. Rational Number Approximation
有理数 a/b と自然数 n が入力.
 a1/b1 <= a/b <= a2/b2
 b1, b2 <= n
を満たすa1/b1, a2/b2の中でa2/b2 - a1/b1を最小とするものを求める問題.

H. Triangles
2次元平面上に赤い点,緑の点,青い点がそれぞれ100個以下ある.
青い点を3点結んで三角形を作ったとき,内部にある赤い点と緑の点の数を比較したとき,赤い点の方が多い三角形,緑の点の方が多い三角形はそれぞれ何個あるか?

Asia - Aizu (Japan) - 2008/2009 (この記事を編集する[管理者用])

5時間10問.
Link先はLiveArchive.
[ Link ]

A. Grey Area
問題文を読んでそのとおりにやるだけ.
棒グラフを描くのに必要なインクの量を求める問題.

B. Expected Allowance
 m面ダイスをn回振って出た目の合計値 - 定数
だけお金がもらえる.0以下になった場合,1もらえる.
もらえるお金の期待値はいくらか?

DPでやるのが普通だと思うけど,入力の制約が全探索しろと言ってる.

C. Stopped Watches
時計がn個与えられる.
長針・短針・秒針の区別がなくて,時計全体を自由に回転しても良いとき,適当に時間を判断して,全ての時計の時差を小さくしたい.

全探索でやるだけ.尺取メソッドっぽく.

D. Digits on the Floor
幾何.
数字を7セグメント文字で書いて,単純な線分の交差などの関係のみで判定することにする.
2次元平面状に線分の集合が与えられるので,その中にある数字をそれぞれカウントする問題.

E. Spherical Mirrors
3次元幾何 + シミュレーション.
3次元空間上に球の形をした鏡がいくつか浮かんでいる.
原点からある方向にレーザービームを飛ばしたとき,最後に鏡に反射する点を求める問題.

F. Traveling Cube
BFS.
サイコロをころころ転がして目的の場所に順番に行く.
最小で何回転がせばたどり着けるか.
ただし,目的の場所には色が着いていて,そこにたどり着くときにサイコロの上の面の色と一致してなければならない.

G. Search of Concatenated Strings
DP.
与えられた文字列を適当にくっつけてできる文字列が,長い文字列の中に幾つ含まれるかを求める問題.

H. Top Spinning
読んでない.

I. Common Polynomial
文字列操作 + 構文解析 + 多項式GCD.
与えられた2つの多項式のGCDを求める問題.
構文解析して入力を理解したら,ユークリッドの互除法.

J. Zigzag
2次元平面上のいくつかの点が与えられる.
それらを全て通るような折れ線のうちで,
 最も折れ曲がりの回数が少ないもの
 その中で折れ線の長さが最も短いもの
を求める問題.

North America - South Central - 2008/2009 (この記事を編集する[管理者用])

中途半端だけど,取り敢えずメモしておく.
追加で問題解いたときに,また書き直すかもしれない.

9問.
Link先はLive Archive.
[ Link ]

A. Rank and File
読んでない.

B. The Extent of the Problem
読んでない.

C. Filtration
読んでない.

D. Like Water for Clay
やるだけ.塗りつぶす.
水が貯まる升目の数を求める問題.
上下左右,どれを下にするかで90度回転しながら4通り求めなければいけない.
隣接関係は8近傍.
水が貯まるマスの数を求めるのは O( マップのサイズ ) で計算可能.

E. Wandering Aimlessly
シミュレーション.
RPGの町人の歩く手順が与えられるので n ターン目の町のマップを出力する問題.
移動する先が壁や町の外に出るようなら移動しない.また,町人同士はぶつからないことが保障されている.
一連のコマンドが終わった後,元の位置に戻るなら,その一連のコマンドを連続して行う.
元の位置に戻らないなら,同じステップを逆向きに辿ってもとの位置に戻る.そしてそれを繰り返す.

各キャラごとに,
 求めるターン % ( 2 * 一連のコマンドにかかるターン数 )
ターン後の位置をシミュレーションで求める.

F. Cables ... in Spaaace!
簡単幾何 + MST.
球状の2点間の距離は表面上で考える.
n 都市の緯度・経度が与えられ,それらの全域最小木の枝の長さの和は,与えられた入力より小さいかどうかを判定する問題.

G. Patterns and Pictures
やるだけ.個人的には + 英文読解.
でかい絵はとあるパターンの連続である.
とあるパターンが入力で与えられて,そのパターンに含まれる小さな絵の面積とその数が与えられる.
でかい絵の面積が n * 36 * 36 ( n = 1, 2, 3 ) のとき,最大でパターンは何個含まれるか.

floor( でかい絵の面積 / 各パターンに含まれる絵の面積の総和 )

H. No Wormholes Were Harmed...
タイムトラベラー.
今西暦 x 年で, y 年に用事がある.
y 年に行った後, x 年に戻るためには,最低どのぐらい年齢が増えるか,を求める問題.

wormhole と呼ばれる時空を越える穴があって,
それを使って a 年後に移動した場合は floor( a / 2 ) 歳だけ年を取る.
a 年前に移動した場合は floor( a / 4 ) 歳だけ若返る.
それぞれのwormhole は入力で与えられたとある年からとある年に移動することができる.

負の枝はあるものの,負の閉路はないのでダイクストラすれば良い.

I. Tribute (Editor)
読んでない.

ACM/ICPC 2008 国内予選 (この記事を編集する[管理者用])

結果でました.
やっぱり東大は強いですね.
というか,全問解いたのが3チームもいたのは凄いです.
問題見て1チームぐらいは全部解きそうだなーとは思ったのですが.

ACM/ICPC 2008 国内予選 (この記事を編集する[管理者用])

現在開催中ですが,取り敢えずF以外は解いたつもりになってみた.
(サンプルは通るプログラムを書いた)
5問で1時間10~1時間20分ぐらい.

A. Brute-force

B. 変形エラトステネスで全部月曜土曜素数を求める

C. 実装.文字列処理.

D. 国内予選おなじみ,変形ダイクストラ.
ダイクストラを真面目に書くのは面倒だったので,更新されなくなるまでベルマン・フォードっぽく.
これだと最悪計算量がだいたい(30*30*4)^2=3600^2なのでオンラインジャッジでは危険かも.

E. 幾何.線分と線分との距離って思ってたより面倒なことがわかった….

F. 1が36個以下らしいので,たぶん頑張って探索…?

Appendix

Recent Articles

ブログ内検索

Ads


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