Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2009-02-08

SRM 434

22:45

  • 250 System Test failed.
  • 400 System Test failed.
  • 1000 Opened.

零点ktkr\(^o^)/

250 pts.

1 x 1の入力ケースに全て-1と答えていました。id:nishio, id:cafelierと同じく。

落ちた直後は何故落ちたか理解できず、平方数判定がおかしいのかと思っていました。私の平方数判定はだいたい次のとおりです。

bool isSqr(LL value) {
 double rt_d = sqrt(value);
 LL rt = int(floor(rt_d + 0.5));
 return rt * rt == value;
}

何人かがこのコードよりちょっと複雑な、rtの周囲±2のあたりまで確認するコードを書いていたので、私のコードだけでは何か不足があるのかと勘違いしていました。

この問題の場合、valueは10^9より小さいので誤差が出ることはないはずです。

500 pts.

36進数の計算。

「36文字種のうちk文字種をZに置き換えて、和が最大になるようにする」を、「k文字をZに置き換えて〜」に空目していくらかロスしました。

結局方針は以下のとおり。

  • 36進自然数を実装。
  • 入力をとりあえず全部足す。
  • 各文字種について、それを'Z'に置き換えたときの和の増加量を計算する。
  • 増加量のうち大きいほうK個だけを足す。

System Testの以下の例に撃墜されました。

numbers =  {"ZACKZAGSZANYZAPSZARFZATIZEALZEASZEBUZEDS",
            "ZEESZEINZEKSZELSZEPSZERKZEROZESTZETAZEZE",
            "ZHOSZIFFZIGSZILAZILLZIMBZINCZINEZINGZINS",
            "ZIPSZITEZITIZITSZIZZZOBOZOBUZOEAZOICZOLS",
            "ZONAZONEZONKZOOMZOONZOOSZOOTZORIZOUKZULU"};
k = 2;

調べたところ、'Z'を'Z'に置き換えたときの増加量が'0000000000000000000000000000000000000000'になっていました。これは0と同じですが、長いためにほかの数字より大きいとみなされていました。

正直、BigInteger無双でした。Javaが足りない。

今のところの障壁はまずテンプレートがないことです。

調べたところ、ExampleBuilderを使うといいらしいです。TZTesterだとだめなのかしら。

1000 pts.

難しい。一見して解き方がわかりませんでした。

  • ある程度の時間でimpossibleかsolvableか判定できる判定ルーチンを作る。
  • solvableなら、端から辞書順に?を他の文字で埋めてゆく。

こんな感じで解けるようです。

 |