2009-06-13

■ [others]The 2nd Imos Contest 23:46

2009-06-13 20:00-23:00

http://judge.imoz.jp/?cid=4

参加しました。難しかったです。ジャッジシステムの作り込まれ具合に感動。

6問中2問正解して、38位/約60人 という結果でした。まぁ実力通りだとこんなもんでしょう。先週がおかしかった

ログ

• A開く
  • やるだけだけど最初の問題にしてはけっこうややこしい
  • ソートし忘れてたり最後のカードが抜けてる場合を忘れてたりでちょっと手間取る。サンプルが親切で良かった
  • submit…しようとしたら練習してなかったので方法がわからないw
    • とりあえずファイル提出してみた
    • Accept
• B開く
  • 最長になりえるのは、葉→根 か 葉→中間ノード→別の葉 という経路
  • それぞれの葉ノードに対して、根からの距離を計算
  • その過程で、それぞれの中間ノードについて子の長さを長い方から2つ保持しておく
  • 答えは、以下のうち一番大きいやつ
    • 葉→根の経路の距離
    • 中間ノード（折り返し点）からその配下の葉で遠いやつ2つの距離を足したもの
  • WA
  • 根が直接複数の子を持つケースを忘れていた
  • 修正して提出→TLE
  • あっれーO(n)なんだけどなー
  • 小手先の高速化をいろいろやってもTLE
• Cに移る
  • とりあえずbrute-forceに書いてみる
  • TLE。ですよねー
  • 計算量的にタイムリミットとはそう大きくかけ離れてはいなさそうで、アルゴリズムの抜本的改良は思いつかなさそうだったこともあり、地道に高速化する方針に
  • 入力の長さで場合分けしたり、小手先の枝刈りを入れたりで泥臭く高速化
  • それでもTLEのまま
• D開く
  • ルールが複雑。DPっぽい雰囲気？
  • タイムリミット10秒というのが嫌な感じなのでパス
• E開く
  • データ構造系？
  • 知識があったらすぐ見えそうな気もするが
  • とりあえずパス
• F開く
  • 整数問題
  • フェルマーの小定理などを思い出しつつ10分くらい考えるも、行き詰まったのでパス
• Bに戻る
  • 標準入力からの読み込みを、Scanner#nextInt()ではなくScanner#nextLine()を使うようにしてみたらTLEじゃなくなった
    • こんなこともあるとは…。やっぱりScannerって遅いんですね
  • Accept
• Cへ
  • 他の方針も思いつかないので引き続き地道な高速化をしていくとTLEがWAに変わった
  • しかしぐちゃぐちゃ書いてるうちにけっこうバグ埋め込んでたみたいで潰すのが大変
  • タイムアップ
  • 終了1分後に通った