hotpepsiの練習帳

Google Code Jam 2017 Qualification Round

00:31

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

Problem A. Oversized Pancake Flipper

問題

• N個のパンケーキがある
• パンケーキの表裏の向きが与えられる
• 連続したK個を裏返せる
• 裏返す総回数を求める

方針

• 先頭が表で、次が裏のとき、先頭で裏返すと永遠に揃わないので、先頭が表なら無視し、裏なら裏返す
• ClojureとHaskellで
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_A.clj
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_A.hs
• 終了後: golang, Rust
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_A.go
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_A.rs

Problem B. Tidy Numbers

問題

• 数の各桁が非減少なものをtidy numberとする
• 数Nまでの範囲の最後のtidy numberを求めよ

方針

• 一番下の桁から
• ひとつ上の桁よりも小さければ、その桁を9にして、一つ上の桁を一つ減らす
• Objective-CとSwiftで
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_B.m
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_B.swift

Problem C. Bathroom Stalls

問題

• N個のマス目があり、初期状態では全てのマス目が空いている
• 最も連続で空いているマス目の中央を埋める
• ひとつずつ、K個のマス目を埋める
• 埋まっているマス目について、左側の連続する空きマスの個数の最小値と、右側の連続する空きマスの個数の最小値を求めよ

方針

• 最初は中央に一つだけ配置する
• そうすると場所が2分割される
• つまりどんどん2分割されていく
• 残りの場所がR個で、D分割されていて、K個を配置することを考える
• K>Dならば、D個の領域全てを2分割して、RとKからD個減らし、Dを2倍にする
• K<=Dのときは、大きい領域のうちK個に配置することになる
• 領域の大きさはR÷DかR÷D+1で、R%D個までは1大きい、すなわちKがR%D以内なら1大きい
• GoとRustとPerlで
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_C.go
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_C.rs
• https://github.com/firewood/topcoder/blob/master/gcj_2017/QR_C.pl

Problem D. Fashion Show

要復習

結果

がんばって7言語で書いたが、よくわからないやつはC++で解いてから書き直しているので、効率が良くない。ちゃんとその言語にあった書き方ができるようにしたい。

Cはkmjpさんの読んで、mapでメモ化するのはわかりやすかった。しかしこういうのを関数型言語で書ける気がしない。

TCO17 Algorithm Round 1A

13:37

Easy (250) PingPongQueue

問題

• 何人かで卓球をする
• 一列に並び、2人ずつ対戦する
• 各自の実力が配列skillsで与えられる
• 実力が高い方が必ず勝つ
• 負けるか、連続でN回勝ったら列の最後に並ぶ
• Kゲーム目の対戦カードを求める

方針

• シミュレーション
• Passed System Test

https://github.com/firewood/topcoder/blob/master/tco_2017/PingPongQueue.cpp

Medium (500) CheeseSlicing

問題

• A×B×Cの大きさのチーズを切る
• どれかの面に平行に切る必要がある
• 切断後の長さが整数の値であること
• 3辺のうちいちばん小さい値を厚みとする
• 残りの辺の積をチーズの面積とする
• 厚みがS以上の塊に切るとき、面積の合計の最大値を求める

方針

• 3辺それぞれの切り方をDFSで全部試す
• メモ化

• Passed System Test

https://github.com/firewood/topcoder/blob/master/tco_2017/CheeseSlicing.cpp

結果

216.52 + 311.48 = 528.00pt 233rd/886 1686 -> 1676 (-10)

easyは「連続で」が抜けてたり、意外とchallengeの余地あったらしい。

https://togetter.com/li/1096655

SRM 711

00:06

Div1 Easy (250) ConsecutiveOnes

問題

• N以上で、2進数表記で1がK個連続する最小の数を求める

方針

• 1がK個連続している数(1 <<K - 1)をXとする</li>
• XとNの上から1ビットずつ見ていく
• Nが1ならXにも1を立てる(＝N以上にする)
• Nが0でXが1なら、Xのほうが大きいので終了し、仮の答えとする
• Xの初期値を1ビットずらして(2倍にして)全て試す
• 仮の答えのうち最小のものが答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_711/ConsecutiveOnes.cpp

結果

o-- +1 194.73 +50 = 244.73pt rating 1649 -> 1686 (+37)

とーらすさん記念の回。

方針が単純なのが良かった。無限ループする解を落として+1

https://togetter.com/li/1094091

SRM 710

23:51

Div1 Easy (300) ReverseMancala

問題

• マンカラはコマを穴から穴へと動かして遊ぶゲームである。ここではコマを石、穴をスロットとする
• N個のスロットがあり、円環状に並んでいる
• ゲームは1ターンずつ進行する
• 操作Aまたは操作Bのいずれかの操作が可能である
• 操作Aは、まずひとつ以上の石が入ったスロットを選び、石を全て手に移す
• 次に、時計回りで隣にあるスロットに、石をひとつずつ置いていく
• 石がなくなったら終了
• 操作Bは、まず石が一つ以上存在するスロットを選ぶ
• 次に、反時計回りで、石をひとつずつ取っていく
• スロットに石が入っていなかったら、そこに手持ちの石をすべて置いて終了
• 状態startとtargetが与えられる
• startからtargetにするための手順を求める

方針

• 何となく均等にできそう
• いろいろやってみるが終了
• (終了後)
• ある場所X以外からAの操作をひたすら実行すると、X一箇所に集めることができる
• Bの操作はAの逆である
• targetからXに集める操作を求めておいて、逆順にBを実行するとXからtargetにできる
• startからXに集める操作とくっつけて完成
• 逆順にするときはindexの値が最後に置いた場所になるので、そこを何とかする
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_710/ReverseMancala.cpp

結果

--- 0pt 42nd/226 rating 1683 -> 1649 (-34)

部屋で誰も提出できなかった珍しい回。連続プラス点が7回で終わってしまった。

マンカラは実在のゲームだったらしい。

https://togetter.com/li/1088982

SRM 709

00:36

Div1 Easy (250) Xscoregame

問題

• 配列Aが与えられる
• Aの各要素Yを任意の順番で選ぶ
• Xの初期値を0としてX=(X+(X XOR Y))を計算する
• Xの最大値を求める

方針

• 何となく大きい順のほうが良さそう
• next_permutationで全部試すのは無理
• 適当に2分割してお茶を濁す
• Challenge Succeeded
• (終了後)
• 下位6ビットの結果が重要なので、そこだけ見てbit DP
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_709/Xscoregame.cpp

結果

x-- +3 150pt 102nd/339 rating 1637 -> 1683 (+46)

違いが出る部分だけでDPするのはなるほどという感じ。

https://togetter.com/li/1083628