eomole as a contestant

TCO 2014 Qual 1A

SRM | 19:59 |

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 みたいな感じなので微妙い。

ツイートする