hotpepsiの練習帳

TCO13 Algorithm Round2C

02:00

Easy (250) DancingFoxes

問題

• N人でダンスをする
• 共通の友達同士でダンスをすると友達になれる
• 友達かどうかが与えられる
• CielとJiroが友達になるための最小のダンスの回数を求める

方針

• Warshall-Floydで距離を求める
• 距離がダンスの回数?
• Challenge Succeeded
• (終了後)
• ダンスイベントの回数だったらしい
• editorialを読む
• 直接の友達の距離を1として、総距離Dを求める
• N=D+1人をフラットに並べて、左端と右端がCielとJiroと考える
• 連続した3人ずつを1グループとして、同じイベントでダンスをする
• 3人の両端の2人がダンスをして、終了後、直接友達になり、人数が1減る
• 3人に満たない人数ならダンスしない
• すなわち、Nが3以上のとき、人数がN/3ずつ減っていく
• https://github.com/firewood/topcoder/blob/master/tco_2013/DancingFoxes.cpp

結果

--- 0pt 519th/978 rating 1320 -> 1311 (-9)

イベントの回数という解釈ができたとしても解けなかった気がする。

Google Code Jam 2013 Round 1B

18:17

A. Osmos

問題

• 物体を吸収していくゲーム
• N個の物体と、手持ちの物体の重さが与えられる
• 手持ちの物体より軽い物体は吸収でき、その重さが加わる
• 場に任意の重さの物体を追加するか、または、場の任意の物体を除外することができる
• 全ての物体を吸収するために必要な、追加または除外の操作回数を求める

方針 (small, large)

• 貪欲
• N個全てを除外するのが最大値
• 1個ずつ吸収していく
• 自重より軽いものがない場合は、自重の-1の重さのものを追加して、追加回数をカウントしておく
• 残りを全て除外したと仮定して、最小値を更新する
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1B_A.cpp

B. Falling Diamonds

問題

• ダイアモンドが上から落ちてくる
• 下にダイアモンドが存在する場合、左か右に積もっていく
• おおむね三角形になる
• 落ちてくる総数と、座標(X,Y)が与えられる
• その座標にダイアモンドが積もる確率を求める

方針 (small)

• (終了後)
• 1個,5個,9個...と、4x+1個ずつ、三角形に積もる
• 頂点を除き、片側に積もる最大の個数は|X|+|Y|
• 三角形の内側なら1.0、完全に外側なら0.0、その間なら計算する
• 両側にlength個ずつ落ちる場所があり、N個落ちてくるときの確率を求める
• 左に落ちる場合を0、右に落ちる場合を1として、Nビットを全列挙して足す
• ただし、片側にlength個以上落ちた場合は、反対側に落ちたものとして計算する
• 落ちる個数はpopcount(x)＋max(0,popcount(~x)－length)
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1B_B_s.cpp

方針 (large)

• (終了後)
• kmjpさんのブログを読む
• DPで計算できるっぽい
• i個落ちてきたときの確率テーブルがあり、i+1個目が落ちてきたとする
• j個存在するが確率Pとする
• 1/2でこちらに落ちない(反対側に落ちる)ので、dp[i+1][j]に0.5×Pを加える
• 1/2で落ちるので、dp[i+1][j+1]に0.5×Pを加える
• すでにlength個落ちている場合は、反対側に落ちるので、dp[i+1][length]にはdp[i][length]を加える
• 反対側にlength個落ちている場合は、こちらに落ちるので、dp[i+1][length+1]にdp[i][length]を加える
• length=6のときのテーブルは以下の通り

i	0個	1個	2個	3個	4個	5個	6個	7個
0	0.500	0.500
1	0.250	0.500	0.250
2	0.125	0.375	0.375	0.125
3	0.063	0.250	0.375	0.250	0.063
4	0.031	0.156	0.313	0.313	0.156	0.031
5	0.016	0.094	0.234	0.313	0.234	0.094	0.016
6	0.000	0.063	0.164	0.273	0.273	0.164	0.063	0.000
7	0.000	0.000	0.145	0.219	0.273	0.219	0.145	0.000	0.000
8	0.000	0.000	0.000	0.254	0.246	0.246	0.254	0.000	0.000	0.000

• 次の行に0.5倍ずつしたものを加える形になっている
• 行の合計値が1.0
• 7個以上落ちてきたとき、6個までしかたまらない
• 7個落ちてきたとき、1個しかない場合は存在しない
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1B_B_l.cpp

結果

A small+large 22pt 1584th/4678

Bはビット列挙を思いつかず。面白い問題だった。

