Hatena::Grouptopcoder

hotpepsiの練習帳

2011-12-18

Codeforces 97 Div2

17:28

登録だけはしていたが初参加。

A Presents

問題

  • プレゼントを渡す先が配列で与えられる
  • 誰からもらったかの配列に変換して返す

方針

  • 特にひねりなし

B Ternary Logic

問題

  • 3進数のXOR
  • A XOR B = CにおいてAとCからBを求める

方針

  • 1桁の中で引き算すればよい
  • 「複数の解があれば」とあるが、一意なので存在しないはず

C Replacement

問題

  • 1以上の整数からなる配列が与えられる
  • そのうちの1つだけ変更したもののうちの最小のものを求める
  • 必ず1つだけ変更すること
  • 違う数値に変更しなければならない

方針

  • 最大の数を1に変更する
  • しかし1しか含んでいない場合は、末尾を2に変更する
  • 0-based indexで先頭に1を入れておく
  • 1-based indexでもらったものをソートして入れて、末尾を消す
  • 全部1の場合だけ特別扱い

D Rectangle and Square

問題

  • 8つの点が与えられる
  • 4点で正方形、残りの4点で長方形(または正方形)ができるかどうかを求める

方針

  • 本番中は任意の2点から辺を作って判定
  • system test failedのため解きなおし
  • next_combinationで4点を選ぶ
    (next_permutationでも40320回なので、TLEしないかも)
  • 判定回数は8C4=70回
  • 4点の重心(中央)から4点までの距離が全て等しければ長方形(または正方形)
  • 両4点が長方形のとき、最初のものが正方形ならOK
  • 正方形かどうかは、任意の2点と残りの2点が交差するかどうかで判定
    これにもnext_permutaion使った。

結果

ooox- 2642pt 380th ratings 1568

pretestは親切設計。Cの全部1のときはpretestがなかったら気がつかなかった。

Dはnext_permutationでも十分間に合うと計算すべきだった。

next_combinationはじめて使った。楽ちん。

後半にいくほど問題文のストーリー性がなくなっていくのが面白い。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20111218