hotpepsiの練習帳

Google Code Jam 2016 Qualification Round

23:36

https://code.google.com/codejam/contest/6254486/dashboard

A. Counting Sheep

問題

• 数Nからはじめる
• Nの2,3,4,...倍を数える
• それまでに数えた数値に0から9まで全て出現したら終了
• 終了する数を求める
• 終了しない場合はINSOMNIAと出力する

方針

• 0はINSOMNIA
• 1以上はいつか必ず終了する
• 各桁Dごとに最初に出現する数を求め、それらの最大値が答え
• SmallはClojureで
• 無限リストを生成して、Dが出現する数をフィルタし、それの最初を取る
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_A.clj
• LargeはHaskellで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_A.hs

B. Revenge of the Pancakes

問題

• N枚のパンケーキが積まれている
• 表が+、裏が-
• 上から任意の枚数をひっくり返すことができる
• 全てを表にするのに必要な最小操作回数を求める

方針

• 一番深い-の位置でひっくり返していく
• SmallはJavaで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_B.java
• LargeはScalaで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_B.scala

C. Coin Jam

問題

• jamcoinは0か1だけからなる2以上の長さの数値で、2から10までのどの基数で解釈しても素数ではない
• 長さNのJ個の異なるjamcoinを生成する

方針

• 素数表を生成しておき、乱数で生成して判定する
• SmallはJavaScriptで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_C.js
• LargeはC#で
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_C.cs

D. Fractiles

問題

• 古代遺跡でタイルの列が発見された
• タイルはLとGの二種類ある
• タイルの列は、K個からなるオリジナルパターンと、複雑さCから生成される
• 複雑さ1の列は、K個のパターンそれ自身
• 複雑さX+1の列は、複雑さXの列から生成される
• X列の1個のタイルLは、K個のオリジナルパターンに置換される
• X列の1個のタイルGは、K個のGに置換される
• タイルは汚れていて判別不能で、S個だけきれいにできる
• 列に少なくとも1つのGが含まれているかどうかを知るため、何番目のタイルをきれいにすればよいかを求める

方針

• SmallはK=S
• オリジナルパターンの左端がLの場合、左からK個は常にオリジナルパターンとなる
• なので、左端のK個をきれいにすればGが含まれているかどうかわかる
• Goで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/QR_D.go
• Largeは未着手

結果

ooooo-

昼からやって半日かかってしまった。Goが難しかった。

http://togetter.com/li/960339

SRM 687

22:49

https://competitiveprogramming.info/topcoder/srm/round/16708/div/1

Div1 Easy (250) AlmostFibonacciKnapsack

問題

• フィボナッチ数列っぽい数列が与えられる
• A[1] = 2
• A[2] = 3
• A[n] = A[n-1] + A[n-2] - 1
• 数Xが与えられたとき、この数列の異なる要素の和で表せるかどうかを求める

方針

• ???
• (終了後)
• 2以上の任意の数が作れるらしい
• Xから貪欲に引いていけばいいが、残りが1にならないようにする
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_687/AlmostFibonacciKnapsack.cpp

結果

0pt 296th/395 rating 1533 -> 1429 (-104)

全くわからなかった。普通のフィボナッチ数の和でも任意の数を表せるらしい。

http://togetter.com/li/959779

SRM 686

23:12

https://competitiveprogramming.info/topcoder/srm/round/16690/div/1

Div1 Easy (300) BracketSequenceDiv1

問題

• ()と[]だけからなる文字列がある
• 0文字以上削除して、1文字以上にする
• きちんと括弧が閉じるのは何通りか求める

方針

• 半分全列挙
• まず左半分と右半分にわける
• 左半分について、残す・削除するをビットで表す
• 残った部分について、1つずつ処理していく
• 括弧の対応関係がおかしければそこで終了
• 一つ前のものに対応していたらひとつ消す
• 消えない場合は、括弧の種類を2ビットで表して(ビットシフトして)蓄積させていく
• 最終的に残った対応関係を記憶する
• 右半分は、文字列と文字を反転させて、左半分と同じ処理をする
• 同じ値同士のものが結合でき、かけたものが組み合わせの数になる
• 合計が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_686/BracketSequenceDiv1.cpp

結果

o-- 136.81pt 119th/283 rating 1488 -> 1533 (+45)

一年ぶりに黄色。

半分全列挙なら解けそうだったので愚直に書いた。この方針だとやるだけといえばやるだけだけど、正しく書けたのは良かった。

http://togetter.com/li/955714

TCO16 Algorithm Round 1A

22:31

https://competitiveprogramming.info/topcoder/srm/round/16701/div/1

Easy (250) EllysTimeMachine

問題

• 短針と長針の時間を入れ替えることができるタイムマシンがある
• 与えられた時刻に対する変換後の時刻を求める

方針

• 変換するだけ
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2016/EllysTimeMachine.cpp

Medium (500) EllysSocks

問題

• N本の大きさの異なる片方の靴下がある
• それらを2つずつ選びPペア作る
• ペアの大きさの差を最小化するとき、最小値を求める

方針

• 二分探索
• 差がDのときにペアがPできるかどうかを評価する関数を用意
• Passed System Test
• (解き直し)
• ソートしておき、隣接するものでペアを作ればいい
• https://github.com/firewood/topcoder/blob/master/tco_2016/EllysSocks.cpp

結果

oo- 231.52 + 334.14 = 565.66pt 301th/913 rating 1489 -> 1488 (-1)

easyは12時の扱いで結構落とせたみたい。撃墜ケース用意しておけばよかった。

http://togetter.com/li/954810

SRM 685

00:50

https://competitiveprogramming.info/topcoder/srm/round/16689/div/1

Div1 Easy (250) MultiplicationTable2

問題

• [0,n)の数の集合Sがある
• Sの任意の要素i,jに対して演算(i $ j)を定義する
• Sの部分集合をTとする
• Tの任意の2要素の(i $ j)が常にTの要素となるとき、Tの最小の大きさを求める

方針

• 任意の数xを選び、xと(x $ x)を計算用の集合sに足す
• sの任意の2要素a,bの(a $ b)がsに含まれなければ足していく
• [0,n)のそれぞれについて上記を試す
• sの最小値が答え
• Passed System Test
• (解き直し)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_685/MultiplicationTable2.cpp

結果

o-- + 1 117.41 + 50 = 167.41pt 219th/421 rating 1474 -> 1489 (+15)

dfsという関数名で書いたが、足せるものがなくなるまで足すのはDFSではない気がした。

http://togetter.com/li/951927