Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-12-05

MazeMaker (SRM453.5 DIV1 Easy)

| 01:12 | MazeMaker  (SRM453.5 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MazeMaker  (SRM453.5 DIV1 Easy) - TopCoder煮ブログ

本番前の練習。あらかじめ与えられた迷路とスタート地点でどこにゴールを設置するとクリアに時間かかるようになるか。迷路をうろつく人の移動パターンがあらかじめ与えられている。

当然、総当りはダメなので悩んだが、スタート地点固定で最大距離を求める、ということなのでダイクストラ法で解けることに気づいた。あとは書いていくだけ。Row/Column を x/y に置き換えて書き始めてしまってかえって混乱してしまった。ダイクストラは queue 使えば簡単だということを覚えてたので TopCoder やる前よりかは早く書けるようになってるかも。

無駄は多かったが 264.75pt/500.0pt の時間で submit(DIV2 Midium のほうで解いたので)。System Test も一発で通った。C++ 一位の人のソースと見比べたらシンプルさでは負けるものの方向性は同じだった。

SRM454 DIV1

| 03:50 | SRM454 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM454 DIV1 - TopCoder煮ブログ

4ヶ月ぶりの参戦。いつも通りなスコア

13731394

211.67pt (○××) 383位/699人

DoubleXor (Easy)

新しい演算子 ^^ を定義したときに N^^(N-1)^^…1 を計算しろ、という問題。左結合なので毎回計算しなきゃいけない。何か法則があるのかと悩んだが、素直に計算しても時間的に問題はなさそうだったので素直に計算して submit。211.67pt。

Challenge Phase で xor したあとに %10 するのを忘れてる人をみつけたが撃墜パターンを考えようとした瞬間に Challenge Succeeded になってて何もできなかった。同じ部屋だった id:cafelier さんがやっつけたようだ。

NumbersAndMatches (Midium)

DP っぽく解くには方針が思いつかないし、DFSっぽく解くには状態列挙で死にそうになった。1時間かけても解けないし、Challenge で他の人がどうやって解いてるのか見ても分からんし悲しい。この手の問題が解けないと yellow 浮上は遠い。

メモ:

MegaSum (Hard)

みてもいない。