Entries

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

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

2012 Qualification Round C問題 - Recycled Numbers (この記事を編集する[管理者用])

Source

Google Code Jam 2012 Qualification Round C問題
Problem Statement

問題概要

AとBは同じ桁の正整数.
整数xの下何桁かを,そのまま,xの左に移動させて,整数yが得られるとき,(x, y)の組を良いという.
A ≤ x < y ≤ Bで,良い組(x, y)はいくつあるかを求める問題.
A, Bはsmallは1000以下,lergeは2000000以下.

解法

xは全部試す.
実際に,右の何桁かを移動させて,それが条件を満たしているか調べれば良い.
1212みたいなときに,1桁移動と3桁移動で同じ組が得られるのを重複して数えてはいけない.
数えたものを記録しておいても良いし,何桁か移動してxに戻ったらそれで打ち切るなどとすれば良い.

Cによるスパゲッティなソースコード

続きを読む

2012 Qualification Round B問題 - Dancing With the Googlers (この記事を編集する[管理者用])

Source

Google Code Jam 2012 Qualification Round B問題
Problem Statement

問題概要

ダンスコンテスト.参加者はN人.
審査員が3人いて,それぞれの審査員は0点~10点 (整数) をつける.
参加者の点数は,その合計で決まり,30点が満点.
ただし,ある参加者に対して審査員の点数がばらけることは珍しく,
 審査員の点数の最大 - 最小が2を超えることはない
 審査員の点数の最大 - 最小が2となった参加者はちょうどS人いる.
N人の参加者の点数(それぞれ合計点のみ)が与えられる.
参加者の中で,少なくても1人の審査員からp点以上の評価を得た人数の最大値を求める問題.
Nはsmallは3以下,largeは100以下.
Sは可能な値.

解法

点数をtとして,
 (t+2)/3がp以上ならp点以上の評価が無条件に得られる
 最大 - 最小が2を超えても良いなら,(t+4)/3がp以上ならp点以上の評価が得られる (tが1以上なら)
S人は上に該当せず,下に該当する人にgreedyに振り分ければ良い.
ただし,t=0の時は,例外処理が必要で,この場合は絶対に全審査員の点数は0.

Cによるスパゲッティなソースコード

続きを読む

2012 Round 1A B問題 - Kingdom Rush (この記事を編集する[管理者用])

Source

Google code jam 2012 Round 1A B問題
Problem Statement

問題概要

Nステージからなるゲームがある.
ステージiは,
 すでにa[i]個の☆を獲得していれば,簡易クリア可能
 すでにb[i]個の☆を獲得していれば,完全クリア可能.
最初は☆を持っていない.
ステージを簡易クリアすると☆が1個もらえる.
ステージを完全クリアすると☆が2個もらえる.ただし簡易クリアしているステージに対しては追加で☆1個のみもらえる.
ステージは好きな順番にプレイできる.
☆を2N個集めるまでにステージをプレイしなければいけない回数の最小値を求める問題.
smallはNは10以下,largeはNは1000以下.

解法

Greedy.
完全クリア可能なステージに対しては,すぐクリアすれば良い.
そのうちクリアしなければならないし,クリアすることで不利になることもないから.
簡易クリアのみ可能なステージだけになったら,完全クリア可能な閾値の高いものから簡易クリアしていく.
完全クリア可能な閾値が低いものは,それによって,完クリか可能になり,プレイ回数が節減できるかもしれないから.

Cによるスパゲッティなソースコード

続きを読む

2012 Round 1A A問題 - Password Problem (この記事を編集する[管理者用])

Source

Google code jam 2012 Round 1A A問題
Problem Statement

問題概要

B文字のパスワードのうち,すでにA文字を打ち込んだ.打った文字は見えない.
ただし,打ち込んだ文字は間違えているかもしれない.
i文字目が間違えていない確率p[i]が与えられる.
バックスペースk回押すと,最後に入力したk文字を消すことができる.
Enterを1回押すと,間違えていたら,全てが消える.合っていればそれで終了.
パスワードを全部打ち込み終わるまでに押す平均キー数の最小値にする戦略をとった時,その平均キー数求める問題.
smallはAが3以下, Bが100以下.
largeはA, Bは100000以下.

解法

戦略は,  Enterを押して,もう1回全部打ち直す.(この場合B+2回必要)
 バックスペースをk回押して,打ち直す.間違えていたら全部もう1回打つ必要がある.
の2通りだけ考えれば良い.
最初のk文字が全部正しい確率とかは最初に求めておけば良い.

Cによるスパゲッティなソースコード

続きを読む

