Entries

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

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

未使用問題: Ciel and Dice [CIELDICE] (この記事を編集する[管理者用])

This is an unused problem for CodeChef March Cook-Off 2012.

Ciel has N dice. The i-th die is a fair Ai-sided die. For a single roll of fair k-sided dice, the number i is shown with probability 1/k for all 1 ≤ ik. (I don't know what 1-sided dice are like, but Ciel may have them!)

Ciel sometimes holds the game with her dice. In the game, Ciel rolls her N dice, and asks the challenger to answer the sum of the numbers which are shown. Of course, the result of the rolling is concealed, but Ciel gives one hint to the challenger. Ciel's hint is the sum S of Xk-th die over all 1 ≤ kM, where Xk are distinct. If the challenger's answer is correct, the challenger get any food menu in the restaurant for free.

Your task is to find the most probable sum for various her hints.

Input

The first line contains 2 integers N and Q, where Q is the number of hints. Then next line contains N integers A1, A2, ..., AN. Then next Q lines contain M+2 integers M, S, X1, X2, ..., XM.

Output

For each hint, if the hint must be wrong, print "Ciel lies" without quotes. Otherwise print the most probable sum. If there are multiple answers, print the minimal one.

Constraints

1 ≤ N ≤ 50000 (5 * 104)
1 ≤ Q ≤ 1500
1 ≤ Ai ≤ 1000000000 (109)
0 ≤ M ≤ 500
0 ≤ S ≤ 1000000000000000000 (1018)
1 ≤ XiN
XiXj (ij)

Sample Input

2 1
6 6
0 0

Sample Output

7

Sample Input

4 2
1 2 3 4
2 3 1 2
2 6 2 3

Sample Output

7
Ciel lies

Output details

The first hint of the first sample input is totally useless. Ciel rolls two six-sided dice, the most probable sum is 7 which occurs with probability 6/36 = 1/6, because there are 6 patterns (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) whose sum is 7.

For the first hint of the second sample input, there are two most probable sums 7, 8.
Sum = 5: There is 1 pattern (1, 2, 1, 1).
Sum = 6: There are 2 patterns (1, 2, 1, 2), (1, 2, 2, 1).
Sum = 7: There are 3 patterns (1, 2, 1, 3), (1, 2, 2, 2), (1, 2, 3, 1).
Sum = 8: There are 3 patterns (1, 2, 1, 4), (1, 2, 2, 3), (1, 2, 3, 2).
Sum = 9: There are 2 patterns (1, 2, 2, 4), (1, 2, 3, 3).
Sum = 10: There is 1 pattern (1, 2, 3, 4).

The second hint of the second sample input is wrong, because the sum of two-sided and three-sided dice cannot be 6.

Facebook Hacker Cup 2012 Round 1 3問目 - Squished Status (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Round 1 3問目

問題概要

数字のみからなる1000文字以下の文字列と,正整数M (255以下) が与えられる.
文字列を,1以上M以下の数字の連続とみなすとき,何通りの区切り方があるか,mod 4207849484 で求める問題.
数字はleading zerosは許されない.

解法

今何文字目まで見たかを状態にしてDPする.
modの値が微妙に大きいので64bit整数とかで扱わないと厳しい.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2012 Round 1 2問目 - Recover the Sequence (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Round 1 2問目

問題概要

とある1~N (Nは10000以下) のpermutation配列に対して,問題文中にあるマージソートのプログラムを動かした.
そのプログラムは,比較する際,どっちが大きいかで,1か2を出力している.
Nと出力結果だけが与えられた時,元々の置換を求める問題.

解法

1~Nが順番に並んでいる配列を,問題文と同じようにマージソートする.
その際,出力結果をみて,それと同じように大小関係を決める.
後は,そうやって得られた配列の対応関係を逆にすれば良い.(ソート結果がa[i] = kなら,b[k] = iにして,bが答え)

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2012 Round 1 1問目 - Checkpoint (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Round 1 1問目

問題概要

碁盤の目の道路がある.(格子点だけ考え,マンハッタン距離が1の点の間に道がある)
スタートからゴールまで,チェックポイントを経由して,最短路で移動しなければいけない.
チェックポイントは,スタートともゴールとも異なる.
最短路での移動方法の数S (10000000以下) が与えられた時,スタートとゴールのマンハッタン距離の最小値を求める問題.

解法

x1+y1およびx2+y2は正として,
 C(x1+y1, x1) * C(x2+y2, x2) = S
となる最小のx1+y1+x2+y2を求める問題になる.
コンビネーションが10^7を超えないものを最初に列挙して,すべてのkに対し,C(x1+y1, x1) = kなる最小のx1+y1を求めておく.
後は,Sを2つの積に分割する方法を全部試す.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2012 Qualification Round 3問目 - Alphabet Soup (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Qualification Round 3問目

問題概要

アルファベット大文字,半角スペースのみからなる文字列が与えられる.文字列の長さは1000以下.
その中に含まれる文字を自由に切り取って使って,HACKERCUPという文字列は最大で何個できるかを求める問題.

解法

 文字列に含まれるHの数,文字列に含まれるAの数,文字列に含まれるCの数/2,文字列に含まれるKの数,…,文字列に含まれるPの数
の最小値が答え.
HACKERCUPにはCが2回出てくるので,Cに関してだけ2で割るのを忘れないように.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2012 Qualification Round 1問目 - Billboards (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Qualification Round 1問目

問題概要

幅W,高さHの板に文字を書く.幅と高さはそれぞれ1000以下.
書く文字は与えられて,単語と単語の間は,スペースを入れるか改行する.文字数はスペースも入れて1000以下.
フォントサイズ(整数)を決めたら,全ての文字とスペースは,それぞれ高さと幅が両方共そのフォントサイズになる.
その板に書ききれる最大のフォントサイズを求める問題.
フォントサイズが1でもダメなら0を返す.
幅12の板にフォントサイズ4の文字を3文字書くことはできるが,幅11には無理.

解法

愚直にフォントサイズを1から順番に,書ききれるかどうか調べれば良い.(もちろん二分探索しても良い)
どこで改行するかはgreedyに,次にくる単語がこの行に書き切れないときに改行すれば良い.
一行に収まらない単語があるときなどはダメなことに注意.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Round 2 3問目 - Bonus Assignments (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 2 3問目
Facebook Hacker Cup 2011 Round 2の参加記録

問題概要

N個 (1000000以下) の自然数a1, a2, ..., aNのうち以下の条件をみたすものはいくつあるかをmod 1000000007で求める問題.
 a1~aNはすべてがKの倍数になっている,というような2以上のKが存在してはいけない
 a1~aNの最小値はA以上B以下
 a1~aNの最大値はC以上D以下
A,B,C,Dは1000000以下.

解法

包除原理を使いまくる.
2つ目の3つ目の条件は
 全部A以上D以下で条件1を満たすもの数 - 全部A以上C未満で条件1を満たすもの数 - 全部Bより大きくD以下で条件1を満たすもの数 + 全部Bより大きくC未満で条件1を満たすもの数
という感じに全員が一定範囲の場合に帰着させる.
1つ目の条件は
 全員が1の倍数 - 全員が2の倍数 - 全員が3の倍数 - 全員が5の倍数 + 全員が6の倍数 - …
という風な包除原理を用いる.
メビウス関数あたりも参照.
 Σメビウス(k) 全員がkの倍数の数

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Round 2 (参加記録) (この記事を編集する[管理者用])

2011年02月06日06時から3時間,3問.
2回戦は上位25人が通過,オンサイト決勝に進出.上位300人にTシャツ.
[Problems] [Score board]

1問目 - Scott's New Trick

要素数N (10^7以下) の数列aと要素数M (10^7以下) の数列bが与えられる.
a[i] * b[i] mod P が K 以下となるよう(i,j)の組が何通りあるかを求める問題.
Pは250000以下,KはP未満.
(数列は実際には乱数生成のパラメータが与えられる)

それぞれの数列の要素がそれぞれmod Pで何個あるか覚えてやるだけ.
と思ったけど普通にやったらO(N+M+P^2)でP^2がでかくて駄目だ….
えーっと,どうするんだろう….
3問目やって,2問目にはまってたので,何もできず.

2問目 - Studious Student II

60文字以下のa,bのみからなる文字列が与えられる.
以下の操作を何回でも繰り返して良い.
 ある部分文字列を,その部分文字列に含まれている1文字で置き換える
操作の適用方法は何通りあるか,mod 1000000007で求める問題.

うーん,どうやるんだろう.
あんまり生成される文字列の種類って無いんじゃないのかな?
単純に現在の文字列をメモしてDPしてみる.
….
長さ20ぐらいですでに全然終わらない.
良く考えてみると,作れる文字列の種類数めちゃくちゃ多いなぁ….
うーんうーん.
DPだとは思うんだけど….
カッコをつけて,それを中にある1文字で置き換える.
実際には内側から処理していくけど,外側からやっていけばいいのでは!
でも,内側の適用結果によっては置き換えられる文字が変わってしまう….
内側に含まれる文字の種類も全部状態に含めればいいのでは!
状態数は…,左端,右端,内側に含まれる文字の種類で,60*60*4ぐらい.
いけそう.
違う!
えっと,カッコは内側から適用しないといけないけど,それ以外は順番が任意だからそれの分をかけないといけない….
でも,それって求まるか…?
….
ツリーつくって,
 ノード数!/Πそれぞれのノードを根とするサブツリーのノード数
あたりをかけたい….
使うカッコの個数も状態に含めればいけるか.
とりあえず,遅いかもしれないけど書いてみよう.
書いた.
状態数は左端,右端,括弧の数,全体をくくるカッコを許すかどうか,内側に含まれる文字の種類,で60*60*60*2*4.
で,更新するのは,次のカッコの左端と右端,括弧の数をどのように配分するかで60*60*60.
合計O(60^6*たくさん).
当然のごとく終わらない….
次のカッコの左端とか考えなくていいじゃん!左端を1つシフトするだけでいいじゃん!
合計O(60^5*たくさん).
….
まだ厳しい.
60文字1ケースに1分以上かかる.
しかし,残り時間わずか.
インプット落としてきて,4つに分割して,4つプログラム動かして手動並列!
落とした.長さ60のケースが17個もある…無理だ….
結局6分以内に実行終わらず12分ぐらいかかった….
O(60^5)で通している人もいるし,ボロいPCだった人は通せなかったりしたらしい.
しかし,自分のPCはそんなにボロくないので,プログラムがかなり定数倍遅かったと思う.

3問目 - Bonus Assignments

N個 (1000000以下) の自然数a1, a2, ..., aNのうち以下の条件をみたすものはいくつあるかをmod 1000000007で求める問題.
 a1~aNはすべてがKの倍数になっている,というような2以上のKが存在してはいけない
 a1~aNの最小値はA以上B以下
 a1~aNの最大値はC以上D以下
A,B,C,Dは1000000以下.

最初問題を読み間違えて意味がわからなかった.
ふむふむ.意味がわかった.
どうするんだろう….
包除原理で行けるんじゃない?
 すべて - 2の倍数 - 3の倍数 - 5の倍数 + 6の倍数 - …
いけそう.
そして,最小値がA以上B以下とかそれも包除原理で行ける.
書こう.
サンプル通った.
サブミット.

結果

難しかった.結局3問目しか解けず敗退.
そもそも1問以上解いた人が150人しかいなかったためTシャツはゲット.

Facebook Hacker Cup 2011 Round 1A 3問目 - Turn on the Lights (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A 3問目
Facebook Hacker Cup 2011 Round 1Aの参加記録

問題概要

R*C (18*18以下) のグリッドが与えられる.
各セルは.かXの文字が書かれている.
毎ターン1セル選んで,そのセルと,その上下左右のセル (あれば) の状態を反転させる.
すべてのセルをXにするのに必要な最小ターン数を求める問題.
不可能ならばそれを指摘する.

解法

1行目だけ全探索する.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Round 1A 1問目 - Wine Tasting (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A 1問目
Facebook Hacker Cup 2011 Round 1Aの参加記録

問題概要

G次 (100以下) 対称群の元のうち,s(i) = iを満たさない個数がC個以下のものの数をmod 1051962371で求める問題.

解法

dp[使った数][相方がいなくなった数字の数][まだ間違えて良い個数]とかでDPした.(以下のコード)
後は,1つもs(i) = iが一致しない場合の数についての漸化式を立てて,コンビネーションと組み合わせて計算することができる.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Round 1A (参加記録) (この記事を編集する[管理者用])

2011年01月22日03時から3時間,3問.
1回戦は3ラウンドのうち,それぞれ上位1000人が通過.
[Problems] [Score board]

1問目 - Wine Tasting

G次 (100以下) 対称群の元のうち,s(i) = iを満たさない個数がC個以下のものの数をmod 1051962371で求める問題.

うーん,なんか見覚えがある.
なんかいい方法なかったっけなぁ….なんか規則性とかあった気がする.
小さいケースで全探索してみる.
規則性わからない.
もういいやDP書こう….
dp[使った数][相方がいなくなった数字の数][まだ間違えて良い個数]とかでメモ化すればOK.
書き書き.
微妙に合わない….
あれぇ….
微修正であった.サブミット.

2問目 - Diversity Number

ある数列t[k]のdiversity numberとは,
 0 <= b[k] < t[k],かつ,b[k]は全て異なる
を満たす数列b[k]の個数.
長さ100以下,各要素100以下の数列a[k]が与えられるので,その部分列で,
最初は単調非減少,残りは単調非増加となるような数列のdiversity numberの和をmod 1000000007で求める問題.
部分列は,長さが違うか,同じ場所なのに違う値になるものが存在したら違うものとみなす.

どう見てもDPなんだが….
どうやれば良いのだろうか….
まず,diversity numberを計算するのは,どうするの?
a[k]をソートしてa[k]-kをかけていくだけか….
てか,それはTopCoderで見た気がするなぁ.
じゃあ,どうするの?
小さい方から処理していきたいから,両端から処理して行こう.
同じ値の処理が面倒….
しかも,重複して数えたらいけないのか!
えーっと,結構難しくないか….
とりあえず,書いた.
答え合わない.
うーむ.デバッグ.デバッグ.時間切れ.

3問目 - Turn on the Lights

R*C (18*18以下) のグリッドが与えられる.
各セルは.かXの文字が書かれている.
毎ターン1セル選んで,そのセルと,その上下左右のセル (あれば) の状態を反転させる.
すべてのセルをXにするのに必要な最小ターン数を求める問題.
不可能ならばそれを指摘する.

自分,これのライブラリ昔作ったぞ….
貼りつけ,サンプル通る.提出.
思いの外,実行に時間かかったけど問題ない.
ビット演算を駆使すれば早くなるが….
サイズが大きくなると,連立方程式に落として解くべきなのか….

結果

1問目と3問目は問題なく通った.
1問以上解けた人数が1000人もいなかったため問題なく通過.
無効試合になったRound 1Aと比べるととても難しくなった.
後,3問目のジャッジの答えが間違えてたのか,一部正しく判定されなくて,その後修正された.

Facebook Hacker Cup 2011 Round 1A [無効試合] 3問目 - First or Last (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A [無効試合] 3問目
Facebook Hacker Cup 2011 Round 1A [無効試合]の参加記録

問題概要

R人でレースを行う.最初自分は最下位.
T箇所だけ,コーナーがあって,各場所について
 今の順位を維持するなら 1/p[k] の確率でクラッシュする
 1人だけ抜くなら 1/q[k] の確率でクラッシュする
という確率が与えられる.
クラッシュせずにR-1人抜く確率の最大値を有理数で厳密に求める問題.
Tは50以下,p[k],q[k]は500以下.

解法

多倍長の有理数が必要な問題.
greedyにp[k]/q[k]の値が小さい方から抜くことにする.
以下のコードは無駄にDPしているコード.

C言語のスパゲッティなコード (not verified)

続きを読む

Facebook Hacker Cup 2011 Round 1A [無効試合] 2問目 - Power Overwhelming (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A [無効試合] 2問目 (問題削除済み)
Facebook Hacker Cup 2011 Round 1A [無効試合]の参加記録

問題概要

整数A, B (1以上100以下) とC (A+B以上10^12以下) が与えられる.
正整数x, yをxA + yBがC以下という制約のもとでxyを最大化するものとする.
ただし,答えが複数あるならxを最大化する.
xを求める問題.

解法

xとyが実数全体なら二次方程式の最大値なので解析的に求まる.
A, Bが小さいので,その周辺を調べれば良い.
xyの最大値が64bit整数に収まらないので注意.(多倍長が必要)
以下のコードでは,解析的にやらず,整数のまま三分探索しているのでかなり怪しい.

C言語のスパゲッティなコード (not verified)

続きを読む

Facebook Hacker Cup 2011 Round 1A [無効試合] 1問目 - After the Dance Battle (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A [無効試合] 1問目
Facebook Hacker Cup 2011 Round 1A [無効試合]の参加記録

問題概要

100*100以下のグリッドが与えられる.
スタート地点,ゴール地点が1箇所ずつ与えられるので,スタートからゴールまでのステップ数の最小値を求める問題.
グリッドは壁(入れない)か空白(0)か色がぬられている(1--9).
1ステップでできる行動は上下左右に移動するか,同じ色の他のセルにワープすることができる.

解法

BFSするだけ.

C言語のスパゲッティなコード (not verified)

続きを読む

Facebook Hacker Cup 2011 Round 1A [無効試合] (参加記録) (この記事を編集する[管理者用])

2011年01月16日00時から3時間(の予定だった),3問.
1回戦は3ラウンドのうち,それぞれ上位1000人が通過.
[Problems] [Score board]

はじめに・・・

サブミットしようとしてもサーバーが応答せずサブミットできない現象が起きたのと,
2問目のサンプルが間違えている,3問目のサンプルが入力の制約を満たしていない,などという問題があり,何故か早めに終了.
現在結果も明らかにならず,2問目は削除されている様子.
Round 1は1週間以上は延期するとのこと.

1問目 - After the Dance Battle

100*100以下のグリッドが与えられる.
スタート地点,ゴール地点が1箇所ずつ与えられるので,スタートからゴールまでのステップ数の最小値を求める問題.
グリッドは壁(入れない)か空白(0)か色がぬられている(1--9).
1ステップでできる行動は上下左右に移動するか,同じ色の他のセルにワープすることができる.

問題文が読みにくい.
入力から読む.入力と出力だけ読めば意味がわかるじゃん….
単にBFSするだけだ.
最悪ケースは,全部のマスが同じ色の場合だけど,10000^2程度なのでなんとかなるだろう.
書く.
書いた.サンプル通ったのでサブミット.

2問目 - Power Overwhelming

整数A, B (1以上100以下) とC (A+B以上10^12以下) が与えられる.
正整数x, yをxA + yBがC以下という制約のもとでxyを最大化するものとする.
ただし,答えが複数あるならxを最大化する.
xを求める問題.

三分探索やるだけでいいよね.
…違う!
x,yは整数なんだから,関数はギザギザしてるはず….
まぁ,適当にやればよさそうだが….
てか,待てよ!
Cが10^12ってことは…,xyの最大値が64bitで収まらないんだけど….
…,先に3問目に行こう.
3問目提出して戻ってきた.
twitterなどでは提出できないという噂がチラホラ見える.普通にできたけどなぁ.
多倍長+三分探索して,後はその周辺を調べたらいいんじゃないの?
ってことで書く.
合わない.
問題文ではyの最大値なんだけど,xの最大値を出力してみたらサンプルっぽいのがでてきた.
でも,結構違う….
てか,このサンプル間違ってないか?
なんか,自分の答えのほうがxyでかいんだが….
もういいや,サンプル無視してサブミットしてみよう.
インプットダウンロードして実行.
サブミット…できない.サブミットボタン押しても反応なし.
chrome, firefox, IEで試したけど駄目だった.
そうこうしてる間に6分間過ぎた.
しばらくしたら,6分過ぎてもサブミットしたら受け付けてあげるよ,とのアナウンスが.
ってことで,サブミット…,してもしてもできない.
10分ぐらい粘ったらサブミットできた.
残り1時間残して全部提出したので寝る.

3問目 - First or Last

R人でレースを行う.最初自分は最下位.
T箇所だけ,コーナーがあって,各場所について
 今の順位を維持するなら 1/p[k] の確率でクラッシュする
 1人だけ抜くなら 1/q[k] の確率でクラッシュする
という確率が与えられる.
クラッシュせずにR-1人抜く確率の最大値を有理数で厳密に求める問題.
Tは50以下,p[k],q[k]は500以下.

…多倍長から逃げてきたら,多倍長有理数ときたよ….
問題自体はDPするだけ.(実はgreedyで良いのに気づかない)
多倍長有理数のライブラリを貼りつけて書くか.
書いた.
インプットダウンロードして実行.
….時間かかるなぁ.
1分ぐらいかかった.怖い.
サブミット.

Facebook Hacker Cup 2011 Qualification Round C問題 - Studious Student (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Qualification Round C問題
Facebook Hacker Cup 2011 Qualification Roundの参加記録

問題概要

10文字以下の文字列がN個 (9以下) 与えられる.
それらを繋げてできる文字列のうち辞書順で最小のものを求める問題.

解法

効率良く解く方法もあるのだけど,今回はNが小さいのでN!通り全部試せば良い.

C++言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Qualification Round B問題 - Peg Game (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Qualification Round B問題
Facebook Hacker Cup 2011 Qualification Roundの参加記録

問題概要

ボールを落とす.パチンコみたいに,pegに当たると左下か右下に当確率で移動する.
pegがなければ真下に落ちる.
一番下のある場所に落とす確率を最大化するためには,一番上のどの場所から落とせば良いか,また最大値を求める問題.
グリッドのサイズは100*100ぐらい以下.

解法

DPする.ここからゴールに辿りつける確率を各セルについて覚えておく.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Qualification Round A問題 - Double Squares (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Qualification Round A問題
Facebook Hacker Cup 2011 Qualification Roundの参加記録

問題概要

0以上2^31未満の整数Xが与えられるので,2つの非負整数の平方数の和で書く方法のパターンの数を求める問題.
10=1^2+3^2=3^2+1^2と順番を入れ替えたものは同一視する.

解法

平方数Yに対してX-Yが平方数かどうかを判定する.

C言語のスパゲッティなコード

続きを読む

Facebook Hacker Cup 2011 Qualification Round (この記事を編集する[管理者用])

2011年01月08日09時から72時間,3問.
予選は1問正解で通過.
[Problems] [Score board]

Facebook Hacker Cupのルール

ソースコードと出力を提出.(予選は出力のみ)
提出はインプットをダウンロード後6分以内にしなければいけない.
合ってるかどうかの判定はコンテスト終了後.
スコアは合ってる問題数,タイブレークに最後に正答を提出した時間の早いほうが上位.
(2011-01-18 15:20追記) タイブレークは最終正答提出時間から,正答提出時間の和に変更された模様.

問題A - Double Squares

0以上2^31未満の整数Xが与えられるので,2つの非負整数の平方数の和で書く方法のパターンの数を求める問題.

とりあえず問題見たけど流石にやるだけ.
(最初なかったのに,後で確認したらテストケースの数の制約が追加されていた)
平方数引いて残りが平方数かどうかチェック!
書く.
FAQを一通り読んでルール確認してからインプットダウンロード.
インプットが2回クリックしないとダウンロード出来ない….
提出しようとしたけど,提出するウインドウが開いたらテキストエリアが一つしか無い….
アウトプットを貼りつけてとりあえず提出.
これ,ちゃんと提出出来てるのか心配だなぁ….
てか,ソースコードはどこから提出するの?
わからない.
取り敢えず,ランクリストは…,上位10人しか表示されないのでよくわからない.
色々ウォール眺めてると,どうやら,予選はソースコードは提出しなくていいという噂が.
でもオフィシャルでそう言ってる記事が見つからない.
なんか色々怪しいので,残り2問は時間を置いて色々情報を集めてからにする.

何時まで経ってもオフィシャルな記事は見えない.
その代わりにTopCoderのForumで中の人が対応しているように見える.
オフィシャルの記事を探すには,TopCoderのForumを見ればいいのか,なるほど.…いや,ぇ.
まぁ,提出しなくても良さそうなので残り2問も解く.

問題B - Peg Game

ボールを落とす.パチンコみたいに,pegに当たると左下か右下に当確率で移動する.
pegがなければ真下に落ちる.
一番下のある場所に落とす確率を最大化するためには,一番上のどの場所から落とせば良いか,また最大値を求める問題.
グリッドのサイズは100*100ぐらい以下.

座標がちょっとめんどいけど.DPでやるだけ.
取り敢えず,図を書いて座標に落とすまで出来てるかチェック.
ん,これ,どこから落とすと最適化は曖昧性をなくすためにテストケースには同じ確率にならないようになっている,って書いてるけど,おなじになるテストケースがサンプルにある.
どういうこと….問題理解間違えてるの?
問題読み直しても間違えてるとは思えない.
取り敢えず,タイがあったら,できるだけ左から落とすようにしてみよう.
書いた.
後,出力の時丸めるのに,0.5を切り落とさないように最後にEPSを足して出力…と.
(と自分はしてたけど,最終的にはクレームが来て,切り捨てても切り上げても正解になったみたい)
サブミット.

問題C - Studious Student

10文字以下の文字列がN個 (9以下) 与えられる.
それらを繋げてできる文字列のうち辞書順で最小のものを求める問題.

UVaで見たことある問題だなぁ….
今回はNが9以下なので全パターン探索でいいや.
書いた.
サブミット. (意外と実行時間かかったなぁ)

Results

取り敢えず,問題なく全部通ったらしい.

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

2010年10月24日13時から3時間,6問.(夜の部は22時から3時間)
[ Link ] [ 夜の部 ]

全然できなかった.難しい.3問解いた.
以下問題別.

・問題A
最初は問題の意味がわからなかった.
意味をなんとなく理解してから適当に書く.
図が2倍2倍にとんがっていくのはすぐわかった.てか見たことある関数.
ってことで書く.
q=0ってどうなるんだ….適当にn=1,t=100とかにしとけばいいか.
いや,nの最小値って1でいいのか?問題文の定義の仕方だとn=0は定義されてないから1で良い気がする.
送る.Accept.
後で気づいたけど,入力が2^n+1の時って答え間違える(-1を返す)んだけど,まぁ,通ってるので触らないことにしておく.
・問題B
どうみても,根から高さを求めるだけ.
トポロジカルソートみたいに書く.
トポロジカルソート知らないとか情報系失格とか聞いたけど,普通にそんなの知ったのごく最近ですよ….
まぁ,これは普通にAccept.
・問題C
うーん,サイズ的にDPだと間に合わない.
紙に書いて適当にやると普通にgreedyで良さそう.
これって答えないことあるのか?なさそうなんだけど….うん,多分ない.
スタックに使われてないのを積んで,スタックに入ってるのと違う色と出くわしたら結ぶ.そうでなければ積む.
Accept.
・問題D
縦横mod dで分けて考えると,毎回,ある区間だけ同じ数字を減らしていくことになる.
2d Fenwick Treeでも使えばできるのかなーと思ったけど結局分からず.
・問題Eと問題F
ほとんど考えてない.

Maximum-Cup 2010 (参加記録) (この記事を編集する[管理者用])

2010年10月02日13時から4時間30分,10問.
[ Link ]

いつものようにトラップだらけのコンテスト.
なんで間違っているのかがわからない.
CとH以外を通した.
以下問題別.

・問題A
やるだけ.トラップの問題なのにトラップがないとかトラップすぎる.
・問題B
連立一次方程式を解くだけ.
rngさんのケースがやばいけど,judgeは親切.行列式は0じゃないものだけ.
・問題C
そのpropertyを使うかどうか2^20通り全探索するだけのように見える.
(使うのであれば,IsにするかNotにするか定まる.どっちでもいいならその条件を使う意味はないから使わない)
しかしWAで通らない.
辞書順とか,1個は条件を指定しないといけないとかは考慮してるはずなんだけどなぁ.
・問題D
ワーシャルフロイドとかするだけ.オーナーさんを忘れるな.
・問題E
DPするだけだけど,微妙にタイムリミットが厳しかった.ギリギリだけど通った.
・問題F
重なってもいいとして全置き方 - 重なる置き方 をコンビネーション用いて計算するだけ.多倍長.
・問題G
2分探索.
・問題H
どの敵を倒したか,今どこにいるかでダイクストラした.
なぜか通らない.
ちゃんと,立ち止まったとき,周りの敵はすべて薙払うし,スタート地点からなぎ払うのにコストは必要ないのは考慮してるが….
・問題I
実装問題.やるだけ.国内予選で似たようなのやったような.
・問題J
よくある編集距離っぽいDPと経路復元.

東京大学プログラミングコンテスト2010 (UTCP2010) (この記事を編集する[管理者用])

2010年07月04日12時から5時間,12問.
[UTPC2010 HP] [standing] [M-judge (problems)]

去年も参加させていただいたのですが,そのときは全く解けなかったのでリベンジ戦.(去年の記事)
10問正解で,リベンジ成功したみたいです.
提出して通ったコード一覧は,全部最後に付けておきます.
以下は問題別.

A. 期末試験!

けいおん!
やるだけ.
最速サブミットを目指したけど,全然遅かった.
問題文開くのが遅かったよ,1分ぐらいかかった気がするよ,とか宣ってみる….
取り敢えず,Accept.

B. 宝くじチェッカー

やるだけ.
intでオーバーフローするかどうか判断するのが面倒だったのでlong longにしておいた.
変数名間違えて4分ぐらい嵌った気がする.
いきなりの絶望感.
取り敢えず,Accept.

C. コンパイル

ぷよぷよ.コンパイルってそういう事か.
シミュレーション書くだけ.DFSを多用する.
Bで遅れた分は,これの実装速度で多少は巻き返したみたいなのかな?
これも,縦横のサイズ間違えたり,バグって遅れた.
取り敢えず,これも,Accept.

D. 無矛盾な単位系

グラフ作って,ワーシャルフロイドするときに,矛盾を発見したらその場でNoを返すようにしてみた.
あっさりAccept.

E. トーマス・ライトの憂鬱

ロックマンのパスワード…だったらしい.
2行2列で,全ての行,列が全部1ならそれだけで複数あるので,決まるところから決めていって,全部決まらないならNoでいいんじゃない?
ソートして前と後ろから眺めてgreedyに処理していく.Accept.

F. UTF-8

単なるDP.
それなりにサクっと書けたのに,バグにはまる.
ケアレスミス×2で,WA3回.そののちAccept.

G. 天体観測

星空のメモリア.
グーグル先生に回転行列教えてーって頼んで,後は,回して回して回して,z座標が全部正かどうか調べた.
1発コンパイルでAccept.

H. 迷い猫、走った

迷い猫オーバーラン.
単純なDPじゃないか…,と思ったらO(1000^3)になる.
うーん,わからんぞ?
二分探索+Greedyっぽい…と思ったら上手くいかない.
二分探索+DPか…?
何を状態にして,何を求めるのか,よく分からない.
そんなに答えは変なのにならなさそうなので,O(n^3)のDPで,枝刈りすればいけるんじゃない?
まぁ,O(1000^3)のDPを書く.
枝刈り面倒になったので,嘘っぽい枝刈りを追加して,送信してみる.
1発Accept…,ぇ.

I. 盗まれた宝石

今までの移動パターンが,どの禁止パターンの何文字目まで一致しているか,という情報を付与してBFSというよくある問題.
ただし,ちょっと実装が面倒.
最初に,マッチング情報から,どの方向に移動すると,どういうマッチング状況になるかのグラフを作る.がりがり.
で,普通にBFSする.がりがり.
サンプル合わない….
おっと,文字と方向が一致してなかった….
1個だけサンプル合わない.
禁止パターンがない場合に死んでる!
これ,サンプル親切すぎるだろう…,これないと面白かったのに,自分は苦しんでた.
サブミット.Accept.

J. 多項式の解の個数

解法がまったく想像できない.
1個ずつ解見つけて割っていくのかな…?
解の候補が絞られたらいいのだけど….
剰余取らないバージョンなら,±最低次の係数の約数/最高次の係数の約数 とかに絞られる気がする.
そんなの成り立たないよな…,一応書いてみる….
成り立たない.
そもそも割れない?
わからない.
諦める.
Ustreamで聞いてた解説の雰囲気から,無理ゲーだということはよくわかった.
まぁ,流石のきたまさ君だし….

K. ワープホール

うーん?
座標圧縮してDP?
いや,上手くいかない…,ある場所からある場所へ移動するときの組み合わせの数をうまく計算できない.
うーん?
座標圧縮なんてしなくていいから,各場所に行くまでの経路の数を覚えておけば,適当に包除原理っぽいことで計算できる.
書こう.
微妙に合わない….
あ,これだと重複してカウントしてる,修正.
答え合う.
サブミット.WA.
うー.
あ,ワープホールの出口が,ワープホールの一口に飛ぶ場合怪しい.
テストケース作る.本質的に同じケースのはずが答え違う.
修正.
サブミット.Accept.

L. 3つのシルエット

とても面倒な3次元幾何だと思う.
でも,どうするのかわからない.
捨てる.
解説聞くと,三角形分割して凸にした後,3次元の凸包カット使うみたい.

続きを読む

天下一プログラマーコンテスト2009 (この記事を編集する[管理者用])

こっそり参加していました.
最初に思ってたより参加者の層が厚かったみたいで,それに合わせて問題の難易度も途中で調整されたらしく,結果的に普通に難しいコンテストだったと思います.
探索問題・実装問題が多くて,どのように枝を刈るべきか,どう実装すれば簡潔に実装できるか,など本当の意味でセンスが問われる問題たちだったと思います.
逆にアルゴリズムについての知識などは,あまり問われないので,こういう類のコンテストに慣れていない人にも優しいコンテストであったと思います.
問題はそのうちここあたりにでるんじゃないかなと思う.

予選1回目 (2009年07月05日00時から24時間,3問)

問題1
ある区間の中に日曜日が何回あるかをカウントする問題.
1日ずつインクリメントしながらループ回してもOKだし,適当に中身に含まれる日を数えて7で割ってごにょごにょするとか.

問題2
数字からなる文字列を連続する4文字切りだしてきて3の倍数になるものの数をカウントする問題.
実際に切り出して数えてみる.

問題3
日本の硬貨,紙幣を使用して10000円になる組み合わせの数を求める問題.
典型的DP.なんとループで回しても結構現実的な計算時間で終わるらしい.答えは32bitには収まらない.

予選2回目 (2009年07月15日00時から24時間,3問)

問題1
都道府県の名前でしりとりしたとき,カタカナでの文字の長さ最長のしりとりを求める問題.
DFSで実際に全部列挙してみる.

問題2
20以下の素数を全部使う必要はないが,左から小さいものから用いて,等式を作る作り方をカウントする問題.
各素数は高々1回しか使えない.
括弧と四則演算が使用可能.等号は1つのみ使用可能.
DPで解いた人が多いみたい.たぶん全探索でも可能.
というか,作れる数字の種類が多いのでDPするメリットが計れない気がしたので,メモリの問題もあるし全探索してみた.
そしたら僕はミスった.

問題3
ちくちくばんばんみたいなタイルがあるので,指定の場所を繋げるまでの最低ステップ数を求める問題.
おそらくiterative deepening.

予選3回目 (2009年07月25日00時から24時間,3問)

問題1
n=1000000までの自然数を17進数で表した時,Gの登場回数をカウントする問題.
桁ごとに適当に17^kで割ったり余りを調べればO(log n)で解けるけど,
まぁループで回しながら全部の17進数表現を求めても大丈夫.

問題2
2次元のn*nのグリッド上に文字が書かれている.(n=100)
最長の2次元回文を求める問題.2次元回文は正方形の枠の部分を適当な順番で読めば回文になるもの.最初のマスは2回読む.
全探索でO(n^5)だけど,ランダムに書かれてて回文の判定はほとんど一瞬で回文にならないことが判定されてしまうので実質O(n^4)程度の時間で求まる.
ちょっと枝刈りすれば実質O(n^3)ぐらいで求まる.

問題3
2次元パッキング問題.
30*30のマスに,20種類の適当なサイズの長方形を埋め込む問題.
長方形には埋め込んだ時に得られる利益と,縦横のサイズが与えられている.
同じ長方形は1個まで設置可能.勿論重なってはいけない.90度回転して配置してもOK.
どうやら,最初に埋め込む長方形の種類を列挙して,面積が900以下で利益最大のものから,実際に配置できるかどうか探索してみる,
という風にやるとうまくいくらしい.

天下一勝ち抜け戦 (2009年08月01日13時15分から,1問あたり1時間程度)

問題1
障害物のある8クイーン問題.ただし,升目は16*16.どれだけ多くのクイーンを配置できるかを求める問題.
マップの形をうまく利用して枝刈りしなければ全探索は厳しかったみたい.
具体的には,右の方から縦に見ていくと枝が刈れて良い感じ.
他の方法は,メモリと相談しながら,後半部分だけメモ化してみて高速化を図るとか.
厳密性は保証できないけど,その他に答えを出すには,
 ニューラルネットワークで,各マスのクイーン置いてほしい度を更新していってみる方法
 分子限定法で探索して途中で解が更新されにくくなったらリスタートする方法(分子限定法にランダム要素を入れておく)
 グリーディーに置けば実は最適解が求まる!
とかできるらしい.

問題2
ナンクロを解く問題.
長い単語から決めつけて探索していけば終わる.
勿論一番難しいのは画像から入力を取る部分である.

問題3
素因数分解するとブレインなんちゃらっぽい言語で書かれたコードが得られる.
それの実行結果を求める問題.
書くだけの実装問題.

天下一決勝戦 (2009年08月02日10時15分から,1時間程度)
エレベータースケジュール問題.
乗る人が来るタイミング,来る階,行きたい階が与えられるので,それぞれの人の所要時間(エレベーターを降りる時間-到着時間)の和を最小化する問題.
エレベーターは1回止まると最低10秒は扉を開けておかなければいけない.1階移動するのに1秒かかる.
人の数が少なく,大して枝刈りしなくても答えはすぐに出る.
ということで,実装問題.

The 2nd Imos Contest (参加記録) (この記事を編集する[管理者用])

2009年06月13日12時30分から3時間,6問.
[ Link ]

F. RSA Crack
全体的に適当に問題文を眺める.
Fって,ごちゃごちゃ書いているけど,素因数分解するだけの問題.(ちゃんと読んではいない)
ただし,数字が大きいので,色々制約を使って数学しないといけないのかな…?
まー,素因数分解なら,ライブラリコピペで通るだろ.
通った.
ライブラリの内容は,問題文からリンク張られているwikipediaに書いてあるPollard's rho algorithm.
絶対想定解法ではないよな…,ごめんなさい.

A. Cards
他の問題は眺めただけじゃ理解できないので普通にAからやろう.
1から始まる等差数列の1つだけ項を除いて,ランダムにシャッフルして入力される.
除かれた項を求める問題.
入力は3つ以上の項がある.
ソートして,1が無ければ1を返す.
そうでなければ,2項の差をとっていって,その最小値が公差.
で,抜けているのを探すだけ.
Accept.

B. Imos Day
インプットだけ読んで,後は図で補完して問題を理解.
要するに,枝に長さがある木が与えられるので,最も遠いノード間の距離を求める問題.
2回DFSするだけ.Accept.

C. Lucky Time
与えられた数字が24時間表記(000000から235959)のデジタル時計の部分文字列として1日に何回現れるかを求める問題.
ケースごとに探索してTLEをもらう.
最初に全ケース計算してAccept.

F. RSA Crack (Rejudge予告)
なんか,皆普通にF通してるから凄いなーと思ってたらrejudge予告来た.
落とされるー,怖いよ,怖いよ.
まあ,取り敢えずDへ.

D. Hailstones
問題の意味がわからない.
サンプルが合わない.
悩む.悩む.取り敢えずEも読んでみる.

E. Corn
めんどくさいタイプのsegment tree問題にしか見えない.

D. Hailstones
適当に書いてみる.合わない.

F. RSA Crack (Rejudge)
いつの間にかrejudgeされていた.
結構落とされてる.けど,自分は落ちてない.良かったー.
タイムリミット20秒から4秒にされたけど160msぐらいでAcceptされてる.
rejudge前は50msぐらいで通ってたのでテストケースも増えた(?)っぽい.

D. Hailstones
サンプル出てきた.
問題が解釈できなかったのは,サンプルを手で解けなかったのが痛い.
ノードを2520(=lcm(1,2,...,10))倍してBFSすればよい.
配列の容量を間違えたり,解釈間違えてたときの枝刈り消し忘れたりで3回WAやらREくらっちゃったけどAccept.

E. Corn
segment tree書きたくないし,問題サイズ大きくないので,適当にブロックに分けて書いてみる.
送る.TLE.
小手先の最適化して送る.TLE.
手元で最大ケースを10個ランダムに作って走らせる.
2.5秒.タイムリミットは3秒.かなり絶妙.

放棄
残り1時間近く残っているけど,放棄してこの記事を書いている.

東京大学プログラミングコンテスト2009 (UTCP2009) (参加記録) (この記事を編集する[管理者用])

2009年06月07日12時から5時間,12問.
[UTCP2009 HP]

見た瞬間解法思いつくような問題を除いて1問も解けなかった.
流石に不甲斐なさすぎる.
でも,面白い問題だったと思う.

準備
日曜日に昼の12時に起きるとか無理ゲーだと思ったけどなんとかなった.
起床後BGMの準備.久しぶりにBGMを変えよう.
ULTIMATE DIAMONDとDon't say lasyを重複登録した後,
yozuca*のbest2つやらゆいにゃんのJOKERやらG線魔王サントラやらRabbit syndromeやらevery struggleやら
その他色々怪しいのを登録してランダム再生で準備完了.

L. シャノワール
フローかと一瞬思ったけどよくわからない.パス.

K. Cat Numbers!
数学っぽい.取り敢えずパス.

J. ねこ泥棒と金曜日のお屋敷
幾何+TSPをDPで解けそう.
しかし,TLEが恐ろしいのと幾何面倒なので後回し.

I. 夏への扉
図が嫌な感じだったので読まずに次.

H. あみだくじ
縦線も横線も多い.segment treeとかが一瞬よぎったけど,取り敢えずよくわかんない.

G. 挨拶の多い本屋さん
これは書くだけ?
適当に,2n回以上猫が鳴いたら止まらないとかで良い気がするし.
取り敢えず,書く.
インデックス間違えたりして手間取る.
送る.
Accept.

F. 天使の階段
DPにしか見えない.
と思って書きだしてから,nもmも50000ってことに気づく.
わかんない….

J. ねこ泥棒と金曜日のお屋敷
TSP書き始める.
しかし,猫捕まえたときの位置が固定ではないのでTSPでは駄目なんじゃ…とか思い出す.
いやいや,猫の方が遅いのでそれで良いはず….
でも,なんか疑心暗鬼にとらわれ始めたので,そろそろAから解いてみる.
AからEまでの解いた順番は覚えてない.

A. ねこかわいがり
雑魚.Accept.

B. 平安京ウォーキング
雑魚.Accept.

C. カードゲーム
雑魚.Accept.

D. 単位変換器
めんどいけど頑張った.Accept.

E. 足し算ゲーム
雑魚.Accept.

J. ねこ泥棒と金曜日のお屋敷
TSP書き終わる.
答えが出ない.
というか,そもそもサンプルおかしい.
秒速80メートルで高々10000メートルぐらい先の猫捕まえて返るのに3時間かかるとか意味分かんない.
座標の単位が書いてない…clar送る.

返ってきた.座標の単位はメートルで良いとか返ってきた.サンプル意味不明.
なんか座標の単位を60メートルにしたら答えっぽいのが出てきた.
けど,なんか秒の小数点以下が少し狂ってる….
取り敢えず,送ってみる.TLE.
色々幾何的な計算するとき2分探索してるのが拙いっぽい.

F. 天使の階段
これは解けている人が少しいる.
取り敢えず枝刈りしながらO(mn)のDP送る.TLE.

わかんない.

H. あみだくじ
要するに,当たりの糸からの距離みたいなものを出せばよい.
隣り合っているものはその時点で距離1になる.
グラフ作ってBFS…でもグラフがでかすぎる.
いや,スワップしたときだけ枝が追加されるのでそんなことはない.
書いてみる.WA.
ってか,枝の順番が重要,グラフ作って最後にBFS一発ではいけない.
しかし,途中で距離を更新していくと,距離が伝搬して結局O(mn)になるような気が….
送ってみる.もちろんTLE.

J. ねこ泥棒と金曜日のお屋敷
clar来た.秒速じゃなくて分速みたい.
座標の大きさ直して,分速にしてみた.
おんなじ計算のはずが,誤差が増えた.
これは2分探索なんかせずに厳密に計算しないと精度もつらい.

K. Cat Numbers!
一応式書いてごちゃごちゃ弄ってみる.
多倍長が必要な式から抜け出せない.
そもそも片方の数字を全探索する解法しか導けない.

F. 天使の階段
やっぱり解いている人が多いこれを考えるのが妥当なのか?
でも,わからない.

I. 夏への扉
なんかこれも解いている人が多い.問題読む.後40分.
フロー…でもない.てかグラフのサイズ的に無い.
自力で辿り着けるなら0を返す.
そうでなければ,猫は人間と合流して,夏まで自力で辿り着ける場所まで送ってもらえば良い.
 猫の初期位置から猫が自力で移動できるノードの集合S1
 夏から猫が自力で移動できるノードの集合S2
 最初に人間がいるノードからだけなる集合S3
として,各ノードに対して,それぞれの集合からの距離を求めてあげて,それの和の最小値が答えなんじゃないか?
書く.送る.WAる.
終わった.

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通りしかなくて,ギアは無限に使ってよい.
素因数分解して有理数の連立一次方程式に落として,後は頑張って解くだけ.

Maximum-Cup 2008 (この記事を編集する[管理者用])

2008年08月02日14時から,4時間30分,8問.

オープン参加含めて,
1位は6 Accepts.
おそらく,6 Acceptsは3人.
参加人数は28人ぐらい.

僕はオープン参加.

A. Opinion Poll
Sort.

B. Pirates of the Mediterranean: The Curse of the Black Perl
問題文をよく読む問題 + Dijkstra.

C. iDOL M@STER
DP + 経路復元.

D. FAN Mail Analyzer
文字列処理 + 実装問題 + simple DP.

E. Sub Version Network System
謎.
何も考えないと計算時間量 50^2 * 3^50 程度.

F. Maximum Rectangular Window
幾何 + これ(http://algorithms.blog55.fc2.com/blog-entry-132.html).
面倒.

G. TOKOSHI's Roll Cake Cutting Problem
simple DP.

H. Forever...?
謎.
入力m<2^31に対して,自然対数の底をeとして,
 ne - floor(ne)
が最小となるような 1<=n<=m を出力する問題.

LINKは結果出たら追記する,覚えていたら.

(2008/08/04 2:10追記)
E-Hの解説がEmKさん(Judgeのうちの1人)のBlog( http://d.hatena.ne.jp/EmK/20080803 )にあった.
Eは本番中にこれきっと最小カットなんだよね?と思いながらもグラフが書けなかった.
実はおしいところまでいってたのか.
でも,こんなグラフ思いつかない.

Appendix

Recent Articles

ブログ内検索

Ads


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