読者です 読者をやめる 読者になる 読者になる

Google Code Jam 2017 Qualification Round

参加しました。英語はつらい。

 

Problem A. Oversized Pancake Flipper

+-+---+-+みたいな列に対して連続するK個の±を反転させる操作で全てを+にするには最低何回必要かという問題。但し操作する箇所ははみ出してはいけない。

 

左端から-があったらひっくり返す。右端まではみ出さないところまでやる。全部+になってたら回数出力。そうでないならIMPOSSIBLE

 

Problem B. Tidiy Numbers

N以下で、昇順になっているような数字(1234, 2333467888等)の最大値はいくつ?

 

Nを上の桁から順に調べていって、広義単調増加してる範囲をしらべ、なおかつ、広義単調増加している列のうち、最後に増加した場所を調べておく。

具体的には、22223344413とかだったら一番左の4の場所を覚えておく。

Nが昇順になっていなかったら、記録しておいた場所の情報を使って、その桁までは同じ、その桁は-1、あとは全部9みたいな数字を出力。

22223344413 → 22223339999

こんな感じ。後は微妙な例外を除去。10から始まる数字とかそういうやつ。

 

Problem C. Bathroom Stalls

N+2箇所の枠があって、左端と右端はすでに埋まっている。すでに埋まっているところとの距離の最小値が最も大きくなるようにK個埋めていくと最後埋める時に左と右に空いてる連続したスペースは何個になりますかという問題。

N=11の時はこんな感じ

K=0 o-----------o 

K=1 o-----o-----o

K=2 o--o--o-----o

K=3 o--o--o--o--o

2^m<=K+1<2^(m+1)となるようなKに対して、全体を2^mで分割して余りを意識しながら、、あとはゴニョゴニョやりました(日本語で書くの難しい)。

 

A~Cまでしか解いてないけど全部通ってたので良かったです。