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でメモ化するのはわかりやすかった。しかしこういうのを関数型言語で書ける気がしない。