結果は、3問中1問解けただけ。。でも1000位以内に入ってるので、Round 2行けるのでは！？
とりあえず、問題解説。
1問目。
オーソドックスなBFSの問題。
グラフに帰着させても解けるが、すべての枝の重みが1のときはBFSで解く方がよい。
問題が読みにくい・・・。
2問目。
不等式制約のついた関数最大化問題。
凸関数なら、二分法でいけると思ったが、よく考えると目的関数は局所的にはギザギザな形になる。
とりあえず、解いてみるがサンプルと合わない。てか、サンプルより良い解が出るのですが・・。サンプル間違ってるんじゃ疑惑。そして何故か現在2問目はサイトから消滅している・・・。
⇒疑惑が確信へと変わる。
【追記】
目的関数ギザギザってのは誤解があるようですねー。
不等式制約から片方の変数の最大値を割り出して、１変数の二次関数にすれば目的関数がギザギザするけど、オリジナル問題の目的関数はギザギザじゃないですね。。単なる単調増加の平面です。
適当な初期点から出発して、逐次、偏微分値が大きい方に進んで行くってのを制約式を満たすまで繰り返せば最大値に辿り着くんじゃないのか、これ。。
3問目。
確率の問題。
DPで解けるなと思ったが、これまた手計算でサンプルと合わない。なぜ！？
でも、黄色い人の情報によるとDPで解けるようです。もしくはGreedyでも解けるみたい。まあ大局観はずれてなかったということで。
概して、英語が読みにくいのですが・・。
そしてサンプルはなるべく手計算できるような簡単なものを入れて欲しいのですが。
てか、1Aの結果早く欲しいのですが。
まー、ぐだぐだ言わずに
英語力もっと付けろ！
与えられた情報が難しいものでも、その意味を読み解く力を付けろ！
って話ですね。
0 件のコメント:
コメントを投稿