Codeforces Beta Round #69 DIV2 Only - biochem

#66 が散々な結果で DIV2 に落ちていた。#67, 68 は不参加だったので復帰を賭けた一戦。

やるだけ。範囲が狭いので、篩う必要もない。Project Euler 用コードを使うだけ。

やるだけ。

効率よくやろうとすると大変なのだろうが、3^7 = 2187 より全ての組み合わせを DFS で列挙して確認すればよい。

anvil というのが何なのかよく分からないが、二次方程式の判別式から、p >= 4q となればよいことが分かる。q が [-b, b]、p が [0, a] の範囲にある面積は 2b * a。このうち、上記直線の下側となる領域の面積の割合を求める。

直線が長方形の右上角より上を通るか下を通るかで場合分け。

Submit。pretest failed。

あ、a や b が 0 の場合を忘れてた。修正。提出。

木を作って、葉のほうから分割統治する。すなわち、あるノード x より葉の部分について、x に戻ってくる場合の最大スコアと、戻って来なくていい場合の最大スコアを計算する。

方針は立ったが、実装できずに40分くらい悩んで諦める。

問題は、木の構造が edge list で与えられるので、そこから木をどう再構築するか。隣接行列では MLE するので、node ごとに vector<int> などで記憶させる必要があった。

それから、DFS する時にもし木が一直線になっていると、再帰が 100000 で stack overflow しかねないので、自前で stack を管理しないといけない。その実装。← 実際には、普通の関数呼び出しでも良かったらしい。

まさかの 5位!!! DIV2 Only とはいえ、かなり嬉しい。

もっとも、レートは 1639→1692 と微増に留まった。今回は、DIV1 と C・D・E 問題が共通だった模様。
E くらいの問題が時間内に解けるようになるのが、当面の目標か。