■ [SRM][本番]SRM464 
2010-03-16 24:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14149&rm=303858
日本人が4人もいる部屋はたぶん初めて
| Level | タイトル | 試合中 | あとで | ひとこと |
|---|---|---|---|---|
| DIV1 250 | ColorfulStrings | AC 15min | - | 算数+実装。好きなタイプの問題 |
| DIV1 550 | ColorfulDecoration | Opened | - | さっぱりわからなかった。グラフは知識もセンスも不足 |
| DIV1 1000 | ColorfulMaze | UnOpened | - | - |
- Coding
- 250
- をを、入力範囲でかいぞ、どうしたら…
- これはいつもの250よりだいぶ難しめに違いないのでじっくり問題を把握する
- Colorfulかどうかの判定には1桁だけの部分も使うんですね
- ということは同じ数字は2回以上出てこないので、n>=11 の場合は return "" でよい
- あとは0123456789のpermutationを調べるだけ…？
- しかし1回の判定がそれなりに重いので 10! はけっこう厳しくないか
- あ
- 2桁以上の場合に0を含んでると、連続数字の積に0が複数回出てくることになるのでだめですね
- ただし1桁の場合は別。チャレンジポイント
- あと、kが1始まりなので、n=1,k=10 （答えは"9"）でミスって""を返しちゃってる人がいるかも
- というわけで 9! ならたぶん大丈夫…かな…？ まあ書いてみよう
- 1〜9からn個使うpermutationを効率的に列挙するには
- next_permutation使うと泥沼になりそうだったのでシンプルに枝刈り再帰で
- あとは頑張って書くだけ
- 書いた、最大ケースも0.3秒で終わる。セーフ
- 提出
- 0と同様に1も使えないことはコード書いている最中に気づいたが、計算量は問題なさそうだったのでそのままにしといた
- 550
- 図がやばげ
- 答えの取り得る範囲から二分探索かもとは思ったが
- ある解候補に対して、その制約を満たす配置があるかどうかをどうやって判定できるかが全くわからない
- 焼きなましてやろうかと一瞬考えるなど
- あまりにわからないので歯を磨いたりしていた
- 250
- Challenge
- 250でわかりやすいコーナーケースがあって赤4人部屋なので撃墜は秒単位の争いになりそう
- 1つ取れればラッキーというくらいか
- と思っていたらそんなでもなかった
- 250のn=1で落ちる人が次々と3人見つかって撃墜成功
- ラスト20秒でもう1人非常に怪しそうな人を見つけて悩むも結局チャレンジせず
- やはりシステムテストのn=1なケースで落ちてた
- しかし確信は持てなかったので自重したのは正解だと思う
- System Test
- スコア：198.83 + 0.00 + 0.00 + (50*3-25*0) = 348.83
- 順位：92位/720人
- レート：1829→1915
連続2桁は初めて
