UAPC2011 Summer

AOJ Online Judge

なんとなく後ろから見ていく。

J問題

  • x番目の要素をO(logn)で取り出せる二部探索木があれば楽勝な気が。

I問題

  • DP臭い
    • でも1周して戻ってくるのをどこで使うかで厄介になってくるなあ
    • そんなもん初めに全部使ってしまえばいいじゃね？
    • 書いた。合わん。「やゆよ」と「わをん」は3つでループすんのか。
    • 修正した。submit AC。

H問題

  • ロックマンですね。分かります。
    • なにも考えずにDirected MSTを使うか。
    • よく見たら場合の数も必要なんかい。
    • 入次数と出次数1のグラフだから閉路の集合になって、一番重みが低い辺を切れば良いと。
    • 去年のUAPCで似た問題があった気がする。
    • 書いた。3番目の答えが2になった。
    • 閉路同士での順番はぐちゃぐちゃになっていいのか。てきとうにコンビネーションを使って計算。submit AC。

G問題

  • AKB48っぽい。
    • 二部探索+ソートとかで行けそう。
    • 既に上位に入ってる場合とかがめんどい。いろいろ注意しながら書いた。submit AC。

A問題

  • F以降は解かれていたので今度はAから順番に解くことに。
    • やるだけゲー。書いた。submit AC。

B問題

  • サイコロをわざわざ展開図から読み込む問題。
    • めんどくさい。めんどくさすぎる。しかもそれだけ。
    • 書いた。submit WA。
    • 同じ確率の場合にHIGHを返すのを見逃していた。submit AC。

C問題

  • 包除原理ですね。分かります。
    • 書いた。submit AC。

D問題

  • topcoderの問題
    • MathとDP、GreedyとGraph、GeometryとOtherはマージ。
    • あとはバランスの良いセットが0,1,2個の場合を考えるだけ。submit AC。

E問題

  • 3SATの問題じゃない。
    • 節に~xとxが同時に含まれてないかどうかチェックするだけ。submit AC。

F問題

  • コミケの問題。
    • クエリは後ろから順に見ていくとして…。後ろから見るだけっぽいな。
    • 書いた。submit AC。

J問題

  • 普通に解かれてら。
    • 残り40分だと少しきつい。と思ったら1時間勘違いしてた。
    • 配列の平方根分割？めんどくさそう。
    • FenwickTreeを使ってなんかできんかな。
    • 二部探索と組み合わせるとできそうだ。
    • 書いた。submit AC。

結果

10完1WA Time=1496 4位。
全体的にはいい感じだったと思うが、komakiさんやjapljさんに1時間差をつけられてる。
後ろから解いていったんでTimeが少し大きいのはいいとして、J問題は最初に見た時に思いつけるべき。