Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2012-12-03

[]UTPC2012 01:54 はてなブックマーク - UTPC2012 - TopCoderの学習のお時間


practice

4個目のケースの問題文を前から1文字ずつ推測しようとして、WAとREとTLEとMLEで分岐させようとしたらMLEを意図的に発生させるのが難しくて挫折した(単純にでかい配列取るとREになる)

というか3分岐でも4分岐でもアルファベット1文字決めるのに3回のサブミットが必要なのは一緒だから気にしなくてよかった


本番

オンサイトで参加した。隣の席だったりんごさんが2Lの緑茶をおもむろに取り出して威嚇してきた


  • F
    • 部分点が???になってて面白そうだったのでまず見てみたけどすぐには方針立たないので次へ
  • E
    • きっと反例あるんだろうけどとりあえず二分探索で投げてみた→やっぱりWA
    • どうせ嘘解法なんだから時間制限いっぱいまで調べるようにしておけば良かった
  • A
    • やる
  • B
    • 後ろから
  • C
    • 完全グラフを想像すると、Nが大きい場合には絶対に森にならないというのはイメージできる
    • Nが小さいときはクエリを毎回処理する。エッジの本数で森かどうか自明にわからない場合はDFSで判定
    • DFSがバグってて時間かかってしまった
    • あとTLEケースもあったので普通の隣接行列じゃなくてBitSetで持って高速化した
    • けどTLEの原因はDFSがバグってたせいもあるはずなので、高速化しないといけなかったどうかは不明
  • D
    • 1つの辺を見ると回転角度θは分かるので
    • 不動点を(X,Y)とするとそれを中心に1/2倍してθ回転するアフィン変換を計算すると連立方程式になる
    • と思って計算してたら式がグロい感じになったので逃亡
  • G
    • スタンダードな組み合わせ+DP
    • いろいろバグってしまったけどサンプルが強かったので一発AC
  • E
    • 適当な上限から時間いっぱい調べるのを書いて部分点をもらう
  • F
    • なぜか最初a==26だと思い込んでて、任意のハッシュ値を持つ文字列を作るの可能やーん、とか思ってた。アホだ
    • 半分全列挙に近いアイディアでやった
    • 5文字の文字列を全部生成してハッシュ値とともにメモっとく。26^5≒10^8なので、最悪のb=10^9のときでも1/10くらいの確率で、ランダムに作った文字列をメモっておいた文字列のうちどれかと組み合わせて特定のハッシュ値にできる
    • 実際は5文字を全生成するとTLEしそうなので、4文字だけ全生成しておいてあとの1文字の分は毎回調べれば良い
    • これで提出したら190点になった
    • (あとで)全体の文字列のハッシュ値が0になるものを探していたけれど、bがaの累乗の場合はどうやっても0にならない場合があると気づいた
    • のでハッシュ値を1になるようにしてみたら今度は198点…
    • あと1ケースが何なのかよくわからない
  • D
    • 一応部分点だけ取っとく
  • L
    • 部分点は普通に木DPすれば良い
    • dp[i][j]で、ノードiの値をj以下にするのに必要な最小操作回数を表す
    • jの値は-200〜200くらいまで考えとけば十分のはず
    • 木の与え方が親切でうれしい
  • E
    • 適当な下限から時間いっぱい調べるのを書くが、残り時間少なくて焦っていたので賢くない方法になってしまい正解できず

手を付けなかった問題について

  • H
    • ぱっと見ではなんか区間をlogNで処理するようなややこしいデータ構造使うのだろうかと思って重く見えてしまった
  • I
    • 部分点だけならDPすればできそうに思ったけど実装しようとする気力とか時間がなかった
  • J
    • 問題文長いし、見るからにwataさんの問題でどうせ最小費用流だろうと思ったので飛ばした
  • K
    • 図形がやばそうなので飛ばした

提出履歴:http://utpc2012.contest.atcoder.jp/submissions/all?user_screen_name=tomerun


結果

  • 100 + 100 + 100 + 50 + 50 + 190 + 200 + 0 + 0 + 0 + 0 + 50 = 840
  • 総合24位/170チームくらい
  • 個人12位/150人くらい

反省とか感想とか

  • Cの単純なDFSでバグったのはやばすぎ
  • Dは解説を聞いた今でも解ける気がしない
  • Eでハマったのが痛すぎる。嘘解法なら嘘解法なりに考えて解けそうなのを出さないと
  • Fはとても楽しかった。乱択は良いものだ
  • Gはかなり得意な系統のはずだけど1時間近くかかっててひどい。サンプルがとても簡単なのととても難しいのしかなかったので、中間のを自分で用意してから書くとデバッグ速かったんではないだろうか
  • Hはちゃんと時間とって考えれば自力でできるかどうかギリギリくらいのとこなので記憶が薄れた数ヶ月後にもう一度やるべき
  • Iは面白そうなので後でやる
  • J,K,Lは鑑賞対象
 |