SRM612

R1288でDivision1に参戦。最近CheckiOやコンサルの仕事などでPythonをよく使っているのでPythonで参戦。

JavaだとKawigiEditというプラグインが便利なんだけどPythonGreedというのが便利そうなのでそれを入れて開始前に2問くらい解いてた。

Easy

顔文字1個から出発して「1文字削除」、「クリップボードへコピー」、「ペースト」の組み合わせだけでちょうどN個にするのに必要な操作の最小回数を求める問題。N<=1000が条件として与えられている。まずは問題分析としてDP的な方法を考えたが「1文字削除」のことを考慮すると「文字数が1000を超えるような中間状態」を考慮しないといけなくて面倒だなと。たぶん倍の2000ちょっとくらいでDPすれば大丈夫なんだろうけどもっとシンプルに出来ないだろうか考えてたら、操作回数でイテレーションしてダイクストラ法みたいにやればいいのだとひらめく。それならシンプルだ。ということで以下のようなコードを書いてテスト通ってサブミット。

    def printSmiles(self, smiles):
        tbl,Q={(1,0):0},[(1,0)]
        while Q!=[]:
            now,clip=t=Q.pop(0)
            if now==smiles:
                return tbl[t]
            ts=[
                (now,now), # copy
                (now+clip,clip), # paste
                (now-1,clip), # delete --- (*)
            ]
            for t1 in ts:
                if t1 not in tbl:
                    tbl[t1]=tbl[t]+1
                    Q.append(t1)

で、サブミット後に次の問題を読んでる途中に上のコードの一文字削除(*)のところで「顔文字の個数Nがマイナスの状態」を作り出してしまう事に気づく。やばい。TopcoderSRMは2回目のサブミットはペナルティが課されるので、なんとか上記のコードでNがマイナスの状態が途中にあっても操作回数の最小解には影響しないことを頭の中で証明しようと試みる。しかしちょっと難しそうなので、上記のコードをコピペしてちゃんとマイナスの状態を除外するやつを書いて、サブミットしちゃったやつと2<=N<=1000の範囲で出力が一致するかを確かめる。僕の最新のMacBookProでも1分以上掛かってドキドキ。出た!あってる!問題ない!
ということで次の問題へ。

Medium

50x50の座標空間上の点をN個選び、x座標、y座標に分離してx座標だけソート、y座標だけソート、という風にして渡されたときに元のN個の座標をどれだけ正しく推定出来るか、確実に推定可能な個数Tを求めなさい、という問題。
問題の意味はすぐ分かった。しかしEasyで手間取ったのでこの時点で残り40分くらい。図に置き換えて考えてみる。この場合座標の具体的な値は関係なく、個数が問題なので縦棒N個と横棒N個を個数ごとにまとめて交差させた図を描きながら考えていた。どうにかうまいほうほうはないものか。
しかしさんざん色々検討したけど「あり得ない複雑度のメモ化+全数探索」という方法くらいしか思いつかず、それでも時間オーバーしそうで書く気がしないままタイムアップ。

Hard

開いてない

結果&感想

Easyは通った。MediumはEgor神のコードを見てみたら思いっきりグラフのフロー最小化問題に置き換えてコピペプログラミングしててガクブルだった。割と多くのレッドコーダーがグラフ理論に置き換えてやっていた。

今回は問題の分析に掛ける姿勢は良かったと思うが、分析するときに「知ってる基礎アルゴリズム」の量が一定数無いといくら考えても答えは出てこないという事態になりがちだと思った。「ひらめきは知識の組み合わせ」なので、もとの材料がやっぱりある程度必要だなと。メジャーどころのグラフアルゴリズムは一通り覚えて、具体的な問題への応用を学ばないと。

あと、最近CheckiOをやって思ったのは、TopcoderSRMだけが「高度で面白いコーディング」じゃないということ。例えば、近似アルゴリズムTopcoderはマラソンマッチとかもあるけど)や機械学習ベイズ推定などのアルゴリズムとかいった数理的な素養がコアになるような分野とか、コード生成やLISPマクロのような分野とか、他にもいろいろな分野があるので、テーマを決めてそういうのも体で覚えるようにしていきたいなって最近思う。

R1288 -> R1372 自己ベスト更新。イエローコーダーまであと128点。3月中あと2回順調なら目標達成できるかも。頑張ろう。
http://community.topcoder.com/tc?module=MemberProfile&cr=23173042