Entries

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

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

February 2011 Cook-Off 5問目 - Three Way Communications (この記事を編集する[管理者用])

Source

codechef February 2011 Cook-Off 5問目
Problem Statement
codechef February 2011 Cook-Offの参加記録

問題概要

平面上の3点が与えられる.
それぞれの点の間の距離がR以下ならば,それらの2点は繋がっているとみなす.
すべての点の間が(間接的にでも良いので)移動可能かどうかを判定する問題.

解法

やるだけ.

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

続きを読む

February 2011 Cook-Off 4問目 - Integer Sequences (この記事を編集する[管理者用])

Source

codechef February 2011 Cook-Off 4問目
Problem Statement
codechef February 2011 Cook-Offの参加記録

問題概要

nとaとbが与えられる.nは15以下で,aとbは0以上2^n未満のそれぞれ異なる整数.
0~2^n-1が1回ずつ現れる数列で,以下の条件を満たすものを1つ求める問題.(存在しないならそれを指摘する)
 aとbは隣り合っていない (最初と最後も隣り合っているとみなす)
 隣合う2つの整数は,2進数で表したとき,ちょうど1桁のみ違う

解法

基本的にはグレイコード.Wikipedia
最上位のビットを付け加えて,ひっくり返しながらコピーしていくなり,なんなりで作れる.
aとbが隣り合っていないというのは,適当に隣り合わなくなるまでビットの入れ替えを行えば良い.
(勿論,ちゃんと考えるとどう入れ替えれば良いかはわかるし,実装できるが)

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

続きを読む

February 2011 Cook-Off 2問目 - Dance Floor Energy (この記事を編集する[管理者用])

Source

codechef February 2011 Cook-Off 2問目
Problem Statement
codechef February 2011 Cook-Offの参加記録

問題概要

ダンス会場.開いている時間は0~Lまで.(Lは1000000000以下)
合計でB人の男性と,G人の女性が参加する.(BとGは200以下)
それぞれの人は,気になっている異性のリストが与えられており,お互いに気になっている人同士しかダンスできない.
それぞれの人が,会場に到着する時間,会場から出て行く時間が与えられる.
すべての瞬間で,最も多くのペアがダンスを踊っていると仮定して,
 kペアがダンスを踊っていた時間 (k = 0, 1, ..., MIN(B,G))
をすべて求める問題.

解法

それぞれの瞬間で最も多くのペアが何ペアか,というのは最大流で求まる.
後は,人が抜ける,人が追加されるなどグラフを修正しながら最大流を流す.

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

続きを読む

February 2011 Cook-Off 1問目 - Breaking Into Atoms (この記事を編集する[管理者用])

Source

codechef February 2011 Cook-Off 1問目
Problem Statement
codechef February 2011 Cook-Offの参加記録

問題概要

{1, 2, ..., n}の部分集合S[1], S[2], ..., S[m]が与えられる.(nは100以下,mは30以下)
1~nまでの数字を以下の条件を満たすようにk個のグループに分ける.
 任意のxに対して,各グループの要素はS[x]に全部含まれているか,S[x]には全部含まれていないかのどちらかでなければいけない
分けれるような最小のkを求める問題.

解法

AとBを同じグループにできて,BとCを同じグループにできるなら,AとCも同じグループにできる.
なので,同じグループにできるもの同士をgreedyにかためてあげれば良い.

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

続きを読む

February 2011 Cook-Off (この記事を編集する[管理者用])

2011年02月21日01時から2時間30分,5問.
[LINK]

韓国から参戦.
先月と比べると問題が全体的に簡単になった.
難しい問題がなかった.
4問解いて相変わらずの5位.
以下問題別.

・1問目 Breaking Into Atoms
AとBが一緒にできて,BとCが一緒にできるなら,AとCも一緒にできる.
ってことに気づけば,グループに分けてやるだけ.
・2問目 Dance Floor Energy
途中でグラフを修正しながら最大流を流すだけ.
いい加減,最大流で,途中でグラフを修正するライブラリ作っておかないとなぁ….
とりあえず,毎回流し直してTLE.修正するにのバグいれまくって時間かかりすぎた.
・3問目 Icing Crowns (解けてない)
底辺になるの辺を全探索して,後はDPでいけると思う. とりあえず面倒くさい.時間が足りず.
・4問目 Integer Sequences
基本的にはグレイコードで,条件を満たすまでビットをランダムに入れ替え続けた.
・5問目 Three Way Communications
流石にやるだけ.

