Topcoderの過去問をやってみる

とりあえず登録した。過去問リストの一番上にあったConvertibleStringsなる過去問をやってみることにする。

問題

いきなり問題文が結構長くて嫌になったがGoogle翻訳を見ながら読んでみる。適当に訳すとこんな感じか?

文字 [A-I] からなる2つの文字列 X, Y があり、X 内のそれぞれの文字を [A-I] の順列で置換して Y に一致させられるなら、X, Y は convertible である。 文字列 A, B が与えられたとき、双方から同じ位置の文字を消し続けて2つの文字列を convertible にすることができる。このとき消さなければならない文字数の最小値を求めよ。

例えば "ABCA" と "FBGF" は 'A'->'F', 'C'->'G' の置換で一致するから元々 convertible であり、消す文字数の最小値は0。"ABCA" と "EFGH" の場合、'A' が対応する文字が2つあるため convertible ではなく、文字を1つ消す必要がある。

解答まで

少し考えてみたが全然方針が立たなかった。1つの文字に複数の文字が対応してるならどこか消さなきゃならないってのは明らかだけど、絶対最小になる規則は思いつかない。一番多く出現する文字から処理するとか考えたけど、それで最小値が得られる証明しろと言われるとお手上げ。一応怪しげなコードを出してみたけど余裕でシステムテスト落ちた。

考えてたら眠くなってきたので一回寝た。

起き抜けの頭で部分問題に分割できねーかとか考えたけど妄想だった。んで自分の頭の悪さを呪ってたら「もう全探索でいいんじゃね?」という声が聞こえた気がしたのでそうすることにした。文字は [A-I] で9個しかないんだから、その順列は 9! 通り。9! は大体36万だから何とかなるだろう。

でPythonで書いてみたんだが、TopcoderってPython2なんだな…。適当に直してテストしてみたら最後のケースでタイムオーバーした。

しゃーないのでC++で書くことにする。C++は英語と同じくらい嫌いだけど一応文法程度は知ってる。順列生成ってどうすんだっけと思ったけどライブラリにstd::next_permutation() てのがあったのでこれを使うことにする。適当に書いて出してみたらなんかまたシステムテストで落とされた。全探索してんのに落ちるってどういうことだ…。

システムテストの内容がわからないのでどうにも困った。本番なら仕方ないが練習なんだからそれくらい見れてもいいんじゃないのか…?と思って調べたらどうもシステムテストの内容を取ってくるツールはあるらしい。gettcてのが便利そうなので入れてみることにした。以下のようにしてインストール(僕はRuby使いじゃないので正しいかどうかは知らない):

$ export GEM_HOME="$HOME/.gem"
$ gem install gettc

で、このツールに問題IDを与えるとシステムテストを取ってきてくれるのだが、問題IDがどこにあるのかわからず少し手間取った。どうもURLの最後から3番目の数値が問題IDらしい(問題文だけ書いてあるページのURLを見れば問題IDが書いてあるのだが、そもそもこのページへのリンクが見つからなかった)。以下のようにしてデータを取得:

$ ~/.gem/bin/gettc 12754

このツールはかなり親切で、システムテストを取ってくるだけでなく make で自動テストができるところまでお膳立てしてくれる。これでテストしてみたらところどころ答えが間違ってたので、順列生成に問題がないかカウントして調べてみたら 9! になってなかった。どうも sizeof("ABCDEFGHI") をそのまま使ったのが敗因ぽい(最後のNUL文字を除く必要がある。これだからC++は嫌なんだよな…)。直したらWeb上のシステムテストまで通った。

一応最終的なC++コードを貼っておく。

後記

一応後からPython版も提出してシステムテストにかけてみたがFailedになった。ローカルで試すと答え自体は全部合ってるんだけどな…。Web上だと答えが違うのか時間が足りないのかわからんてのは結構きつくないか?

あと、Python2が指定されてるのはやっぱりきつい。もうローカル環境はPython3で統一しちゃってるので今更戻りたくない。他のサイトだとPython3が使えるところもあるようなので調べてみようと思う。なお、gettcはなぜかPython3を使うようになってるのでTopcoder側と整合性がなく、手で修正してから提出する必要があるっぽい。

今回一応システムテストは通したが、正直これって解いたうちに入らんような気もする。文字が9種類しかないから全探索でも何とかなったけど、この解法はスケールしない(文字の種類がちょっと増えただけで破綻する)からクソだと思う。多分出題者が僕みたいな雑魚でも解けるように配慮したんだろうけど、それに乗っかってたら負けだよな…。

ということで文字の種類を増やした問題を生成してそれを解くのもやってみようかと思う。

てすと

頭が悪すぎるのでせめてミジンコ目指して色々やろうと思います