Entries

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

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

LiveArchive 4410 - Shooting the Monster (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
2つの多角形が与えられる.時間t=0で1つはy軸より左,1つは右にある.
y軸より左にある多角形はスピード1で右に進んでいる.
 ∫共通部分の面積 dt (tは0から∞)
を求める問題.
多角形の頂点は格子点上で,y座標は-500から500程度.多角形の頂点数はそれぞれ50個以下.

[ 解答 ]
面倒な実装問題かと思ったけどよくよく考えると大して面倒でもなかった.
2つの多角形について,各y座標に対してヒストグラムを作る.
区間1ずつに区切って考えると高々1次関数なのでそんなに大変ではない.
後は,それをかけて積分するだけ.

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のレースの結果が与えられるので,レーサーとチームが獲得したポイントとともに順位順に出力する問題.

LiveArchive 4412 - The Great Game (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
じゃんけん勝負をする.勝つ確率を求める問題.
1セットは1000回以下の勝負で,相手が出す手の確率は毎回のセットのうちの何番目の勝負か,で決まっている.
取ったセット数がWだけ差をつければ自分の勝ちで,Lだけ差をつけられれば自分の負け.
WとLはそれぞれ100以下.

[ 解答 ]
1セットの勝率 ( 正確には 勝つ確率/(引き分けでない確率) ) がわかれば,解析解が存在する.
http://en.wikipedia.org/wiki/Gambler%27s_ruin
1セットの勝率は,2分探索 + O(N^2)のDPで求まる.

Contest of Newbies V (この記事を編集する[管理者用])

2007年12月27日21時から,4時間.
[ Link ]

A. Simple Equations
1以上10000以下の自然数A, B, Cが与えられたとき,
 x + y + z = A
 xyz = B
 x^2 + y^2 + z^2 = C
となるような,互いに異なる整数x, y, zを求める問題.
複数なるならばxが最小となるもの,次にyが最小となるものを選ぶ.
2乗和の上限がCなので,x, yに関して-100から100ぐらいまで全探索すれば良い.

B. Let's Yum Cha!
ナップザック問題.
ただし色々面倒な要素が混じっているだけ.

C. Moliu Number Generator
最初の数値は0で1足したり1引いたり2倍したりできる.
与えられたNに対して何ステップでNにできるかを求める問題.
基本的には,Nが2の倍数ならN/2を作るのに必要なステップ数 + 1,
Nが奇数なら(N+1)/2,(N-1)/2を作るのに必要なステップ数(の小さいほう) + 2.
とりあえず,Nが小さいとき(sqrt(2^31)以下)程度のときは答えをメモしておいて,後は探索すれば良い.

てっきり入力が2^31未満だと思ってWAもらってたけど,実は制約が2^31以下で,unsignedじゃないと読み込めないという罠が….

D. Pincer Attack!!
シミュレーション + DFS.
ロボットが適当に巡回している迷路でロボットに捕まらずに脱出できる手順を出力する問題.

E. Lovely Hint
DP. (枝刈り探索でも可能?)
Aは1,Zは26とアルファベットに番号をつけて,使えるアルファべットが与えられたとき,
隣り合うアルファベット間に 5*番号 <= 4*次の文字の番号 を満たすように並べる.
最長いくらか,また最長を達成する並べ方は何通りあるかを求める問題.

F. Sudoku without numbers?
数独を解く問題.答えは一意に定まることが保障されている.
ただ,最初から数字がいくらか入っているのではなくて,隣り合う枡の数字の大小関係が与えられている.

タイムリミットが結構ゆるくて何も考えずに全探索しても良い.

G. Simple Equations - Extreme!!
Aと同じ問題.
ただし,入力A,B,Cの上限が6*10^18となっている.

 xyz = B
から絶対値最小のx,y,zは高々10^6程度で,後は適当に連立方程式を解いて求めようとしたけどTLEもらった.

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

2008年12月24日11時から.
[ match overviws ] [ otinn.com summary (Japan) ]

DIV1 EASY (250pt)
2次元で,x > 0 の範囲に線分からなる物体が50個以下ある.
ランダムに角度を選んで原点からレーザーを発射したとき,貫通する物体の数の期待値を求める問題.

期待値なので,各物体を貫通する確率を別々に求めて足せば良い.
貫通する確率はatan2等を使えば計算できる.

DIV1 MEDIUM (500pt)
自然数で,適当にA個に区切ると各部分の桁が等差数列になっているもののうち,N桁全体で各桁が非減少のものをcool数という.
mega-cool数はA-1個に区切って等差数列にできないものをいう.
N桁の自然数でmega-cool数はいくつあるかを求める問題,ただしmod 1,000,000,007で.

結局色々考えるとDPに落ちる.
Aが10以上なら問答無用で答えは0で,dp[N][A][前の部分の最後の数字][前の部分の等差数列の公差]みたいな感じ.

DIV1 HARD (1000pt)
N*Nの升目が白黒に色分けされている.
白い升目のみからなる長方形で,他の白い升目のみからなる長方形に包含されないものの数を求める問題.
Nは2000以下.

色々とやり方はあるみたい.

DIV2 EASY (250pt)
mega-cool数とは,各桁を数列と見たときに等差数列となっているもの.
1以上N以下のmega-cool数の数を求める問題.
Nは1000以下.

やるだけ.

DIV2 MEDIUM (500pt)
サイズ50以下配列x[i]が与えられる.
順番にx座標がx[i]でy座標が無限大の部分から点を落下させる.
点が止まるのは,1つ前に落下した点と距離がRになったときか,y=0に到達したとき.
止まるy座標を求める問題.

シミュレーション,やるだけ.

DIV2 HARD (1000pt)
自然数SとPが与えられたとき,非負実数N個からなる集合で,和がSで積がNになるようにすることができる,最小のNを求める問題.
そのようなNが存在しないならそれを指摘する.

NとSを固定して考えると,積が最大となるのは要素が全部S/Nのときで,和を変えずに積の値を減らすことはできるので,(S/N)^NがP以上となる最小のNを求めればよい.
Nはそんなに大きくなるわけないので適当な停止条件をつけた上で全探索する.
ただし,SがNより大きいときは問答無用で2が答えなので気をつける.

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

2008年12月21日02時から,ただし部屋割りが終わらなくて実質5分遅れで開始,5分延長.
[ match overviws ] [ otinn.com summary (Japan) ]

1000ptが過去のSRM 500ptの問題の類題だった.
1位になった人おめでとうございます.

EASY (250pt)
適当にAd-hocにやれば良い.

MEDIUM (500pt)
DP.
ただし,重複しないようにだけ少し注意する.

HARD (1000pt)
2つに分けて全探索 + 尺取メソッド.

(2008/12/29 12:55編集) match overviws, otinn.com summary (Japan), 各問題へのリンク追加.

ACM ICPC::Kualalumpur Regional Contest (Semi Live) (この記事を編集する[管理者用])

2008年12月20日18時から7時間,11問.
[ Link ]

ご飯食べながら3時間で7問解いて,残りはずっとDに嵌ってた.
結局8問解けて,解けなかった問題はG,H,J.

ついでに現地で戦ってた人の記事.[ Link ]

A. ASCII Diamond
やるだけ.

B. Match Maker
状態数2^15のDPと経路復元.

C. Tariff Plan
やるだけ.

D. Irreducible Fractions
aとbが与えられたとき,任意の自然数nに対して
 (an+x)/(bn+y)
が既約分数となるような 0 <= x,y <= 10^7 の数を求める問題.
計算すると問題文に書かれているp,qの範囲がそれぞれb,aの約数でなければいけないことがわかって,後はp,q全パターンに対してx,yが満たすべき直線の式を求めて,その直線が通る格子点の数を頑張って計算する.

E. Gun Fight
グラフ作って最大流流すだけ(最大マッチング).

F. Unlock the Lock
BFSするだけ.
最初の数字と目標の数字が与えられ,ボタンが10個以下あってボタンを押すと現在の数字に一定数足される.
目標の数字を得るのに必要なボタンを押す回数は最低何回か?
ただし,数字は全てmod 10000で保存される.

G. Ironman Race in Treeland
ノード数30000以下の木で,各枝に2要素,長さとダメージが与えられる.
ダメージが一定数以下という制約の元で長さ最長のパスを求める問題.

H. Shooting the Monster
おそらく超絶実装問題.
2つの多角形が与えられる.時間t=0で1つはy軸より左,1つは右にある.
y軸より左にある多角形はスピード1で右に進んでいる.
 ∫共通部分の面積 dt (tは0から∞)
を求める問題.

I. Addition-Subtraction Game
ノード数100以下のDAGが与えられる.
ただし,各ノードから出ている枝の数の最大値は15.
また,各ノードに1以上100以下のパラメータが与えられている.

2人でゲームをする.
最初に各ノードに適当に石が置いてある.
各ターンでは,枝が出ているノード(パラメータa)にある石を1個取り去って,その分,枝がでている先のノードに合計でa個だけ石を追加する.
石を取り除くことができなくなったら負け.

あからさまにGrundy numberを求める問題.
計算時間も100*2^15でいける.

J. The Great game
じゃんけん勝負をする.勝つ確率を求める問題.
1セットは1000回以下の勝負で,相手が出す手の確率は毎回のセットのうちの何番目の勝負か,で決まっている.
取ったセット数がWだけ差をつければ自分の勝ちで,Lだけ差をつけられれば自分の負け.
WとLはそれぞれ100以下.

まず,1セットでの勝率を最適化するのが難しいし,Wセットだけ差をつける確率とか計算するのも多分そんなに簡単ではない.

K. Triangle Hazard
2次元幾何計算問題.頑張って計算して書くだけ.
問題文の図で点P,Q,Rの座標とm1,..,m6の比率が与えられるので,A,B,Cの座標を求める問題.

OnlineJudge記事まとめ (この記事を編集する[管理者用])

OnlineJudge記事まとめを作ってみた.
http://rsujskf.blog32.fc2.com/blog-entry-174.html

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]の範囲にある約数の数が素数個である自然数を列挙する問題.

LiveArchive 4190 - GCD Determinant (この記事を編集する[管理者用])

[ Link ]
ACM/ICPC Europe - Southeastern - 2008/2009の問題.( blog )

[ 問題概要 ]
1000個以下の数列 {x_i} が与えられる.
x_iの約数は全て数列の中に入っていることが保障されている.
i, j要素が gcd(x_i, x_j) なる行列の行列式を mod 1000000007 で求める問題.

続きを読む

One more high level contest (この記事を編集する[管理者用])

2008年12月13日17時から5時間,10問.
The 2008 Nordic Collegiate Programming Contest.
[ Link ]

8問解けた.
解けなかったのはDとJ.

3分探索で
 c1 = (a+a+b)/3, c2 = (a+a+b)/3;
とか書いてて8個もWAもらった.死にたい.

A. Aspen Avenue
長さLで道幅Wの道の両側に等間隔にn本の木を植えたい.nは偶数.
しかし,木は最初,道の左端に適当に置いてあるので,所定の位置に動かすのに必要な最小移動距離は幾らか,という問題.
Greedyでいけそうでいけない問題.素直にDPすれば良い.
因みに,狂った頭で最小費用流なんか回した日にはTLEがもらえた.

B. Best Compression Ever
異なるn個のファイルを圧縮したら全てbビット以下になった.
そんな圧縮方法は存在するのか?という問題.
2^(b+1)-1 <= nならば存在すると答えるだけ.

C. Code Theft
文字列処理 + 実装 + 二分探索 + Rabin-Karp.
コードが与えられ,それとは別にn個のコードが与えられる.
行の初め,終わりのスペースは無視する,2個以上連続してるスペースは1個のスペースと同値と思う,空行を無視する.
n個のコードのうち,最初のコードと同じ行が連続して続く行数が最大となるコードはどれか?
行数は10000以下.

D. Dinner
400人以下の人が顔見知りになった年が与えられる.
さて,2つのグループに分けて,片方のグループはy年より前に全員顔見知りになった,もう片方のグループはy年より前には誰も顔見知りではない,というようなグループの分け方が存在する最小の年yを求める問題.
2つのグループはそれぞれn/3人以上2n/3人以下でなければならない.

E. Event Planning
やるだけ.
n人の人がある期間のうちに同時に同じホテルに1回泊まりたい.
ホテルの価格とその期間におけるホテルの価格が与えられるのでコストを最小にしてくださいという問題.

F. Fixing the Bugs
Greedy + DP.
10個以下のバグがあって,1つバグを潰すごとに点数がもらえる.
それぞれ時間1でバグを潰せる確率が与えられるので,時間100以下で得られる点数の期待値を最大化する問題.
ただし,1回バグを潰すのに失敗したら,そのバグは実は手ごわいということで,次に時間1でそのバグを潰せる確率はf倍される.

Greedyにやるれば良いので,どれのバグを潰しにかかるかを状況ごとに最初に計算しておく.
後はDPで計算時間,計算領域ともに O( 2^バグの数 * 時間^2 ) 程度で計算できる.

G. Getting Gold
高々50*50の2次元グリッドが与えられ,初期位置,ゴールドの位置(たくさん),トラップの位置(たくさん),障害物が与えられる.
歩く人にはトラップは見えないけど,トラップに隣接したら近くにトラップがあることが分かる.
トラップに絶対ひっかからないようにしながら得られるゴールドの数は最大でいくつか?
DFSするだけ.

H. Hard Evidence
凸な多角形とそれを完全に囲む円が与えられる.
円の外の点Oから多角形の見たとき,見えるもっとも左の点ともっとも右の点をLとRとする.
角度LORを最大化する問題.

Oは円周上に取れば良くて,円周を適当に分割してそれぞれの範囲で3分探索する.
凸多角形なので,もっとも右の点とかを計算するのはO(n)かけてはいけない.

I. Introspective Caching
Greedy + Heap.
未来にアクセスするものが完全に分かっている場合,キャッシュの動作を最適化する問題.
キャッシュの中身を捨てるときに,最も次回アクセスまでの時間が長いものを捨てれば良い.

J. Just A Few More Triangles!
500000以下の自然数 N が与えられたときに,
 a^2 + b^2 = c^2 mod N
を満たす 0 <= a <= b <= N-1, 0 <= c <= N-1 の組の個数を求める問題.

The 1st Imos Contest (この記事を編集する[管理者用])

2008年12月13日12時30分から3時間,6問.

KMCoderで誘われたので参加してしまった.
結構面白かったです.コンテスト主催者様お疲れ様でした.

15時30分に投稿されるように予約しておく.

A. Extended RSA
素数bとc,20以下のdが与えられるので
 ab = c ( mod 2^d )
を満たす最小の素数aを求める問題.
答えは2^31未満であることが保障されている.
もしbが2ならbとcと2^dを2で割っておけばbと2^dは互いに素とすることができる.
後は,全探索してaを見つけて,素数でなければ素数になるまで2^dを足し続ける.

B. Product-Sum
偶数桁の自然数を真ん中で2つにぶった切って,左をa右をbとする.
 a*b - (a+b) = N
となるような最小の偶数桁の自然数を求める問題.
 a = (N+b) / (b-1)
なので,bを2から動かしてa >= bの範囲を全部調べる.
そして,aとbが同じ桁ならaとbをひっくり返すのを忘れない.

C. Apple Trees
2次元平面上に10000個以下の点(ただし偶数個)がある.
原点を通り,点を半分ずつに分ける直線を1つ求める問題.
まず適当に線を引いて,後はすこしずつ傾けていく.

最初の点からの角度を求めるのに,x軸からの角度を求めていて2回WAもらった…,ちゃんと問題を読もう.
他の1回のWAは最初Cでmath.hが使えなかったから拡張子をcppにして送ったらどうだろうと試してみたもの.

D. Mountain Residence
1000以下の自然数が書かれたn*nのグリッドが与えられる.
その中のs*sのグリッドで
 グリッドに書かれた数字の最大値 - 平均値
を最小とするものを求める問題.
平均値の方に関しては,結局和を求めるだけなので普通に足していくだけで O(n^2) で求まる.
最大値の方は,書かれている自然数が1000以下なのでsegment treeを使えば O( n (1000+n log(1000) ) )ぐらいで計算できる.

E. Pie Party
0と5の間の実数Rと自然数Lが与えられたとき,
 | R - D/N | , N <= L
を最小とするD/Nを求める問題.
L <= 10000000なのでO(L)は微妙かと思ったけど,とりあえずStern Brocot Tree送ったら通った.

F. Gear Factory
100個以下のギアが与えられるので,それを組み合わせて与えられたギア比を作る問題.
作り方は高々1通りしかなくて,ギアは無限に使ってよい.
素因数分解して有理数の連立一次方程式に落として,後は頑張って解くだけ.

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

2008年12月12日01時から.
[ overview ] [ otinn.com summary (Japan) ]

正直間違えてDIV2用の問題がDIV1で出題されたのかと思うぐらいの難易度だった.
1問ミスれば致命傷で,後は1000pt速解き勝負.

EASY (250pt)
アルファベットが書かれた100×100以下のグリッドが与えられる.
グリッドに含まれる長方形を全て取ってきて,それらに書かれているそれぞれの文字をカウントする問題.
元々のグリッド上で各文字に対して,それを含むような長方形の数を計算して足していくだけ.

MEDIUM (500pt)
x1,x2,...,xnのn個の未知量があって,n-1個の関係式が与えられる.
関係式は,xi : xj = a : bといった感じに比率が与えられる.
制約を満たす最小の正の整数x1,x2,...,xnを求める問題.
やるだけ.

HARD (1000pt)
最大50×50のところどころ欠けているグリッドに2つの図形A, Bで敷き詰める.
敷き詰めれるかどうかを判定し,敷き詰めれるなら敷き詰めた結果で辞書順最小のものを求める問題.

図形の形から敷き詰めれるかどうかはAd-hocに敷き詰めれば良いことがわかる.
それでは,辞書順最小にならないので,最初のほうから1つずつAを置いた場合に,まだ敷き詰めれるなら採用して,敷き詰めれないならBを置いて次に移るということを繰り返す.

ケアレスミス (この記事を編集する[管理者用])

2週間ぐらい前からコーディングの時,ケアレスミスをやらかすことがやたらと多い.
半年前ぐらいからはケアレスミスなんて殆どしなくなったんだけどなぁ….
一行書く場所を間違えてTopCoderで840点失うとか凹むので何とかしたい….

PKU 2431 - Expedition (この記事を編集する[管理者用])

[ Link ]

[ 問題概要 ]
1次元上で,車を運転してxだけ進みたい.
ただし,最初につまれている燃料が限られていて,途中で落ちている燃料を拾っていかなければならない.
燃料を拾う回数を最小化する問題.
持てる燃料の量に上限はなく,燃料は最初いる地点から進みたい方向にxだけ行く間にしか落ちてない.(逆向きに進んで燃料を拾うようなことは考えなくて良い)

落ちている燃料の場所の数は10000以下.

続きを読む

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点結んで三角形を作ったとき,内部にある赤い点と緑の点の数を比較したとき,赤い点の方が多い三角形,緑の点の方が多い三角形はそれぞれ何個あるか?

#include<math.h> (この記事を編集する[管理者用])

面白い現象で嵌ったのでメモしておく.
KMCoder SRM67 950pt問題 [ Link ] でWAもらっていたのだけど,
#include<math.h>
を書き足しただけでACをもらえた.

コンパイラ#include<math.h>を書いたか結果
C書いたAccept
GCC書いたAccept
C書かないWrong Answer
GCC書かないAccept

多分,ceilやfloorが変な動作したんだろうなぁ….
とりあえず,これからはちゃんと#include<math.h>を書くようにしよう….

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

闘神都市3 - 活力86160/攻撃14239/防御2111 (この記事を編集する[管理者用])

回復薬60万個以上使ったけど召喚ドア最後の敵を倒した.
後は見てないCG埋めたらやることないな….

続きを読む

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

の問題セットがLiveArchiveに追加された.
[ Link ]

G問題(Search of Concatenated Strings)がようやく通ったー.
残りの問題は暇なときにまたやろうっと.

闘神都市3 - 活力68616/攻撃7398/防御1849 (この記事を編集する[管理者用])

Status [ jpg ]
召喚ドアとかの進捗状況は続きに.

続きを読む

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

2008年12月02日21時から.

結構簡単な問題セットだと思うのだけれども,皆点数は高くない.
特に僕の点数はとても酷かった.

EASY (250pt)
10文字以下の文字列が与えられる.
文字列を並び替えて,隣り合う文字がすべて異なるような文字列は何種類できるか?
next_permutationして数えるだけ.

MEDIUM (500pt)
26種類のアルファベットを並べて,N文字以下の回文を作る.
その中で,k種類以下しか使われていないような回文はいくつあるか?

包除原理や等比級数の和の公式やコンビネーションを用いて計算すればOK.
和の公式では a / b = a * b^(p-2) mod p を使う.
もしくは,1文字ずつ追加していくことを考えて,現在使用している文字の種類をカウントしていくことを考えると,遷移行列が作れるので,べき乗を求めれば良い.

HARD (1000pt)
2人でゲームする.
1直線上の16マスにLまたはOを順番に書き入れていって,LOLを作ったほうが勝ち.
勝つなら最短で勝てる,負けるなら最長で負けるような戦略をとるとき,結果はどうなるか?
最初の状態が与えられる.

状態数3^16でDPすると,微妙にTLEになる.
制限時間が2秒でなく3秒なら確実に通るぐらいの微妙さ.
頑張って高速化すれば通ると思うのだけれども,よくよく考えればTLEになっちゃうテストケースは高々十数個~数十個しかないので,それをローカルで計算してしまって埋め込めば通る.
実際に通している人は,皆答えを埋め込んでいた.
流石に答えを埋め込むのが想定解法ではないと思うのだけれども.

闘神都市3 - レベル50 (才能限界) (この記事を編集する[管理者用])

続く.

続きを読む

闘神都市3 - レベル41ぐらい (この記事を編集する[管理者用])

終わった.

とりあえず,面白かった.
相変わらずふみゃ姉さん良い仕事しすぎでした.

細かい感想とかは続きに(ネタバレ).

最終追記 2008/12/01 16:10.

続きを読む

闘神都市3 - レベル38 (この記事を編集する[管理者用])

ネタバレ要素があるので続く.

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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