hotpepsiの練習帳

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はじめて使った。楽ちん。

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