TopCoder Open Round 1 - simezi

参加。仮眠しようと思ったら眠れなくて、開始頃にちょうど眠気がｗ
頑張ってストレッチしたり顔洗ったりして眠気を飛ばして参戦。

812位 231.53 / opened / unopened
0撃墜0ミス

1608->1576
ぎりぎりorzなんとか通過。

うげー赤4人の部屋。challengeやりにくそうだなー。

文字列s,tが与えられる。s,tの各文字を右または左に1文字ずらして(a->b,b->cなど。aとzはつながる）sとtを同一の文字列にしたい。

s,tの文字をずらす回数が最小で、アルファベット順で最初に最初にくる「同一の文字列」を求めよ。

問題文の意味がよくわからない。
sをtにかえるの？逆？
どうもサンプルを見るに違う。sとtを「共通のゴール」にもって行けという意味らしい。

で、s[i]とt[i]のアルファベットの中間はどれをゴールにしてもずらす回数の和は一緒なので

になるよね。実装。サンプル通った。

コーナーケース確認。"bbb","nop"あたりを。正しいね。送信。

二つのレジスタX,Yを持つ単純なコンピュータがある。
X,Yの初期値は1で、次の二つの命令が可能である。

このとき与えられた数rをレジスタXに作るための、長さ最小で、かつその中でアルファベット順で最初にくる命令列を求めよ。

r≦10^6である

うーんなんかユークリッドの互除法ライクな問題な気が……

最小の長さってどう求めたらいいんだろ。
フィボナッチ数とか使うんだろうか。

紙に書いて考える。全然規則性わからん。
探索プログラム書いてみよう。逆からメモ化探索。（←一意になることに気づいていない）
最小の長さを与えるYレジスタの最小値を出力してみる。

ふーむ。Xが素数のときは色々ある。Xに約数の多いときは少なくなる。
大体Yの値としてY/Xが(1+phi)になるようなのが含まれてたりするのか？？

なってないなあ。規則性が全然わかんねえ。
フィボナッチ数の項のときはフィボナッチ数を作ってくような命令が一番短くなるっぽいが、それ以外ってどうなるんだー。

みんな解いてる。あせる。
命令の最後はXに決まってるよな。
……だけど、そこから先なにもわからない。時すでに時間切れ。

unopened.

現在900位くらい。Round1の通過人数を調べる。850か……
System Testで絶対50人は落ちるし、1問チャレンジか0チャレンジノーミスでギリギリなんとかなるかも。

250間違っている人を探す。
間を全探索してる人がいる。頭いい。

距離13より小なら'a'に変えるという人がいる。これは自分と同じ方針。
これ実は12より小とかでもサンプル通るんだが、12にしてる人いないかなー。いないな。。。居ない。。

500が物凄い勢いで落とされてる。
あれ難しかったもんな！みんな嘘解法なんだろ！！（←強がり

自分も他人の500を色々と見るが方針あってるのかどうかわからないプログラムにチャレンジするとか頭悪いので眺めるだけ。

現時点で830位くらい。250通れ！！！！

通った。よかった。