3完。問題見てけっこう覚悟してたけどギリ黄パフォで耐えた。自分がこのBCを解けるとはなあという感慨と、ここまでやって355位かよという絶望感。
A - Dial Up
すぐ解けたけどやりたくない。場合分けすれば簡単なのは明らかだが、やりたくないに決まっている。頑張って場合分けして書いた。自分としてはかなり高いパフォーマンスを出して書けたと感じた。できれば、場合分けを少なくするほうの能力が欲しかったけど。
まず、最小で何回シフトすれば違う値になるか調べる。そして、Tで切り替えが何回起こるか調べる。Tが全部同じ数でSの先頭とも一致していればM回。そういうのを全部で6個書いた。普通にACだったけど、そうじゃない可能性もそこそこあったはずで、そうなったらかなり嫌な気持ちになっていただろうなと想像して少し嫌な気持ちになる。
B - Squares
10^6ならともかく10^12ってお前。x^2はかなり大きくなりうるので、yを引いてもその正方形のほんの外殻しか削り切れない。なにもわからないので、Cを読んだりDを読んだりして気分転換して考え続ける。平方根とって積分とか考えたけど誤差を出さない方法がない。平方数をz^2として、式変形を色々試す。順位表を見ると信じられないほど解かれていて、実験して x, y, z を出力させてみたりもした。yが素数のときに解が1個しかないと気づき、約数の個数でできなくもないのかとか思うが、10^12なので無理。いざとなったら埋め込みもとさえ思ったが、今考えると10^12はあまりにも大きい。
y=x^2-z^2=(x+z)(x-z) というのに気づいたのが22時くらいだったと思う。差が偶数の2数であって積がN以下のものの個数。これはいけるんじゃないか。希望が見えたけどすぐには解けない。図を描くと、sqrt(N)の場所で対称になっている。X*YがN以下でX>=Yのものを考える。グラフを斜めの線で切る感じ。i から N/i までの、i との差が偶数の数の個数を求めて足していく。考察の探索深さがやべえ。
C - LIS to Original Sequence
A_1の前にA_1より小さいものが来てはいけない。A_1とA_2の間にA_1より大きくA_2より小さい数が来てはいけない。というように、いくつかの簡単にわかる必要条件がある。辞書順最小なので、A_1の前に小さいものを置きたいが、前述の条件からそれはできない。ということは、可能であればA_1を先頭にしたい。可能であるという前提で考察を進めていく。その次には（A_iに含まれてないなら）1を置きたい。これは大丈夫そうだが、2も置くとLISが伸びてしまう。A_2より小さいものは置けないし、A_2より大きいものを置いたら辞書順で後になってしまうので、次はA_2を置きたい。その次は2,3と置けたりするだろうか。いや、前に1があるからLISが伸びてしまい置けない。2しか置けないのは考え方が楽になって都合がいい。さて、A_kの周辺はどうか。A_kより大きいものをA_kより後には置けない。しかし、残ったものを全部降順に置くなら問題ない。既に置いた1や2は小さい順に置いたので、それより大きいものから更に大きくなるのはLISが伸びてしまいダメ。つまり、A_iより小さいものが残っていれば直後に挿入して、最後のA_kは残ったものと混ぜて降順ソートして全部追加。コーナーケースはあまり考えてなかったけど通った。
D - Unique Subsequence
ABC214Fを思い出させる。貪欲に左から取ることにして残った取り方を除けばよかったりしないかなと思うが、条件を満たさないのも1通りずつ残ってしまう。いやなんかその辺上手く取れないかなと思ったけど、だめだった。最後は時間もないので諦めてしまった。いやあ疲れた。