UVa 11935 - Through the Desert (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11935

問題概要

ある砂漠のコースを完走できる最小の燃料タンクの容積を求める問題.
コースは,スタートからの距離とそこで起こるイベントのリストで与えられる.
車の燃費は途中で変わりうる.(車の燃費が変わるというイベントが起こる)
イベントは以下の通り.
 車の燃費が変わる
 燃料タンクに1箇所穴が増える
 燃料タンクに燃料をいっぱいまで入れる
 燃料タンクの穴を全部直す
 ゴール
燃料タンクに穴があると,距離1だけ走るごとに穴の数だけ燃料を消費する.

解法

実際にシミュレーションして,(最後に燃料タンクをいっぱいにしてから)現在までに使った燃料をそれぞれの地点で求めて,その最大値だけ燃料タンクの容積があれば良い.

UVa 11934 - Magic Formula (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11934

問題概要

a, b, c, d, L が与えられるので,
 f(n) = a*n^2 + b*n + c
として,f(0), f(1), ..., f(L)の中でdで割り切れるものの数を求める問題.
a, b, cは-1000以上1000以下,Lは0以上1000以下,dは2以上1000000以下.

解法

実際に割り切れるかどうか全部確かめる.

UVa 11933 - Splitting Numbers (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11933

問題概要

1以上2^31未満の整数nが与えられる.
 n = a + b
となるように分ける.
ただし,nを2進数で表して,1になってるのを下位ビットから交互にa, bに振り分ける.
aとbを求める問題.

解法

やるだけ.

UVa 11932 - Net Profit (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11932

問題概要

2人でゲームをする.
ノード数N (16以下) の無向グラフが与えられ,それぞれのノードには点数 (-1000以上1000以下) が付けられている.
順番にまだ選択されていないノードを1つ選択して行く.
ノードは,先手の最初はどれでも選択でき,その後は,既に選ばれたノードに隣接するノードのみしか選択できない.
それぞれのプレイヤーの得点は,自分の選択したノードの得点の和となる.
両者が最適にプレイしたときの結果を求める問題.

解法

ビットDPする.

UVa 11931 - Maze Escape (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11931

問題概要

迷路.20*20以下のグリッドが与えられる.壁は通れない.
自分の初期位置,ボタンの位置,箱の初期位置,出口の位置が1個ずつ与えられる.
箱をボタンの上に乗せると出口が通れるようになり,その後出口にたどり着くと外に出られる.
箱を押すと自分と箱が同時に1マス動く.
1ターンで上下左右に動ける.
脱出するための最小ターン数を求める問題.

解法

自分と箱の座標を状態としてBFSするだけ.

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

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11930

問題概要

2次元平面上の長方形がN個 (1000以下) 与えられる.
それぞれの長方形から対角線を1つ選んで,選んだ対角線がすべて交わらないようにできるかどうかを判定する問題.
交わるとは,共通点を1点以上持つこと.

解法

それぞれの対角線が交わるかどうかを判定して2-SATに落として,強連結成分分解して解く.
長方形の頂点の座標が時計回りや反時計回りに与えられてるとは限らない点に注意.

UVa 11928 - The Busy Dog (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11928

問題概要

2次元平面上で,柱の座標と,移動経路が折れ線で与えられる.
移動経路の最初と最後は一致する.移動経路の折れ線の折れる部分の数は10000個以下.
柱の周りを正味何周回ったか(負もあり)を求める問題.
途中で柱に激突しているならそれを指摘する.

解法

柱と移動経路にそって三角形をつくって,柱の部分が作る角度を足していく.
すると,回った回数×2πぐらいになる.

UVa 11927 - Games Are Important (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11927

問題概要

ノード数1000以下,枝数10000以下のDAGが与えられる.
各ノードに1000個以下の石が置かれている.
2人でゲームをする.打つ手がなくなったら負け.
各ターンそれぞれ石を1つ選んで,その石を別の隣接しているノードに移す.

解法

石ごとに独立したゲームに見なせるので,Grundy Numberを計算するだけ.

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

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11926

問題概要

予定が与えられる.
ある種類の予定は,時間[A, B)を占領するもので,
ある種類の予定は,時間[A+kC, B+kC) (k=0,1,2,...) を占領するもの.
各種類の予定はそれぞれ100個以下ずつ.
時間[0, 1000000)で予定が重なっている部分があるかどうかを求める問題.

解法

時間が1000000しかないので,使う部分を塗っていって,既に塗られていたら即座に重なっていると返す.

UVa 11925 - Generating Permutations (この記事を編集する[管理者用])

Source

Alberta Collegiate Programming Contest (ACPC 2010) (2011-02-26) (blog)
UVa 11925

問題概要

1~Nまでの数字の置換が配列で与えられる.(Nは300以下)
その配列を作るための手順を求める問題.
最初は1~Nまでが順番に並んでおり,できる操作は
 操作1 最初の2つの要素を入れ替える
 操作2 最初の要素を最後に回す
操作回数は最小である必要はないが,2*N^2以下でなければならない.

解法

インデックスを付け替えるとソートする問題になる.
ソートされてなければ,適当にぐるぐる回しながら,最初の2項の上下関係が崩れているときに入れ替えると,それで2*N^2は超えない.

Alberta Collegiate Programming Contest (ACPC 2010) (この記事を編集する[管理者用])

2011年02月26日18時から5時間,11問.
[ Link ]

簡単めな問題が多かった.
Aのジャッジがおかしかったみたいで後にリジャッジされた.
E以外の10問解いた.EはAccepted 0.
以下問題別.

・問題A (解いた)
普通に回転しながら反転してたらひっくり返すだけで2*n^2もかからなさそうなのでそれで.
・問題B (解いた)
区間が1000000しかないので,塗りつぶした.
・問題C (解いた)
Grundy Numberを計算するだけ.
・問題D (解いた)
poleと各辺でできる三角形のpoleの部分の角度を足していく方法.
・問題E (解いてない)
とりあえず全探索を書いてみたけど終わるはずもなく.
・問題F (解いた)
嵌りまくった.問題文がシンプルすぎて書かれていないことは何も仮定してはいけない.
自分がはまったのは,長方形の4点が与えられるけど,それが順番が任意であること.
それぞれの長方形の対角線が交わるかどうか判定して2-SATに落とす.
・問題G (解いた)
BFSするだけ.
・問題H (解いた)
よくありそうなビットDP.
・問題I (解いた)
やるだけ.
・問題J (解いた)
やるだけ.
・問題K (解いた)
単純なシミュレーション.

SPOJ 3477 - Baby [BABY] (この記事を編集する[管理者用])

Source

ACM Kanpur 2007
SPOJ 3477 [BABY]

問題概要

N*N (Nは4以上16以下) のチェス盤の2つの盤面が与えられる.
それぞれの盤面にはN個のクイーンが,同じ行,同じ列に高々1個のみ含まれる.
2つ目の盤面はNクイーン問題の解になっている.
さて,1回の手順で,1つのクイーンを上下左右のマスに移動できるとき,1個目の盤面を2個目の盤面に変換するための最小手順数を求める問題.

解法

最小費用流.
問題サイズ的にビットDPでも可能なんだと思う.

SPOJ 402 - Hike on a Graph [HIKE] (この記事を編集する[管理者用])

Source

University of Ulm Local Contest 2000
SPOJ 402 [HIKE]

問題概要

ノード数50以下の無向グラフが与えられる.
全ノード間と,各ノード自分自身との間に枝があり,枝には色が塗られている.
3人の人の初期位置のノードが与えられるので,全員が同じノードに辿りつくまでの最小ステップ数を求める問題.
1ステップでは1人の人が移動でき,その際,移動できる枝の色は,他の2人の位置の間にある枝の色と同じ色しか通れない.

解法

3人がどこにいるか最大50^3の状態数でBFSする.

SPOJ 381 - 106 miles to Chicago [CHICAGO] (この記事を編集する[管理者用])

Source

University of Ulm Local Contest 2005
SPOJ 381 [CHICAGO]

問題概要

ノード数100以下の無向グラフが与えられる.
枝にはその枝を安全に通ることの出来る確率が与えられている.
あるノードからあるノードまで,
1回も危険に晒されずに無事にたどり着くことのできる確率の最大値を求める問題.

解法

ダイクストラ.
各ノードまで安全に行ける確率を求めるとして,確率の最も高いノードから処理していく形.
ノード数が100しかないので,ワーシャルフロイドなどでも可能.

Beta Round #53 C問題 - Array (この記事を編集する[管理者用])

Source

Codeforces Beta Round #53 C問題
Problem description
Beta Round #53の自分の参加記録

問題概要

nが与えられる.(nは100000以下)
要素数nの数列で,各要素1以上n以下で,単調非減少,または単調非増加なものは何通りあるかmod 1000000007で求める問題.

解法

包除原理より,
 単調非減少の数 + 単調非増加の数 - 単調非減少かつ単調非増加の数
となる.
1項目と2項目は等しく,3項目は自明にn個.
1項目は,どこで増やすかを考えると,重複組合せの数に落ち着く.

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

続きを読む

Beta Round #53 B問題 - Martian Architecture (この記事を編集する[管理者用])

Source

Codeforces Beta Round #53 B問題
Problem description
Beta Round #53の自分の参加記録

問題概要

n個 (100000以下) の箱があって,最初は空.
m回 (100000以下) の操作を行う.
 箱番号aにx個石を入れて,箱番号a+1にx+1個石を入れて,…,箱番号bにx+b-a個石を入れる (xは1000以下)
k個 (100個以下) の箱番号が与えられて,その箱に入っている石の数の合計を求める問題.

解法

k個の箱それぞれに何個石が入っているか愚直に計算すれば良い.
前の箱からの増減を覚えておくことで,うまく全部の箱の石の数を求めることもできるが,そこまでする必要もない.

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

続きを読む

Beta Round #53 A問題 - Square Earth? (この記事を編集する[管理者用])

Source

Codeforces Beta Round #53 A問題
Problem description
Beta Round #53の自分の参加記録

問題概要

1辺の長さがn (1000以下) の正方形の周上の2点のx,y座標が与えられる.
周上しか移動できないとして,2点間の距離を求める問題.

解法

どうやってもいいのでやるだけ.
でも,場合分けしまくると,正確に実装できているか不安になる.
以下のコードでは,原点から時計回りの距離を求めて,計算している.
サイズが小さいのでBFSとかやってもいいし,重要な点だけ集めてきてワーシャルフロイドなどしてもいいかもしれない.

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

続きを読む

Beta Round #53 (参加記録) (この記事を編集する[管理者用])

2011年01月26日01時から2時間,5問.codeforcesルール
[ LINK ]

A. Square Earth?

1辺の長さがn (1000以下) の正方形の周上の2点のx,y座標が与えられる.
周上しか移動できないとして,2点間の距離を求める問題.

DQみたいにトーラス世界での距離を求める問題?
いや,サンプル見る限り違うな….
ああ,周上しか移動できないんだ.
書くだけだ.
原点から反時計回りに移動するのにかかる距離に変換して,引いて,周の半分より大きければ周 - 距離に補正…と.
サブミット.

B. Martian Architecture

n個 (100000以下) の箱があって,最初は空.
m回 (100000以下) の操作を行う.
 箱番号aにx個石を入れて,箱番号a+1にx+1個石を入れて,…,箱番号bにx+b-a個石を入れる (xは1000以下)
k個 (100個以下) の箱番号が与えられて,その箱に入っている石の数の合計を求める問題.

うーん,問題が読みにくい.けど,なんとなく理解.
愚直にシミュレーションしたら間に合わないしなぁ….
どうにかやってうまく求めれるはず.
….
あれ?
kが小さいから,選ばれた箱だけ全部計算したら間に合うんじゃ….
書く.間に合いそう.サブミット.
(もちろんうまく計算する方法もあります)

C. Array

nが与えられる.(nは100000以下)
要素数nの数列で,各要素1以上n以下で,単調非減少,または単調非増加なものは何通りあるかmod 1000000007で求める問題.

問題の意味が分からない.
あ,わかった.
えっと,普通にDPやったら,O(n^2)でダメだよなぁ….
とりあえず,包除原理で,単調非減少のもの + 単調非増加なもの - 全部同じ数のもの が答えになる.
から,単調非減少だけ求めればOK.
うーん.普通にコンビネーションで求めれそうだ.
どこで1増やすか,と考えると普通に重複組合せの数だ.
書く.
サンプル合った.サブミット.

D. Journey

n*m (1000*1000以下) のグリッドが与えられる.
ところどころに障害物がある.上下左右に動ける.
障害物のない場所で,ランダムに始点と終点 (始点と終点は同じでも良い) を選んだとき,その2点間の最小距離の平均値を求める問題.
障害物は,各行,各列にはたかだか1個までしかなく,障害物は斜めに接していることはない.

はてさて,そんなに難しくなさそうだが….
単純に始点と終点が同じ行か列に選ばれて,その間に障害物があるときのみ2だけ迂回しないとダメで,ほかはマンハッタン距離でいいのでは.
マンハッタン距離の平均はとりあえず求めておいて損はない.
書く.
行と列に分離して求める.がりがり.
あとは,同じ行に選ばれて,その間に障害物がある確率とか求めて足す.
がりがり.
サンプル通った.
こんなに簡単でいいのか…?
まぁ,自信ないけどサブミット.
最後数分ぐらいでHackされた.するんだったらもう少し早くやってよ!
うーん,考える.
あ,なるほど.

 S...X...
 ......XT

Sが始点,Tが終点,Xが障害物.
とかでも迂回しないとダメ.
うおおおおお.修正ー.
直った,サブミット!pre test WA.時間切れ.

E. Chess

障害物のある無限に広いチェス盤が与えられる.
障害物は座標の絶対値が10以下の部分にしか無い.
原点からナイトがKターン以内で辿りつけるマスの数をmod 1000000007求める問題.
Kは10^18以下.

原点付近にしか障害物がないから,原点付近を全探索して,あとは適当に….
って,何となく思うけど,ちゃんとやろうとすると全然わからないよ?
うーん,諦めよう.

Hacks

Cで,茸さんが勘違いしてるっぽかったのでとりあえず落としておく.
あとは,なんか (res*2 - n)%mod みたいなことして,マイナスになりそうな人がいた.
マイナスになるケースを全探索して探して落とす.
次々マイナスになるコードがサブミットされてくる….
片っ端から落とす.
A問題でコード誤読して1失敗.
合計5成功1失敗.

Results

ABCは無難に通る.

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問目のジャッジの答えが間違えてたのか,一部正しく判定されなくて,その後修正された.

January 2011 Cook-Off 5問目 - Whole submatrix (この記事を編集する[管理者用])

Source

codechef January 2011 Cook-Off 5問目
Problem Statement
codechef January 2011 Cook-Offの参加記録

問題概要

N*Mの{0,1}行列が与えられる.(Nは1000以下,Mは3以下)
L個 (N以下) の異なる整数a[k]と,K個 (M以下) の異なる整数b[k]を選んで,
すべてのi,jに対して,行列のa[i], b[j]要素が全部1となるような選び方は何通りあるかmod 1000000080798150871で求める問題.

解法

列について全探索すると,選んだ列全部が1の行しか使えないので,コンビネーションで求まる.
コンビネーションはDPで計算しておくと,modの値がでかくてもオーバーフローしない.

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

続きを読む

January 2011 Cook-Off 4問目 - Time of collisions (この記事を編集する[管理者用])

Source

codechef January 2011 Cook-Off 4問目
Problem Statement
codechef January 2011 Cook-Offの参加記録

問題概要

N個 (50000以下) の粒子が1次元の線上を移動している.
粒子の初期位置 (-1000000以上1000000以下の整数) と初期速度 (-20以上20以下の整数) が与えられる.
粒子が衝突したときは,お互いの速度を入れ替える.
衝突が起こる時間の和の有理数の形で厳密に求める問題.
無限回衝突が起こるならそれを指摘する.

解法

速度の取りうる値は41通りしかないので,それで分類して処理する.
速さAと速さBのグループを考えるとすると,(Aの方が右向き速度が大きい)
尺取メソッドで,それぞれのA粒子の右にあるB粒子の数とその座標の和を求めて,衝突までの時間の和を計算する.
うまくやれば多倍長は必要なくできるっぽい(?)けど,多倍長を使ってしまった.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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