hotpepsiの練習帳

Google Code Jam 2015 Round1B

01:56

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

Problem A. Counter Culture

問題

• 1からNまでを順番にカウントする
• ただしズルができる
• 各カウントにおいて、一つ前の番号の+1か、桁を逆転したもののどちらかを選べる
• カウントの総回数の最小値を求める

方針

• 1000から10000を作ることを考える
• 1009を逆転するより1099を逆転するほうが良い
• という感じで、目標となる桁になるまでは、今の桁の半分までを埋めてから逆転する
• 目標となる桁になったら、端の桁から順番に、逆転したほうが有利かどうか調べていく
• https://github.com/firewood/topcoder/blob/master/gcj_2015/R1B_A.cpp

結果

Aのみ 25pt 1503rd

Aだけで二時間くらいかかってしまった。難しかった。

http://togetter.com/li/815961