Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2010-10-22

SRM 485 Div1

12:08 |  SRM 485 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM 485 Div1 - yehara のTopCoder日記

2回連続の 0 点。死にたい・・・

Level 1 (250)

最初の数列の各要素の偶奇を考える。全部偶数ということはありえないので(その場合は全体を 2 で割った数列からも同じ結果になり、そちらの方が優先度が高い)、奇奇奇奇・・・か、偶奇偶奇・・・か、奇遇奇遇・・・になる。なので、seq[0],seq[2] か、seq[1],seq[3] のどちらかの組み合わせは必ず元の数字のまま残っているはずである。そこから想定できる元の数列を最大 2 通り作ることができる(最大と書いたのは、想定数列が2つ同じになる可能性があるので)。そこから各要素を割れるまで 2 で割るオペレーションをして入力と一致したほうが解。

しかし、ここで 2 で割る処理を while(r[i]%2== 0) r[i] /=2; とか書いてしまって失敗。数値が 0 のとき無限ループに陥る。もともとの数列が [6, 7, 8, 9] のときに生成される数列は [3, 7, 1, 9] で、seq[0],seq[2] がもともとの数字が残っていると仮定したときの想定される元の数列は [3, 2, 1, 0]。0 が出現しうる。> 0 のチェックもいれておく必要があった。

Level 2 (500)

結構時間使ったけどわからなかった。大きいケースでは解がなく、探索範囲はかなり限定できるらしい。

Level 3 (1000)

みてない。

まとめ

2回連続の 0 点で rating 大暴落。(1604->1503->1402)。ついに青。まあぼちぼち取り戻していこう。

NEETNEET2010/10/23 01:13>奇奇奇奇・・・か、偶奇偶奇・・・か、奇遇奇遇・・・になる

あ、なるほど。頭いいですねー。まずbfsで全探索して例題は通ったけど、長い数列だと死ぬということで最初の3項(てきとー)だけbfsで探索して、あとはdiff=seq[2]-seq[1];として順に復元していきました。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20101022
 |