topcoderのSRM(Single Round Match)に参加した

はじめに

昨日(6/4)20:00からあったSRMに参加しました。SRMとはSingle Round Matchのことで，制限時間内に難易度の違う３問を答えて，その速さと正確性を競う個人の競技プログラミングのことです。結果は一つも解けませんでした。まだ解けていないので，今日からその問題をどうやって考えればいいのかを思考錯誤しながら書いていきます。

※もし問題を勝手に載せてはいけないとか，解答を載せてはいけないなどのルールがあるのであれば教えて下さい。すぐに削除します。

問題660 DIV2

実際の問題はこれです↓

まぁ英語なんですよ，，，えぇ，，，英語なんです。しかもコピペできないんで翻訳サイトにペチペチしました。

ただ毎回やることは決まっていて，ある入力に対して理想的な出力をする関数を作ればいいだけなんです。だから例が4つほど用意されているのでそれを見れば何をすればいいのかは雰囲気つかめます。その例がこれです（どちらかといえばこれらの例を全てクリアする関数を作ることが求められています）。

この問題の場合文字列と数値が与えられていて，数値の数だけ文字列を変換できる。そして変換したものを１文字ずつずらして行ったとき，辞書順で一番速い文字列はどれかってことです（たぶん）。最終的に辞書順なので変換後の文字は"a"になりますね。

わからない点

わからないのは"どの文字を変換すればいいのか"です。(1),(2),(3)をみるとアルファベット順で一番大きいのを"a"に変換していますが，(4),(5)はそうではありません。辞書的に並べたときに一番速い順になるように変換しています。

考えられる方法

全部調べる

とりあえず"a"以外の文字を数値の個数だけ変換した全部の場合を考えて，それらを辞書順に並べてときに一番速い文字列が求める文字列です。本番はもっと効率よくする方法を考えて，結局何もかけなかったです。ただこの方法をどうやってやるのかもわかっていないのでこれでやってみます。

※コードを書いていないので書けたらこのブログに貼っていきます。

今後

今回のSRMは，アルゴリズムが全くわからないまま時間が過ぎていったので，めっちゃ悔しかったです。「やべぇ一問もできねぇ＝＞勉強しよう」ってなりました。Project Eulerのようにじっくり問題を楽しみながら解くシステムもいいですが，SRMのように解けない悔しさを制限時間いっぱいまで感じさせてくれるシステムもまた面白かったです。