Hatena::Grouptopcoder

敗戦記

2011-04-14

Codeforces Beta Round #67 (Div. 2)

| 22:27

翌日は一限からでしたが試しに参加してみました。

前回、前々回がいろいろと酷い出来で凹んでいたので、満足のいく回で良かったです。

A

  • long longから0を省いてstring型にする関数と、stringを数字にする関数を書いた。

4分

B

  • 実装ゲー。
  • mapとか使いながら、pair<int,string>の配列にintをマイナスにしてつっこんでソートして出力した。

16分

C

  • 読む。最初TLEしない解法がすぐに思い浮かばない。
  • でも他の人達は即効で解いている人もいるので、そこまで難しくないのだろうと考える。
    • 最大公約数の約数を全列挙することにした。
  • あとは約数を-にして突っ込んだvectorをソートしてlower_boundした。
  • 提出した後に微妙にlong longを使っていなかったことにビクビクしていた。

36分

このあとDとEを読むが、Eは幾何なので無理で、DはTLEしない解法が思いつきそうになかったのでhack狙いで提出しようかなどと考えて取り合えずCのハックへ。

Hack

  • Cであきらかに一つのクエリにO(gcd(a,b))欠けている人が居たので落としました。
  • ここらへんでよくみると去年一緒にICPCに出てくれた先輩が同じ部屋だということに気づく。
    • ただ、Cで一つのクエリをO(gcd(a,b)^(1/2))で処理していて、これだと最大で1万×1万以上になり、ギリギリ間に合わさそうなので落とさせていただきました。

D

  • ここらへんであとは約数を全列挙しているものしか残っていないのでDのTLE解を書く。
  • 最小値を0にしたままだったのでプリテスト通らない。
    • 直してアクセプト

95分

Hack

  • 明らかに自分と同じ解法の人が居たので、急いでDのジェネレーターを書く。
  • 入力の形式を勘違いして何回か向こう側で弾かれる。
    • なんとか直して提出。
  • 二人ほど落とす。
  • 最後にCでTLEしそうな人が居たので落とす。

一限からなので終わったら速攻で寝ました。

SystemTest

  • ooox- Dは寝ながら考えていたのですが、解法全然思いつきませんでしたね。

結局3問とハック点500点で3212点で部屋一位、参加者全体では46位でした。

TLEが狙える回は、ソースコードを細かいところまで見る必要がなく、forの個数とかだけを見ればいいので恐ろしく楽でいいと思います。

ただ、部屋内でSystemTestで結構落ちている人もいて、約数全列挙でもスクリプト系言語で書いた人は約数の個数が多いケースでTLEになっていたようです。次からはせっかくのチャンスなので取りこぼしを少なくしたいです。

1533 -> 1633 (+100) 切りの良い上昇。