x をくっつけたら２番目のルールは無視できる。あとは T を元にして S をスキャンする。■D 問題「Divide Interval」。問題文が難しいよね。文というか式が。何度も読んで理解したところでは、ある２の冪乗 W があって、その２冪 W でアラインされた幅 W を持つ範囲が良い数列だと言っている。この説明でわかりやすくなったかは疑問。２つの２冪 w と W があって、w<W のとき、幅 W の良い数列の中と隣に、幅 w の良い数列はきっちり隙間なく整列するので、とりあえず最大の W を L...R の範囲内に見つけて、その左右に W 未満で範囲に収まる最大の w を再帰的に求めていけばいいように思う。考察半分実装半分でどちらもやや難しくやや大変だから、普段より高めの 450 点だったかと思う。22 分かけている。ビット演算で何かをやろうとしてあきらめて 60 通りの全探索に切り替えるまでに時間を使った。■E 問題「Weighted Tic-Tac-Toe」。メモ化再帰でとりあえずやってみたら通りました。盤面は３進数で。Takahashi と Aoki を区別するために手番を知りたくなって、どうやって知るか困ったけど、残りの白マスの偶奇で判別できた。メモ化関数の戻り値の仕様次第では二人の名前を区別する必要がないと思うのだけど、そう期待して実装を始めたのだけど、勝者の名前を返すような仕様にしてしまったので困ってしまっていた。終了条件が２つあって、一方の条件ではスコアが無関係だからそういう仕様に誘導されてしまった。24 分かけている。かけた時間から判断すると、D と E がどちらも 450 点だったのはまこと適切だったと思う。■F 問題「Subsequence LCM」。解けてないよ。愚直解法で TLE×14/AC×23。A の中の同一要素をまとめて処理すると TLE×12/AC×25。２つだけ AC が増えた。LCM でフィルタしていた部分を GCD で判定するようにして不用意に大きすぎる値を生み出さないようにも注意したけど、たぶんそれによる改善はあんまりない。これ以上のアイデアはない。■■■D 問題。最初の提出 #52331543 はせっかく定義した IJ 関数が一度しか呼び出されていなくてもったいないので、それを LR 関数として再定義してスクリプトの後半でも利用するようにした。提出 #52388999。16 行くらいあった後半部分が３行になった。while 文が２つある構成は同じだけど、ループの本体が関数を呼び出すだけの１行になった。各所で読んだのだけど、セグメント木についてはまったく頭に浮かびませんでした。セグメント木の図を思い浮かべれば問題の理解が早かったと思う。でもそれが思い浮かんだ時点でもう問題を理解してるよね。