Hatena::Grouptopcoder

敗戦記

2011-03-08

Codeforces #61 (Div.2)

| 11:48

自分にしてはかなり良かった回。

DIV2 ROOM10

A

  • 開く。一瞬文字列を使うか迷う。
  • 取り敢えず、long long c;if(cin>>c)でBigIntegerを判別し、LLONG_MAXとかを使ったら書けた。

8分

B

  • 読む。かなり前に授業で扱ったhttp://poj.org/problem?id=2227をなんとなく思い出す。
  • n<=1000ということでTLEも心配なさそうなので、n^2で普通に書いて出す。

15分

C

  • 開く。構文解析だったので微妙に張り切る。
  • 何だかメール配達(http://codeforces.com/problemset/problem/56/C)のやつに似ているな、というようなことを思いながら書く。
  • どうも上手くいかなく、Dを解いている人のほうが多かったので一旦Dへ。

D

  • 読む。素数を小さい方からp1,p2,p3・・・としたときに、p1*p2,p2*p3,p3*p4,・・・って出力すれば、いいのかとか考える。
  • 書くとREになる。
    • 確保する配列のサイズが小さかった。
    • 訂正するとWA
  • もう一回問題文を見ると、全てのi,j(i≠j)についてgcd(ai,aj)≠1とか書いてあった。
    • どうしよう。
    • ai=p1*p2*p3*・・・*p(i-1)*p(i+1)*・・・*pnにしようと結論が固まる。
    • ついでにn=2の場合はだめじゃないかな、ということにも気づけた。
    • 書くとプリテスト通過。

63分

  • ちょっと待てよ。と思う。

68分

Hack

  • Dで多倍長とか、n=2とかの見落としがないかと思って一人開く。
    • 素数を全列挙してない人がいたので50を投げてみたけれど普通に失敗した。
    • あれ、多倍長使わなくても解けるのか?
  • 一旦Cへ。

C

  • 戻ってくる。
  • あまり考えがまとまらないながらもゴリゴリと書く。
  • プリテスト通過。

82分

Hack

  • Dで、同じ方針で多倍長使っていない人が居たので50投げて落とす。
  • Aで、-を考えていない人がいたので落とそうと思ったらInvalid inputとか言われる。
    • この時始めてAは正の数しか与えられないことに気づく。
    • 結構-を考慮している人が多かった。
  • Dで素数全列挙かつ、多倍長使ってないとか、n=2を考慮してない人とか探したけれどいないので、取り敢えずEをみようと思う。

E

  • 多倍長持ち言語に嫉妬しながら開く。
  • 何とか問題の意味を把握。
  • 残り30分弱だったので、TLE解法でハックを狙うか、真面目に考えてO(n^2)より小さい解法が思い浮かぶか天秤にかけた結果、TLEを狙うのが得策だろうという結論に。
  • 書く。
    • 反対周りの考慮忘れてた。
    • 書く。反対周りがバグっていて、若干焦りながら修正しつつサブミット。
  • プリテスト通過。

110分

Hack

  • Eを見るとn^2解法の人が居たので、ジェネレーターを書く。
    • 性格悪いな自分、と思いながら投げて三人落とす。
    • 終了直前に駆けこんできた人がいて助かりました。
  • Dでn=2を考慮していない人が居たので二人落とす。
  • 最終的に+550

System Test

  • ○○×○×。
  • Cは通るか微妙かと思いっていましたが、構文解析の解析位置の移動の仕方が間違っていたようで、やはり落ちました。
  • Eはハックするためだけに書いたようなものなので、まぁ、落ちます。

感想

  • 一応部屋一位で、DIV2 65位でした。青い人もいた中では健闘できたほうだと思います。

1477 -> 1686 (+209) 紫になれました。多分またDIV1回では落ちると思うので、しばらくはDIV2オンリーもratedで出られてしまう気がします。