SRM 578

02:46

Div1 Easy (250) GooseInZooDivOne

問題

• 檻の中にガチョウとアヒルがいる
• ガチョウは1匹以上、合計で偶数匹いる
• あるガチョウからマンハッタン距離dist以内にいる鳥はガチョウである
• ガチョウとアヒルの取りうる組み合わせを求める

方針

• あるグループがガチョウでない場合は全てアヒル
• その場合、他のガチョウとはdistより離れている
• ということは、いずれにしろdist以内でグループ化すればよい
• union-findでグループ化した(けど普通にDFSでいい)
• グループ単位でガチョウなのかアヒルなのかの2択
• それに1羽以上と偶奇の制約が加わる
• 最大50×50＝2500グループ
• 1グループずつ偶奇を数え上げてみる
• 作れる偶数の総数と奇数の総数でDP
• 直前の偶数の場合の数をeven、直前の奇数の場合の数をoddとする
• 次のグループが偶数なら、そのグループを足しても偶奇が変わらない
• そのグループを使う場合と使わない場合で、場合の数はそれぞれeven×2とodd×2になる
• 次のグループが奇数なら、偶奇が変わる
• 奇数に足すときは偶数が作れるので、evenに加えてodd個の偶数が作れる
• 偶数に足すときは奇数が作れるので、oddに加えてeven個の奇数が作れる
• 最後に、存在しない(ゼロ羽)場合を引く
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_578/GooseInZooDivOne.cpp

結果

o-- 100.88pt 299th/576 rating 1271 -> 1320 (+49)

方針自体はだいたい合っていた。偶数のグループの数は2の累乗であり、奇数のグループは偶数個だけ取り出すのだが、それも2の累乗で求めることができるので、もっと簡単に書けたらしい。

goose＝ぐーす＝偶数、な気がする。

Google Code Jam 2013 Round 1A

23:23

Problem A. Bullseye

問題

• 白地に黒丸を描く
• 書き始めの半径rと、ペンキの量tが与えられる
• 中途半端な丸は描かない
• 何個丸が描けるか求める

方針 (small)

• シミュレーション
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_A_s.py

方針 (large)

• 半径rに必要なペンキの量は(r+1)^2-r^2=2*x+1
• 半径は2ずつ増えるので、必要なペンキ量は1,5,9,...または3,7,11,...
• 半径の半分をxとすると4x+1または4x+3
• 積分するとxから必要なペンキの量が求まる (2*x^2+xまたは2*x^2+3*x)
• 開始の半径rが3以上のときは、tにそれまでに必要なペンキの量を足す
• 解の公式でxを求める
• (math.sqrtを使ったため通らず)
• 整数のsqrtに修正
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_A_l.py

Problem B. Manage your Energy

問題

• 初期エネルギーEと、毎日の回復量R、N日分の幸福量Aが与えられる
• 一日のエネルギーはEを超えない
• 消費量×Aの総和の最大を求める

方針 (small)

• Eの最大値が小さいので、その日の消費量を1からEまで全部試す
• next[次の日の残りエネルギー] = 幸福量
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_B_s.cpp

方針 (large)

• (終了後)
• どうやら最大のから消費していけばよいらしい
• 次に消費する日はpriority queueで決める
• 日ごとに、少なくともその値以上を保つ必要がある最小値minと、その日に取りうるエネルギーの最大値maxを持っておく
• 初期値はmin=0、max=E
• 消費するときは、その日に消費できる最大値max-minを消費する
• その結果、前日にはmax-R以上、前々日はmax-2*R以上を保つ必要があるので、更新する
• また、消費できる最大値まで消費するので、次の日以降の最大値は、min+R、min+R*2、...となるので、更新する
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_B_l.cpp

結果

A small + B small = 23pt 2654th

もっとシンプルに解く必要がある。

SRM 577

23:39

Div1 Easy (250) EllysRoomAssignmentsDiv1

問題

• SRMの部屋割りを行う
• Ellyと他の参加者のレートが与えられる
• Ellyの部屋の平均レートを求める

方針

• 問題文よく読まずにスタート
• サンプル合わなくて終了
• (終了後)
• 自分以外は均等に割り振られるので平均値を使う
• 自分が割り当てられるときは自分のレートを使う
• 最後の場合だけ端数になるので、場合わけ
• 端数の処理で自分を含まない場合、人数が多いほうと少ないほうの両方を計算
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_577/EllysRoomAssignmentsDiv1.cpp

結果

--- -1 -25pt 759th/771 rating 1439 -> 1271 (-168)

上がる余地がたくさんできた。