| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
58 分 6 完 + 2ペナです。68位でした。
今回、セット全体としてかなり難しい回でしょうか？6 完の難易度自体はいつも通りという感じもしますが、B, C, E などはなかなか手ごわかったです。問題 B は問題 B の中で最強に近いように思いますし、問題 C も問題 C の中で最強に近いように感じました。ある程度むずかしめの方が、私としては楽しくてありがたいですが。
問題 Fは、苦手なイメージのある種類の問題なので、時間内に解けて良かったです。結構正解人数多いんだなー。
問題B – 1%
指数関数はとても速く増えます。を知っていますか？という問題で、答が十分小さいと思えれば順に計算するだけです。「入力例 2」を観察すると、高々 3800 回の計算でよいことが分かりますね。サンプルがない場合は、手元で実験してみるのも手です。より一般的な知識としては、
- 自然対数の底 $e$ ：$\lim_{N\to\infty} \biggl(1+\frac{1}{N}\biggr)^N = e$ と定義する（単調増加にある値に収束することが示せる）。
- $e = 2.718\cdots$
- 大きな $N$ に対して $\biggl(1+\frac{1}{N}\biggr)^N$ は約 $2.7$ になると思っておけばよい。
程度を知っておくと、この手の概算に役立ちます。$1.01^{100}$ が約 $2.7$ です。雑に $1.01^{100} > 2$ と思うと、$1.01^{6000} > 2^{60} > 10^{18}$ となって、計算回数が $6000$ 以下であることが分かります。
計算式について
例えば x = floor(1.01 * x) というような計算式を実装すると、計算誤差の問題が発生します。Python（以外の言語の場合にもわりとそう）では、特に精度を指定しない限り、小数は 64 bit 浮動小数点数 です。桁数の保持に $11$ bit を使って有効数字は $53$ bit、おおよそ $15$ から $16$ 桁から先の計算については保証されません。実数を小数として扱おうとする以上仕方のない仕組みです。
整数でできる計算は整数で行うようにしましょう。
- x = x * 101 // 100
- x += x // 100
など。パフォーマンスもこちらの方が優れています。
問題C – Many Requirements
itertools.combinations_with_replacement(range(1, M+1), N)itertools はとても便利で、競技プログラミングを Python で取り組む利点のひとつにもなるでしょうか。
問題E – Rotation Matching
$a_i – b_i\pmod{N}$, $b_i – a_i\pmod{N}$ がすべて異なるようにするゲームですね。貪欲に避けるとかは厳しそうです。一例だけを作ればよいので、すべての $M,N$ で通用するように、ある程度一般的な規則で色々試してみましょう。
流石に具体的な $M$ で考えます。$M = 5$ とでもして、適当に作ってみます。
(1) A = [0,1,2,3,4], B = [5,6,7,8,9]
一回は考えましたが、全部衝突している超最悪なケースです。破棄します。
(2) A = [1,3,5,7,9], B = [2,6,10,14,18]
$b = 2a$ で $a$ を異なるようにすれば $b-a$ が異なるという戦略ですが、いまいちダメっぽい。
(3) A = [0,1,2,3,4], B = [9,8,7,6,5]
差が、$(9,-9)$, $(7,-7)$, $(5,-5)$, $(3,-3)$, $(1,-1)$ となっています。これがなかなか良さそうなのですが、まだだめです。$N = 12$ のとき、$9=-3$ などとなって衝突しています。
$(1,-1)$, $(3,-3)$, $(5,-5)$ までは良い感じです。残りに差が $2,4$ をぴったり当てはめられるといい感じだなと思い
(4) A = [0,1,2,3,4], B = [-2,-3,7,6,5]
完成です。一般の $M$ でも、全体を (3) の規則で作ったあと、最後に B の前半を変更すれば勝ちです。最後に、$N$ で割った余りをとって $1$ を足したりして完成です。
問題F – LIS on Tree
2週間前 の復習みたいな問題でしょうか？色ごとの値みたいなのはなくて、件の問題に比べると管理すべき値が一種しかないので易しそうです。
初めは、普通の 木 dp のように、根側から dp していくことを考えましたが、上手くいきません。何らかの形で、根側から順に計算していきたい雰囲気ですので、適当なデータ構造を持って Euler Tour で探索するという手法を思い浮かべます。
Euler Tour で探索する場合には、数列の項の追加と削除ができると良い感じです。この枠組みで扱えそうな LIS の計算方法を検討します。
アリ本にある有名なやつ（「数列の長さ → 末項の最小値」）というデータの持ち方だと、数列の項の削除方法が思い浮かびませんでした。「数列の末項 → 最大長」という対応を、何等かのデータ構造で管理しましょう。（公式解説の方法：巻き戻しのテクニック！初体験ではないですが、出てこなかったです。なるほど勉強になりました。BITだと更新箇所を覚えるのが面倒ですが、LIS の dp なら、更新箇所が疎なので簡単に戻せますね。）
末項が $n$ の場合の最大長を dp[n] としたときに、$\mathrm{dp}[n] = \max_{i < n}\{ \mathrm{dp}[i] \}$ という種類の操作ができた方が良さそうです。左端からの区間 max ですので、BIT（Fenwick Tree）、Seg木 （Segment Tree）を思い浮かべます。
BIT だと、数列の末項の削除が難しそうなので、Seg木を選択しました。配列をなぞるだけの LIS の計算ならできそうです。
最後に、「削除」の方法です。キーが重複していると、上手く削除できないと思ったので、全ての項が互いに異なると思えるような仕組みを考えます。A[v] の代わりに A[v] * N – depth[v] を考えると、根からある頂点までのパス上での項がすべて異なります（$N$ で割った余りが異なるので）。あとは座圧してEuler Tour順に探索すれば、各 $v$ に対して、「その項が末項であるような最大数列長」が計算できます。
最後に、答の計算においては、末項が自身の先祖であるような場合を含めて計算しなければいけません（2ペナ）。サンプルがひとつしかなかったので厳しい感情になりましたが、ひとつのサンプルでも根をとりかえればサンプルを増やすことができるので、色々な根で手計算と比較することで気づくことができました。