Japan 2011 予選 C問題 - ビット数 (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 予選 C問題

問題概要

問題分が日本語なので略.

解法

最下位のビットが1なら,そのビットをどっちにわけてもいい.
最下位のビットが0なら,両方の数字の最下位のビットが立つように分けたほうがいい.
というのを再帰的にやる.
(もしくは,分ける片方の数字は,すべてのビットが1の,N未満の最大の数にすればいい)

Cによるスパゲッティなソースコード

続きを読む

Japan 2011 予選 B問題 - 最高のコーヒー (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 予選 B問題

問題概要

問題分が日本語なので略.

解法

時間を逆から遡ると,飲めるコーヒーの種類は増えていく一方なので,飲めるコーヒーのうちもっとも満足度の高いものを飲めば良い.
ヒープなどを使えばO(N log N).
以下の解答は,賞味期限の早いものから順番に飲んでいって,賞味期限切れで飲めなかった,今まで飲んだ満足度が一番小さいのを飲むのを取り消していく.

Cによるスパゲッティなソースコード

続きを読む

Japan 2011 予選 A問題 - カードシャッフル (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 予選 A問題

問題概要

問題分が日本語なので略.

解法

目的のカードがある場所を,最後のシャッフルから順番に辿っていく.

Cによるスパゲッティなソースコード

続きを読む

Japan 2011 決勝 C問題 - ワイルドカード (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 決勝 C問題

問題概要

問題分が日本語なので略.

解法

DPする.
dp[a][b]は1つ目の文字列のa文字目以降にマッチして,2つ目の文字列のb文字目以降にマッチしない,題意を満たす正規表現とすればいい.
最初や最後に*を使わないパターンにもうまく対応させる.

C++によるスパゲッティなソースコード

続きを読む

Japan 2011 決勝 B問題 - バクテリアの増殖 (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 決勝 B問題

問題概要

問題分が日本語なので略.

解法

x^x mod zを考えるとき,基本的にyが大きくなると,yについて周期phi(z)に落ち込む.
なので,x mod zとx mod phi(z)があればいい.
ただし,phiはオイラーのファイ関数.
時刻n後のバクテリアの数をf(n)として,
1以上C以下の整数xについて,f(n) mod xの値と,f(n)がxより大きいかどうかを覚えておく.

Cによるスパゲッティなソースコード

続きを読む

Japan 2011 決勝 A問題 - アンテナ修復 (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 決勝 A問題

問題概要

問題分が日本語なので略.

解法

三角形の面積は,2辺の長さとsin(間の角)と1/2の積なので,
与えられた要素を並び替えて,隣り合う積の和を最大化すればいい.(最初と最後は隣り合うとみなして)
直感的に大きいものは大きいものと当てたほうがいいから,一番大きい物を起点に,その左右に1個ずつならべていく.
少なくても,2要素をswapしてこれ以上大きくできないのは自明で,これが最大値なのもちゃんと証明すれば証明できる.

Cによるスパゲッティなソースコード

続きを読む

Japan 2011 決勝 (参加記録) (この記事を編集する[管理者用])

2011年10月08日13時から3時間,5問.
[ Link ]

A, B, C, D-small, E-smallの92点で1位.らしくない順位をとってしまった.
日本限定ってことで,GCJらしくないセットだった.だからこそ戦えた感じ.
本家GCJではセンスが要求されるが,GCJJでは実装力と注意深さ的なのが要求されてる気がした.
大雑把な方針はすぐ見えるが,細かいところは地味に難しく,注意深く実装しないとバグるタイプの問題.
後,smallが強いのも特徴で,large用の解法でsmall通ると,だいたいlargeも通る気がする.
以下時系列順.

まずは全部問題を読む.
Aはgreedyでいいとして…,
Bは指数の方の周期はオイラーのファイ関数なのでそれでごにょごにょするだけだろう.
CはどうせDP,それぞれの文字列に対してどこまでマッチしているか(あるいはマッチしてる区間か?)を覚えてごにょごにょするだけ.
Dは…わからんなぁ…,smallは全探索だけど.
Eは…わからんなぁ…,smallはマップ作ってBFSするだけだろうけど.
A, B, Cを解くのは前提で,DとEを解けるか勝負っぽい.(気がしてた)
とりあえず,Aをさっくり通す.
B問題は…,あれ,(X^X)^(X^X)みたいな感じになるから,基数はmod Cで,指数はmod phi(C)で考えないといけない….
…,計算量爆発しませんか….
ああ,すべての時間について,バクテリアの数 mod 1, mod 2, ..., mod 1000をすべて計算しておけば,DPっぽくいける.
計算量 (logとか除けば) 1000^2で,テストケース500個あるけど,大丈夫か?
テストケース作って試したけど,大丈夫そう.
WAる.
phi[i]にすべきところを1箇所iにしてた.提出.
もう1時間近くたってしまってて絶望…,してたけど,みんなの点数も低い.
C問題は…,これ辞書順最小難しくないか??
とりあえず,普通にDPを書いてみる.
愚直に書いたら,O(50^6)とかになってしまった….
いや,それより,辞書順最小がむずい.
string使って富豪プログラミング…,まぁ,試しにね….
ランダムケース食わせると,1ケースあたり1秒ぐらい…,大丈夫かな,これ….
念のためO(50^5)に落としてみたけど,もともとO(50^5)のstringが重くて効果なし.
最悪ケースっぽいのを食わしても,どっちみち1秒で終わる.あれ,たぶん大丈夫だな….
small食わせると,答えの長さが無限大になってるケース (答えを見つけれてない) がいくつかある.
4分以内に修正しなきゃ…,最初や最後が*じゃないケースにまともに対応してなかったーーー.
4分オーバー.
修正してもう1回small,WAる.
smallの実行結果見ると明らかにおかしい…,対応しきれてなかった.
今度はsmall AC, largeも提出.
残り1時間10分ちょい.DもEもlarge考えてる暇はなく,smallを両方通す作戦に移行.
(Dは前の行の状態や道がどのようにつながってるかのDPであることに気づいたけど,そんなんやってられるかー)
Dの全探索をやる.
バグる….
あせる….
あう.
small実行.最後の方の答え5ばっかだなー.WA.
…,見つかった最大値を初期化するの忘れてる….だから5ばっかりだったんだよ…,もうちょっと怪しめ….
small AC.
この時点でなんでかしらないけど1位.
3分後にhosさんに抜かれて,自分のほうが1回WAが多くて,実質30秒差.
Eのsmallをやる.
線に近づけるのに気づいてなかった.
えっと…,めんどいです.
座標を縦横3倍に拡大して,座標/3の値が切り替わる移動だけコスト1にすればいいか.
マップを作って,01-BFSを書く.
答えが合わない.
マップが間違ってる….
直す.
答えが一瞬合う.
コメント消してるうちに答えが合わなくなる.
あれ….
結局何が悪かったのかわからなかったけどもう1回デバグすることになった.
1発でsmall AC.
残り時間10分では流石に後は何も出来ず.small 2つなんて30分あれば行けると思ってたのに….
みんなもっと解いてくると思ったのだけど,やってみると地味なところが難しいセットで,意外と手間取ってしまったようです.

以下は,D-smallとE-smallのコード.
A問題, B問題, C問題は個別の記事を参照.

続きを読む

2011 Qualification Round D問題 - GoroSort (この記事を編集する[管理者用])

Source

Google code jam 2011 Qualification Round D問題
Problem Statement
2011 Qualification Round 自分の参加記録

問題概要

1~Nがちょうど1回ずつ登場する配列が与えられる.
配列を昇順でソートするのに必要な操作回数の期待値の最小値を求める問題.
1回の操作では,
 配列の要素をいくつか (0以上N以下) 固定して,配列のその他の要素をランダムに並び替える
ことができる.
Small: Nは10以下
Large: Nは1000以下

解法

まず,最適戦術として,自分がいるべき場所にすでにいる場合に限り固定する,というのを繰り返せば良い.
これでいいことは,直感的に説明がつく.
後は,DPする.
全てが,自分がいるべき場所にいないとして,1回の操作で,正しい場所に戻る数字の数がk個となるパターン数を数え上げる.
そのパターン数の数え上げもDPでできる.
DPして出てくる答えとしては,簡単で,自分がいるべき場所にいないものの数がそのまま答えになる.
直感的にも,それは正しそうなことはわかるが,全然自明じゃない.
ということで,DPじゃなくても,規則性を見つければ勝ち.
DPでlargeまで解く場合,場合の数がdoubleでもオーバーフローするので,例えばlogを取りながらうまく計算するなどする必要がある.

Cによるスパゲッティなソースコード

続きを読む

2011 Qualification Round C問題 - Candy Splitting (この記事を編集する[管理者用])

Source

Google code jam 2011 Qualification Round C問題
Problem Statement
2011 Qualification Round 自分の参加記録

問題概要

N個の正整数が与えられる.
その整数を2つのグループにわける.片方が空集合であってはいけない.
その2つのグループの各要素のXOR (排他的論理和) が等しくならなければいけない.
そのようなグループ分けがなければNOと出力し,そうでなければ,片方のグループの要素の和を最大値を出力する問題.
Small: Nは2以上15以下
Large: Nは2以上1000以下

解法

全てのXORが0になればどんな分け方をしても良い.
そうでなければ,どんな分け方をしても駄目.
分けれるなら,最小の1つとその他に分ければ良い.

Cによるスパゲッティなソースコード

続きを読む

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

Source

Google code jam 2011 Qualification Round B問題
Problem Statement
2011 Qualification Round 自分の参加記録

問題概要

{Q, W, E, R, A, S, D, F} を基本文字と言う事にして,それ以外のアルファベットを基本じゃない文字ということにする.
最初リストは空で,リストに順番に1文字ずつ,合計でN文字入れていく.
最終的なリストを求める問題.
ただし,以下2種類の規則が与えられ,それが適応できる状況になったら適応していく.
 規則1: xyz (xとyはベース文字,zはベース文字でない) の形で与えられ,xとyが隣り合ったら,即座にxy (かyz) をzに置き換える
 規則2: xy の形で与えられ,規則1が即座に適応できない状況で,xとyの両方がリストに存在するなら,リストを空にする
Small: 与えられる規則1の数は1個以下,与えられる規則2の数は1個以下,Nは10以下
Large: 与えられる規則1の数は36個以下,与えられる規則2の数は28個以下,Nは100以下

解法

シミュレーションすれば良い.

Cによるスパゲッティなソースコード

続きを読む

2011 Qualification Round A問題 - Bot Trust (この記事を編集する[管理者用])

Source

Google code jam 2011 Qualification Round A問題
Problem Statement
2011 Qualification Round 自分の参加記録

問題概要

2つのロボットと,2組の一直線上に並んだボタンがある.
ボタンは,それぞれ,100個ずつ等間隔に並んでいる.
片方のロボットは片方の直線上を動け,もう片方のロボットはまた別の直線上を動ける.
ロボットは時間1あたりに,今いる場所のボタンを押すか,隣のボタンに移動することができる.
最初,2つのロボットはそれぞれ端のボタンにいる.
順番に押すべきボタンの列が与えられたとき,それを達成するための最小時間を求める問題.
Small: 押すべきボタン数は10個以下
Large: 押すべきボタン数は100個以下

解法

それぞれのロボットが自分が次押すべきボタンに近づいていくように動けば良い.
愚直に時間を1ずつ進めてシミュレーションしても間に合うので,そうした.

Cによるスパゲッティなソースコード

続きを読む

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

2010年05月07日08時から24時間,4問.
[ Link ]

今年は25点以上でRound 1に進出.
Smallだけで進出することも可能になった.

A問題 - Bot Trust

2つのロボットと,2組の一直線上に並んだボタンがある.
ボタンは,それぞれ,100個ずつ等間隔に並んでいる.
片方のロボットは片方の直線上を動け,もう片方のロボットはまた別の直線上を動ける.
ロボットは時間1あたりに,今いる場所のボタンを押すか,隣のボタンに移動することができる.
最初,2つのロボットはそれぞれ端のボタンにいる.
順番に押すべきボタンの列が与えられたとき,それを達成するための最小時間を求める問題.
Small: 押すべきボタン数は10個以下
Large: 押すべきボタン数は100個以下

シミュレーションやるだけで問題ないよな.
Largeでも時間は余裕.書く.サブミット.

B問題 - Magicka

{Q, W, E, R, A, S, D, F} を基本文字と言う事にして,それ以外のアルファベットを基本じゃない文字ということにする.
最初リストは空で,リストに順番に1文字ずつ,合計でN文字入れていく.
最終的なリストを求める問題.
ただし,以下2種類の規則が与えられ,それが適応できる状況になったら適応していく.
 規則1: xyz (xとyはベース文字,zはベース文字でない) の形で与えられ,xとyが隣り合ったら,即座にxy (かyz) をzに置き換える
 規則2: xy の形で与えられ,規則1が即座に適応できない状況で,xとyの両方がリストに存在するなら,リストを空にする
Small: 与えられる規則1の数は1個以下,与えられる規則2の数は1個以下,Nは10以下
Large: 与えられる規則1の数は36個以下,与えられる規則2の数は28個以下,Nは100以下

問題文がややこしい.
連鎖とかあるの,同時に2つ以上の条件満たしたらどうなるの?
….
そういうのは無いよう条件が作られているのか!
じゃあ,まぁ,適当にシミュレーションでいい.
書く.Incorrect.あれ?
あ,これ,規則2は全部消えるのか.挟まれた部分だけ消えるんだと思ってた.
修正.SmallはCorrect.Largeもサブミット.

C問題 - Candy Splitting

N個の正整数が与えられる.
その整数を2つのグループにわける.片方が空集合であってはいけない.
その2つのグループの各要素のXOR (排他的論理和) が等しくならなければいけない.
そのようなグループ分けがなければNOと出力し,そうでなければ,片方のグループの要素の和を最大値を出力する問題.
Small: Nは2以上15以下
Large: Nは2以上1000以下

ん,Nは1000?
どうやるんだ….
分けれる条件はXORが0.
って,分けれるならどうわけても分けれるのか.
えっと,全部総取りは駄目なんだっけ,駄目って書いてあるな.
じゃあ,一番少ないのを弟に渡して終わりかな.
書く.サブミット.

D問題 - GoroSort

1~Nがちょうど1回ずつ登場する配列が与えられる.
配列を昇順でソートするのに必要な操作回数の期待値の最小値を求める問題.
1回の操作では,
 配列の要素をいくつか (0以上N以下) 固定して,配列のその他の要素をランダムに並び替える
ことができる.
Small: Nは10以下
Large: Nは1000以下

これ前計算したことあるから結果知ってる.
合ってない場所だけ入れ替えると,大体1個合うから,大体「場所が間違えてる要素の数」ぐらいでソートが終わりそうだけど,実際にそうなる.
でも,まあ,これ,知らなかったら大変だろうなぁ…,普通にやるならDPかな.
知ってるから,それで書く.サブミット.

Result

4問とも通った.少し簡単になったかなぁ.

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

2010年06月12日23時から2時間30分,4問.
[ Link ]

A. De-RNG-ed

項数Kの数列が与えられる.その数列は
 x[n+1] = (A*x[n]+B) mod p
で生成されている.
A,Bは0以上P未満で,pは10^D以下.
数列とDが与えられたとき,それだけの情報から,K+1項目が一意に定まるなら求めて,一意に定まらないならそれを指摘する問題.
small: Dは4以下
large: Dは6以下

うーん,全部の問題読むまで解くつもりはないけど一応ちょっとだけ考える.
pが決まれば,AかBは決めれる?
項数が1のとき困る…が,それなら一意に定まらないから問題ない.
smallはそれで全探索で行けそう.
largeはそれじゃ無理そう…,うーん.

B. Fence

長さlength[i]の板がN種類与えられる.Nは100以下.
それぞれの種類の板は無限に沢山ある.
それらを繋げて,ちょうど長さLの板を作りたい.Lは10^10以上10^18以下.
最小で何個の板を使えばよいか求める問題,作れないならそれを指摘する.
small: length[i]は10^2以下
large: length[i]は10^5以下

これって,ある程度までDPで求めて,残りは一番長いのを使うってので駄目なんだっけ…?
良かった気もするし駄目だった気もする.

D. Different Sum

B進数で筆算の足し算をやる.
答えがNになるようなもので,足す数の各列は同じ数字が2度以上でないようにしたい.
Nが与えられたとき,そのような方法はいくらあるか mod 1000000007 で求める問題.
small: Nは100以下,Bは10以下
large: Nは10^18以下,Bは70以下

C問題が微妙に長かったのでこっちから読む.
DPっぽい…が,時間間に合う?
 dp[現在の桁][繰り上がりの数][前の桁で使った数字の数]
…あれ,0の扱い大丈夫か?
うーん,ダメっぽい.どうする….
 dp[現在の桁][繰り上がりの数][前の桁で使った数字の数][前回0の桁を使ったかどうか]
でどうだ?
まぁ,これは簡単なのでは,C問題も読んでみよう.

C. Hot Dog Proliferation

一直線上の並んだ無限個の箱があって,いくつかボールが入っている.
ある箱から2個ボールを取り出して,その両脇の箱に1個ずつボールをいれるという操作ができる.
全ての箱に高々1個しかボールが入ってない状態にするために必要な,最小限の操作の回数を求める問題.
最初に入ってるボールの座標は-10^6以上10^6以下.
最初にボールが入ってる箱の数は200個以下.
small: ボールの合計数は200以下
large: ボールの合計数は100000以下

うーん? 全部の箱の玉の数を,ヒープに突っ込んで,大きい方から処理していく,シミュレーションでいけるんじゃないの?
玉の数,100000ぐらいしかないし…,あれ,結構大きくなる気もするな…,行けるのかどうか分からない.
とりあえず,最小値求めろと書いてるけど,どうやってもターン数かわらないよね.
書いてみよう.
書いてみた.
うわ,答え滅茶苦茶大きくなる….
1つの箱に500ぐらい玉置くと,それだけで8秒ぐらいかかるよ….
Largeとかどうするのよ….
取り敢えず,2の冪の個数だけは一度にまとめて処理できないかな….
 00000800000
は最終状態は
 01111011110
となる!
2の冪だったら全部同じ感じ.
問題は,何ステップでこれになるのか…?
 1, 5, 30, 204, 1494, 11440, ...
みたいな数列…,数列検索かけても引っかからないし,素因数分解とかしてもわからない.
うーん,これは最初に求めそうか….
2^kのものがあったとして答えを求める,2^(k-1)までの答えは使えば良い.
…,終わらねぇ…,2^12が出てこない….
てか,気づいたら1時間以上たってるし.
この問題は,結構やばい,違うのやろう,smallだけサブミット,correct.

B. Fence

取り敢えず,普通にDP+greedyしてみる.small通るかどうか試そう.
smallサブミット,correct.
もういいや,largeも出してしまえ….

A. De-RNG-ed

一応smallだけ提出してみる.Incorrect.あれ.まぁ,これ解いても得られるものはないから無視.
(x[i]よりpが大きいという条件を無視していた)
てか,だったらなんで,small出したんだ….

D. Different Sum

Cが解けないんだったら,Dが解けないと無理.Aじゃ足りない.
方針はだいたいわかってるので,いろいろ考えながら書けば解けるはず.
でも,残り45分だし,結構面倒そうだし,書けるか?
書いてみる.
微妙に合わない.
時間終わった.

Result

BのLarge落ちました.そりゃそうだよなぁ.Dが解けても無理でした.
しかし,相変わらず,解けそうで解けない問題出してくるなぁ,GCJは…,楽しい.
Aのk=2の場合は単純にできることに気づかなかったのは頭悪い.
他の問題は後で復習しよう….

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

2010年06月05日23時から2時間30分,4問.
[ Link ]

A. Elegant Diamond

ダイヤモンド型に文字列に,新しく何文字か付け加えて,左右対称かつ上下対称なダイヤモンド型文字列にしたい.
付け加える最小の文字の数を求める問題.

やるだけの実装問題っぽいけど,どうやるんだろう….
とりあえず,Round 2なので落ち着いて,問題を読んでいこう.

B. World Cup 2010

2^pチームでトーナメントが行われる.pは10以下.
各対戦のチケットの価格が与えられる.
各チームに対して,そのチームの対戦を最大で何個まで見逃しても良いか,という数字が与えられる.
勝敗がわからないとき,買うチケットを選んで,コストを最小化する問題.
small: チケットの値段は全て1
large: チケットの値段は0以上100000以下

…,どうみてもDPに見える.
segment treeみたいな感じのツリー作って,
 今みているノード,今までその集合は何回見逃したか
を状態にしてDPすればいい.
てか,smallだけ解く方法とかが分からない.
まぁ,これは…,解ける.次の問題読もう.

C. Bacteria

ライフゲーム.
 生きていて,上か左が生きてたら,次のターンも生きてる
 死んでて,上と左が生きてたら,次のターン生きる
 それ以外は死ぬ
全滅するまでにかかるターンするを求める問題.
最初の生きてるマスの集合は,長方形型のグリッドで与えられる.
small: 盤面のサイズが100*100以下,長方形の数は10以下
large: 盤面のサイズが1000000*1000000以下,長方形の数は1000以下

うーん,問題文のサンプル見ると,なんか右下にうにょうにょ動いていく感じ.
わからんから,次の問題見よう.

D. Grazing Google Goats

2次元平面上の,N個の点p[i]と,M個の点q[i]が与えられる.
各q[i]に対して,
 p[k]を中心として,q[i]を通る円を考えて,そのN円の共通部分の面積
を求める問題.
small: N=2, Mは10以下 large: Nは5000以下,Mは1000以下

問題文読みにくい.図だけ見て多分理解.
largeが無理ゲーにしか見えない.

B. World Cup 2010

これはDP書くだけ.
書こう.
…めんどうじゃないか,これ.
普通にheapとかsegment treeっぽくノードに番号つけると,入力と上下入れ替えないといけない.
色々書くのが面倒….
まぁ,時間掛かっちゃったけど書いた.一発でサンプルはあった.
smallサブミット,correct.largeもサブミット.

A. Elegant Diamond

とりあえず,実装するだけっぽいので,やってみよう.
でも,どうすればいいの…,ちゃんと考えないと.
小さい対称なダイヤを探して,それを有効活用するように,やれば良い.
で,見つかった最大のサイズをr,もともとのサイズをnとして,答えは
 (2n-r)^2 - n^2
だ.
・・・本当か?
いや,真ん中の方で,対称なダイヤ見つけても,それを有効活用できないし….
4つの頂点のうち,どれかを含む最大サイズの対称なダイヤを見つければ良さそう…かな.
書いてみる.
二次元配列に落として…,めんどうだなこれ.
数字は1桁だっけ?
1桁だ.
アスキーアートのまま扱おう.
で,90度回転する関数用意して,4回回転しながら一番上の頂点を含むような対称ダイヤの最大サイズを全探索する.
書いた.
smallサブミット.Incorrect.がーん.
しばらくコード見なおすけどよく分からない…,やばいぞ….

C. Bacteria

とりあえず,Cのsmallはシミュレーションするだけで良いはず.
部分点を拾っておこう.書いた.smallサブミット.correct.

A. Elegant Diamond

あ,頂点を含まなくても,小さい対称ダイヤが辺上にあれば有効活用できる….
直そう…,これ計算量大丈夫か?
最悪ケース(largeの場合の)を入れてみる.作るの面倒だった.0.2秒ぐらい,まぁ大丈夫かな….
small提出.Incorrect….
うーん….
ちょっといろいろ出力してみよう.
回転がちゃんとできてない!
変数名打ち間違えてるorz
修正.サブミット.Incorrect.むーん….
自分で色々作ったケース全部合うんだけどなぁ….
プログラムが間違えてる?考え方がマズイの?

D. Grazing Google Goats

とりあえず,なんかこのままだと500位以内怪しいので,Dもsmallだけ拾っておこう.
えっと…,2円の重なる部分のライブラリは…,あれ,僕作ってなかったのかな,見つからない….
もういいや,n円で覆われる部分の面積を計算するライブラリと包除原理使って無理やり求める!
smallサブミット.correct.

A. Elegant Diamond

いろいろわからず,とりあえず,-O0 (最適化なし)でコンパイルし直して送ってみるとかいろいろ試す.
まぁ,もちろん全部Incorrect.

Result

B両方と,CとDのsmallのみ正解.
Aができないとか酷い….
普通にデカイダイヤの中心を全探索すれば良かった,そういう方法が何故見えない….
はまったら,違う視点から見て,全部コード書き直しても良いかも.
危険な位置だったけど,なんとか通過.
次は正念場なので,今回の結果は気にせず次頑張ろう.

2010 Round 1C C問題 - Making Chess Boards (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1C C問題
Problem Statement
SPOJ 6706 [CT101CC] (2010/05/28 23:45追加)

問題概要

各セルが黒か白かのM*Nのグリッドが与えられる.
チェス盤を切り取っていく.チェス盤は白と黒とが交互になっている市松模様の正方形の盤面.
切り取っていく順番は,できるだけ大きいのから,複数あるなら,左上のから切り取る.
最終的に,どのサイズのチェス盤が,どのぐらい切り取られたかを求める問題.
small: M, Nは32以下
large: M, Nは512以下

解法

全てのマスに対して,そのマスを左上角になるようなチェス盤のうち,最大サイズをDPで求める.これはO(MN)で可能.
後は,実際に大きいものから切り出していって,切り出されたことによって,DPの値を修正していく.
このときに,サイズごとになぞっていくとO(MN*MIN(M,N))ぐらいになる.
ヒープを使うと,O(MN log(MN))ぐらいで解ける.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1C B問題 - Load Testing (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1C B問題
Problem Statement
SPOJ 6678 [GCJ101C]

問題概要

あるサーバはL人の負荷には耐えれて,P人の負荷には耐えれないということが分かっている.
Cは2以上10以下の与えられた定数として,a人の負荷に耐えれて,a*C人の負荷に耐えられないというaを1つ見つけたい.
負荷テストを1回行うと,好きなXに対して,X人の負荷に耐えれるかどうかがわかる.
最小負荷テスト回数を求める問題.
small: L, Pは10^3以下
large: L, Pは10^9以下

解法

再帰的に考えると,Lを固定したとき,n回の負荷テストでaを見つけることのできる最大のPはP=L*C^(2^n)であることがわかる.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1C A問題 - Rope Intranet (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1C A問題
Problem Statement

問題概要

それぞれ要素数Nの相異なる数字からなる数列A[i]とB[i]が与えられる.
N本の線分の端点をそれぞれ(0,A[i])-(1,B[i])としたとき,交点の数を求める問題.
ただし,3本以上の線分が同じ点で交わることはないとする.
small: Nは2以下.
large: Nは1000以下

解法

全部の線分の組み合わせに対して,交わってるかどうか判定する.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1B C問題 - Your Rank is Pure (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B C問題
Problem Statement

問題概要

与えられた2以上の自然数Nに対して,
 {2, 3, ..., N}
の部分集合SでNがPureなものの数をmod 100003で求める問題.
F(N)を集合Sの中にあるN以下のものの数として
 「NがPure」 とは 「F(N)=1 か F(N)がPure のどちらかが成り立つ」
で定義する.
small: Nは25以下.
large: Nは500以下

解法

コンビネーションを使いながら計算するO(N^3)のDP.
 dp[i][j] = {2, 3, ..., i}の部分集合でiがPureで要素数がjの集合の数

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1B B問題 - Picking Up Chicks (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B B問題
Problem Statement
SPOJ 6691 [GCJ101BB]

問題概要

N匹のひよこが1次元上を移動できる.
各ひよこの初期位置,最大スピードが与えられる.
最初,各ひよこは目的地の左にいる.
K匹以上が目的地に辿り着くために,最小のひよこの追い越し回数を求める問題.
不可能ならそれを指摘する.
small: Nは10以下.Kは3以下
large: N, Kは50以下

解法

目的地に辿り着けるひよこを追い抜かす必要はない,後ろからついていけば良い.
なので,目的地に辿りつけるひよこは,自分より前にいる,目的地に辿り着けないひよこの数だけ追い抜けば目的地にたどり着ける.
つまり,初期位置で前からK匹の目的地に辿り着けるひよこが,目的地に辿り着くまでに追い抜くひよこの数の和を求める.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1B A問題 - File Fix-it (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B A問題
Problem Statement

問題概要

すでに作られているフォルダのパスがN個与えられる.
新しく作りたいフォルダのパスがM個与えられるので,mkdirコマンドを叩かないといけない数を求める問題.
small: N, Mは10以下
large: N, Mは100以下

解法

文字列+実装問題.
すでに作られているフォルダパスを全部ハッシュに入れていった.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1A C問題 - Number Game (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A C問題
Problem Statement
2010 Round 1A 自分の参加記録
SPOJ 7260 [NUMGAME] (2010-09-20 10:40追加)

問題概要

2人でゲームをする.
最初正整数AとBが与えられている.
二人交互に任意の正整数kを選んで以下のどちらかを行う
 A を kB だけ減らす.ただし結果はAは正整数でなければいけない.
 B を kA だけ減らす.ただし結果はBは正整数でなければいけない.
打つ手がなくなったら負け.
A1, A2, B1, B2が与えられるので,
 A ∈ [A1, A2]
 B ∈ [B1, B2]
なる先手必勝パターンの数を求める問題.
small: A1, A2, B1, B2は1000000以下,A2-A1, B2-B1は30以下
large: A1, A2, B1, B2は1000000以下

解法

まず,A, Bが与えられたときに,それが先手必勝かどうかを考える.それは  大きい方が小さい方の2倍以上なら,kを何を選ぶかの選択権があるので,必勝
 そうでなければ,減らし方は1通りしかないのでシミュレーションする
でO(log(min(A,B)))で求めることができる.(smallはこれでOK)
それで,実際に先手必敗パターンを書き出してみると,規則が見える.
具体的には,BはA以上として,Aを固定したとき,先手必敗になるのはBがfloor((A-1)*(1+sqrt(5))/2)+1以下のときのみ.
それを実装すればO(min(A,B))で求まる.
(規則を見つけるコードとその実行結果も以下に貼りつけておきます)

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1A B問題 - Make it Smooth (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A B問題
Problem Statement
2010 Round 1A 自分の参加記録
SPOJ 6700 [GCJ101AB] (2010/05/28 05:20追記)

問題概要

0以上255以下を要素に持つ長さNの整数列が与えられる.
それの隣り合う項の差をM以下にするために必要なコストを求める問題.
できる操作は以下の3種類.
 コストDで1要素を消す
 コストIで好きな場所に好きな要素を挿入する
 コスト1である要素の数字を1だけ増やすか減らす
small: Nは3以下
large: Nは100以下

解法

 dp[今見てる場所(この場所の前までは条件を満たしている)][一つ前の数字]
でDPしようとしたら,ループしたので,ベルマンフォードっぽく書いた.
2010/05/28 05:20追記 ループのない形のちゃんとしたDPも書いた.以下のコードを追加しておきます.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1A A問題 - Rotate (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A A問題
Problem Statement
2010 Round 1A 自分の参加記録

問題概要

N*NのグリッドにRかBの文字が書いてある.重力によって,文字は下に落ちている.
90度時計回りに回転させる.文字は重力によって下に落ちる.
縦横斜め,一直線上にRとBがそれぞれK個以上繋がっている場所があるかどうかを,それぞれ判定する問題.
small: Nは7以下
large: Nは50以下

解法

実装するだけ.サイズは小さいので愚直な方法で大丈夫.
(実際に回転させなくても,右に寄せるでもOK)

Cによるスパゲッティなソースコード

続きを読む

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

2010年05月22日10時から2時間30分,3問.
[ Link ]

開始前

3回あるなかのどれかで勝ち抜けられれば良いので,まだ気楽なラウンド.
2時間半なので4問か(もしくは5問?)と思ってたら3問しかなかった.

A. Rotate

N*NのグリッドにRかBの文字が書いてある.重力によって,文字は下に落ちている.
90度時計回りに回転させる.文字は重力によって下に落ちる.
縦横斜め,一直線上にRとBがそれぞれK個以上繋がっている場所があるかどうかを,それぞれ判定する問題.
small: Nは7以下
large: Nは50以下

なんか予選より問題わかりやすいなぁ,英語読解力的な意味で.
そして,やるだけ問題.largeでもサイズ小さい.
書いた.WAった.あれ?
左下の斜めのライン考えてないじゃんorz
直した.small correct.largeもついでにサブミット.

B. Make it Smooth

0以上255以下を要素に持つ長さNの整数列が与えられる.
それの隣り合う項の差をM以下にするために必要なコストを求める問題.
できる操作は以下の3種類.
 コストDで1要素を消す
 コストIで好きな場所に好きな要素を挿入する
 コスト1である要素の数字を1だけ増やすか減らす
small: Nは3以下
large: Nは100以下

DPですよねっ.
うーん,dp[残り要素の数][一つ前の要素の数字]でいいかぁ….
ま,サイズ小さいし,最も愚直に書いても実行時間大丈夫だろう.
書く.
あれ?これループしないか?
dp[a][b]から数字cを付け加えたらdp[a][c]が必要になる…,ループする.
まぁ,数字付け加えるのは,次の値に近くなるように付け加えるんじゃなければ無意味なので,そういう時だけ考えよう.
これならループしないよね!
書いた.WAった….またかい.
うーん?
次の要素を変えて,目的を満たす場合もあるよね…,なんでそれ考えてないんだ….
直した.自分で作ったサンプルが合わない.くだらないミスを潰す.自分で作ったサンプルは合った.
small correct.largeもサブミット.

C. Number Game

2人でゲームをする.
最初正整数AとBが与えられている.
二人交互に任意の正整数kを選んで以下のどちらかを行う
 A を kB だけ減らす.ただし結果はAは正整数でなければいけない.
 B を kA だけ減らす.ただし結果はBは正整数でなければいけない.
打つ手がなくなったら負け.
A1, A2, B1, B2が与えられるので,
 A ∈ [A1, A2]
 B ∈ [B1, B2]
なる先手必勝パターンの数を求める問題.
small: A1, A2, B1, B2は1000000以下,A2-A1, B2-B1は30以下
large: A1, A2, B1, B2は1000000以下

えーっと…,規則を見つけるゲーム?
とりあえず,小さい場合の答えを列挙しよう.規則わからなければそれでsmallだけサブミットしてもいいし.
A, Bが与えられたとき,先手必勝か後手必勝かを判定するには…
 大きい方が小さい方の2倍以上なら,kを何を選ぶかの選択権があるので,必勝
 そうでなければ,減らし方は1通りしかないのでシミュレーションする
さて,規則は見えるかな….
あからさまに,見えるなぁw
Aを固定したとき,必勝パターンでないのはBがある区間に入っているとき.
この区間の最大値の値って,たぶん(1+sqrt(5))/2ずつ増えてるんだよね…? 確かめる.うん,たぶんそう.
よし,書こう.
書いた.small correct.largeサブミット.

Result

あれ,B落ちた….
> まぁ,数字付け加えるのは,次の値に近くなるように付け加えるんじゃなければ無意味なので
これ嘘じゃない? (これつけててもLarge通ったのでよくわからないけど)
てか,前回使った数字も書き換え直してるし,そんなことやっちゃ駄目じゃん.
もうめちゃくちゃ….

2010 Qualification Round C問題 - Theme Park (この記事を編集する[管理者用])

Source

Google code jam 2010 Qualification Round C問題
Problem Statement
2010 Qualification Round 自分の参加記録

問題概要

ジェットコースターの列に,
 a1, a2, a3, ..., aN
人のグループが並んでいる.
ジェットコースターの定員はK人で,前から乗れるグループのみ乗る.追い越してのることはない.
終わったら,また列の後ろに並ぶ.
R回ジェットコースターを運行したら,のべ何人の人が乗ったことになるかを求める問題.
large: Rは1000以下,Kは100以下,Nは10以下.
large: Rは10^8以下,Kは10^9以下,Nは1000以下.

解法

どのグループが先頭だったら,次はどのグループが先頭になって,何人乗る,ってのを最初に計算しておくと,1ステップあたりO(1)でシミュレーションできるようになる.これでlargeも通る.(以下のコードではこれはやってない)
他は,Nが小さいので,同じグループが2回以上先頭に来たら後はループする.ループを検出して一気に処理してやることでも高速化できる.(以下のコードではこれをやっている)

Cによるスパゲッティなソースコード

続きを読む

2010 Qualification Round B問題 - Fair Warning (この記事を編集する[管理者用])

Source

Google code jam 2010 Qualification Round B問題
Problem Statement
2010 Qualification Round 自分の参加記録

問題概要

各要素がM以下の正整数列が与えられる.要素数はN以下.全部が同じ要素ってことはない. 全てyだけ加えると,全部がTの倍数になる. Tが最大になるような,最小のyを求める問題. small: Nは10^8以下,Nは3以下.
large: Mは10^50以下,Nは1000以下.

解法

Tの最大値は各要素の差のGCDになる.
多倍長が必要な問題.

Cによるスパゲッティなソースコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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