UTPC 2011

Online Judge

ノートPCとVMwareの起動が遅くて15-20分くらい遅れて参加。

A-D問題

  • やるだけ。

E問題

  • 部分点狙ってもしゃあないんで、N=1000の場合を考える。
    • Bi<Bjとなると、j→iと取るよりもi→jと取るべき。
    • なんでBの方でソートしておくべき。
    • あとはN=1000なんでDPでいけそう。AC。

G問題

  • なんかF以降がむずい。解いている人が多いGに手をつける
    • とりあえず3個連続する辺を2箇所で取ればいいんじゃないの？
    • 実装してサブミットする前に1,1,10,10,10,10とかのケースで死ぬことに気づいた。
    • 2個の三角形の辺の選び方の組み合わせを全通り考えてみた。
    • 結局3個連続する辺もしくは6個連続する辺を取れば良く、6個連続する場合も辺の分配の仕方は3通りしか無いことがことが判明。
    • 実装してサブミット。AC。

F問題

  • たぶんn/2個できるっしょ。
    • てきとうに辺を選んでいってパスをk個作る方針でがんばんる。
    • n=8,k=4くらいで死ぬ。
    • いろいろ考える。全域木だからパスである必要ないじゃん。
    • 左右対称になるようにてきとうにやってみたら簡単に作れた。AC。

H問題

  • H分からん。Iにいたっては20点分も分からん。
    • DPで解くのか？区間の問題になるのか？
    • なんかこういう風な区間の問題を蟻本で見た気がする。
    • たしか最小費用流で解くはずなんでグラフを紙上に作ってみた。
    • なんかうまくいかない。時間がなくなってきたので20点分だけ提出。

I問題

  • よう分からん。
    • +,-,*が使えないとなるとビット単位で見ていけばいいじゃん。
    • とりあえず20点分を提出。WA。
    • 負の数を使っていたので修正して提出。AC。
    • +,-,*が使えると？
    • 下の数式みたいに他のxを代入したときに0になるようにすればいいんじゃない。

　　　　　　　　　(x-x_2)(x-x_3)\cdots(x-x_n)/M*y_1

    • オーバーフローとかで0になったらいやだな。
    • 最悪のケースでもならないことが分かった。しかしもう時間が無くて終了

結果

I問題：割り算が無いの忘れてた。
740点6位。参加が遅れなかったら5位になれったぽいのでちょっと勿体無かった。反省としてはWAが1回しか無くてそこそこ調子良かった気がする。G,Fにちょっと時間をかけすぎた。あと解説を聞くとH,I,Kくらいはできても良さそうな気がした。