Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-01-16

Topcoder SRM529 Div2 反省

| 09:52 | Topcoder SRM529 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Topcoder SRM529 Div2 反省 - iwbtr - kmats Topcoder SRM529 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 215

Points: 535.17

Solved: 2 (250, 00:07 / 500, 00:27)

Rating: 745 -> 875 (+130)

割と良かったけれど緑に届かず.

HardでN == 0 || N == 1を考慮していない人が割といたのにChallengeで先を越されてしまったのが残念.


529 Div2 250

チェスの駒(ポーン)が1次元配列a上(size <= 20)に並んでおり,駒は配列の先頭(a[0])を目指して以下の条件で移動する.

  • 1度に移動できるのは1マスだけ
  • 2つペアの時のみ移動できる
  • 移動すると,駒は1つにまとめられる

この時,できるだけa[0]に駒を集めた時のa[0]の値を答えよ.というもの.

配列int a[n]の末尾から駒の数a[i]を見て,a[i-1] += a[i] / 2を繰り返せばいいだけ.


529 Div2 500

歴代の王の名前を辞書順にソートする.ただし,王の名前の末尾にはスペース1つの後にローマ数字が書いてあり,同じ名前の王の場合は数字が小さい方を優先する.

王の名前自体はvector< string >に格納されているので,普通にソート

各要素(王の名前)の比較時には,名前部分string aとローマ数字部分string bに分ける.

まずはa同士で比較して,違う名前ならその結果を返す.

同じ名前なら,今度はb同士を比較.

ローマ数字は1~10がI, II, III, IV, V, VI, VII, VIII, IX, X, 20, 30, 40, 50がXX, XXX, XL, Lとなっている.

これらを文字数で区別すると,

  • 4: VIII
  • 3: III, VII, XXX
  • 2: II, IV, VI, IX, XX, XL
  • 1: I, V, X, L

となる.後は文字数が大きい方から優先してローマ数字列bを先頭から比較していけば,bの値が求められる.

後は,求めた値同士を比較してその結果を返す.

文字数を小さい方から比較していくと,"IV"を4ではなく"I"+"V"の6としてしまうなど,正しい結果が得られない.

以上の方法だとローマ数字の変換部分の記述が面倒だが,愚直な処理なので分かりやすい.

Div1 Easyと同じ問題で,特にDiv1の方ではもっとスマートな方法で解いた人が多いようだけど・・


529 Div2 1000

人工知能界の大物マービン・ミンスキーさん登場.

問題自体は,与えられたアルゴリズムと同等な,かつ計算量の小さいプログラムを書け,というもの.

とりあえず問題文に載ったアルゴリズム写経し,その後色々考えるも時間切れ・・

submitした人自体60人もいなかったらしく,割と難しい方だったのかも.

更に,submitした人の多くが,N == 0 || N == 1の場合はreturn -1するのを忘れており,ここで大量に撃墜されていた.

自分も撃墜するぞと意気込むも,ソースコードを見ている内に撃墜されるということが2回・・

0もしくは10^12を突っ込む準備はできていたのに,いざソースコードを開くとそのあまりにも行数の少ない回答に面食らってしまったorz

ああ勿体ない,勿体ない


反省点

  • challengeフェイズでチャンスを逃した

教訓

  • 他人のコードをみても驚かない
  • 確実にいけるのを確認してからでなく,多分いけそうと思ったらchallengeする