2014-04-13
TCO 2014 Qual 1A
SRM | | 
1週間延期されたのがあった。
去年の TCO 予選シーズン以来 TopCoder に出ていなかったのでかなり久々。
Easy: 文字列に対して適当な prefix を切り出して suffix N 文字をソートという処理を繰り返して辞書順最小の文字列を作る問題。Prefix の選び方は1文字ずつ前進で N 文字になるまで限界まで続ける戦略が最適であるのが、考察するとわからなくもないのでそれを実装するとよい。もう少し効率よくするなら、先頭 1 文字を除いてソート、先頭 N 文字を切り出してソートが最終結果なのでそれを実装すればよい。全体ソートして先頭 N 文字を切り出すという嘘解法にたどり着きやすいけど "TOPCODER" で落ちるので、サンプル親切だった。
Mid: 文字を並び替えて辞書順最小の文字列を作る問題。ただし、元の位置から N 文字以上離れてはいけない。これは先頭から使える文字を貪欲に置いていけば OK。ただし、その場所を逃すと制約を満たさなくなるという文字が生じたらそれを置かないといけないことに注意する。
Hard: よくわからなかったけど 8N くらいの DP でいいらしい。
Challenge: 灰色さんが "TOPCODER" で落ちるはずの嘘解法を提出していたので3人くらい落とした。(実のところ1人目はTLE狙いだった。枝刈り落とそうとしてしまうのやはり辞めた方がいい。まあ結果オーライ)サンプルくらいチェックしようね？
3 年前の TCO の時期のレートを超えて highest 更新。あと部屋 1 位で div で獲得した最高のスコアだったらしいけど、div 1.5 みたいな感じなので微妙い。
GCJ 2014 Qual
Other | | 
Template を Java 8 にバージョンアップして出てみた。というより template 更新ばかりに時間をかけて危うく時間切れになるところだった。。とはいえ並列ストリーム以外は全然使ってないけど。
A: やるだけ。もうちょっと詳しく説明すると、 4 行 4 列の行列が 2 つあるのでそれぞれから指定された行を抜き出して一致する数字はいくつありますか？1つならその数字も教えてねという問題。まあ、登場人物は盤面を90度回転させればよかっただけのになぜそうしなかったのか、謎である。
B: クッキクリッカーで所定の枚数を最速で集めるには？ただし、施設は農場だけで(ばーさんもいない)、さらに連続時間モデル。建てる施設数をパラメータに最適化すれば良くて多分凸性もありそう。なんか制約から線形探索で良さそうな気がしたのでそれ投げてしまったけど通った。でも、あとでよく考えてみると C=1, F=1, X=100,000 とか渡されるとヤバイことに気付いた。これだからランダム入力は…
C: 盤面のサイズと地雷の数が与えられるので、1 クリックで終了できるような盤面を生成する問題。Small は全配置を生成してそれぞれ 1 クリックで終了できる位置がないか調べた。Large はそれでは無理なので、左と上に幅 3 の領域を残して角にクリックポイントを置き、残りの部分に規則的に埋め、次に幅 3 の領域に規則的に並べて、最後に残った 3x3 は全探索した。3x3 の領域に離接する外側のタイルでアドホックな場合分けを入れたので、そこで撃墜できそうな予感だったけど、落ちなかった。ランダム入力さまさま…
D: 問題文に警告が出ているように理解するまで時間のかかる問題。詐欺プレイをするときは釣りができるので、Ken の各おもりりに最大までそれに勝てる自分のおもりを割り当てることができる。一方、しないときは自分の持っているおもりの重さしか伝えられないので、避けられないとき以外は Ken によってそれより小さい重さのおもりが 1 個ずつ消費されてしまうので、残りが答えとなる。
結局全部通って満点 90 点でした。
