結果
01:09:34(1) 全完です。
A - We Love Golf (00:01:12)
切り上げと切り下げで比較です。
B - 1% (00:03:00)
101 を掛けるとオーバーフローしますから、利息分を計算してたし算です。
C - Many Requirements (00:18:21)
激ムズです。やり方を間違えているのでしょうか……
A としてありえる個数は 通りしかありません。
20 の階乗が出てきてまずそうに見えるのですが、実はこれは案外、間に合います。
カタラン数を憶えていると、およその大きさが分かるかもしれません。
これを DFS で全列挙し、スコアを計算です。
感想
はじめ、不等号の下の見逃していて、bit 全探索を書いていました。
bit 全探索の回は焼け野原になります。私は知っていますをしていたのですが、 それどころでなく難しかったですね。
とはいえ 15 分はさすがに掛かりすぎでしょう。
D - Floor Function (00:22:28)
まず、x を b で割って、x = bq + r と表しましょう。 あら不思議 q の項が消えますね。
ということは、q に依存しませんから、q = 0 のときだけを考えると良いです。 またまたあら不思議です。
今度は単調増加ですから最も大きいものを選ぶと良いです。
感想
珍しくギャグです。
E - Rotation Matching (00:49:04(1))
あーっ！ さてはまたギャグですね！？
洞察のプロですから、見えちゃうんですよね〜〜〜 幅が全部バラバラなら OK ですから、ハンバーガーのように 16, 25, 34 と選んで AC です。
……って、通らないではありませんか（泣）
落ち着いて考えてみました。 そうです。幅には 「補」(complement) が存在します。 特に偶数のときには牙を剥きます。 たとえば、
入力
2 6
のときに、
出力
1 4 2 3
としてはいけません。
この場合は 1 4 を少し伸ばして 1 5 にするとよいです。
一般には、内側から順に書いていって、被りそうになったら一つ伸ばすをするとよいです。
感想
ギャグなどと言ってしまって、申し訳ありませんでした（泣）
F - LIS on Tree (01:19:34)
このセットのオアシス、典型地力問題です。
みなさん、LIS の求め方をご存知でしょうか。 最も有名なものは、
dp[ 長さ ] = 終端の値
でしょう。
今回は、祖先の情報をすべて持った状態で DFS をするのが良さそうです。 ですから、第一に思いつくのは、この DP 配列を持って廻ることです。 しかし、これはうまく行きません。というのも、頂点を脱出するときに、DP を「戻す」ことができないからです。
ところで LIS は、キーと値を逆転して
dp[ 終端の値 ] = 長さの最大値
としても、（セグツリーなどを使うと）計算することができます。 こちらならば、（キーをディスティンクトにしておけば、）DP を「戻す」ことができます。
今回はこちらが良さそうです。
やることは伝わったと思うのですが、前処理が必要です。 具体的には、座標圧縮と頂点の値のディスティンクト化です。 ディスティンクト化は、今回は LIS の定義に等号がありませんから、同じ値の頂点ならば祖先のほうが大きいとすると良いです。
これを一度に行うために、 DFS で訪問順を計算しておき、a の値と、訪問時刻の逆順との辞書式順序でソートすると圧縮ができます。
