与えられるテスト結果が誤っており上記の条件を満たす組み合わせが存在しない場合もあります。その場合は 0 通りと解答してください」の意味がよくわからなかった。信頼できない入力が混じっていて、それを見抜いて何らかの対処が求められているのかと思った。実際は単純に矛盾するテストによって答えが０通りの場合があるよということを言っているだけだった。たしかに、複数のテストを照合した結果矛盾が生じて答えが存在しない場合、じゃあ、個々のテストにおいて「開いた(開くはずがない)」「開かなかった(開かないはずがない)」という結果をどう扱えばいいかという疑問が生じる。それは誤りであるという断り書きだった。■D 問題「Masked Popcount」。かつてよく見られた数え上げ問題。苦手だよ。でも精進によってなんとなくの型みたいなものは持っている。上限が N で与えられてるのがやっかいなんだよね。たとえば N=2**60 ならこれは主客転倒で寄与を簡単に数えられる。じゃあどのようにしてそういう状況を作るかというと、与えられた N のビットのうち、最も左にあって最初に倒されるビットを決め打つことによって N を複数の区間に分割する。N のプリフィックスと自由に {0,1} が選べるサフィックスとで構成される区間について問題を解く。たとえば N=0b10101 ならプリフィックスは１のビットの数と同じ次の３つ(0b10100、0b100xx、0b0xxxx)。 もちろん１つもビットを倒さない場合も忘れない。■E 問題「Max/Min」。よくわからない問題。N の上限は 20 万。これは O(N) もしくは O(NlogN) が解法となるよくある制約で、N の制約としてはほぼ上限。そして A が取り得る値が 100 万以下。これは N と比較すると大きい数字だけど、処理すべき区間が 100 万以下であってそれ以上は考えなくてもいいと思うと、そんなに大きい数字には思えない不思議。結局これは調和級数の上限がどうのという問題だったんだろうか。特別な道具を使わずに配列を操作すると決めたあとでも答えを合わせるのに苦労して、結局１時間近くかけてしまった。やるべきことはひと目でわかるんですよ。すべての組み合わせについて足し合わせるに当たって、予めソートして Ai と Aj の大小関係を固定してしまえば考えるべきは分子が分母の１倍か２倍か３倍か……。時間が厳しいので(そこが問われている問題なので)同じ値はまとめて計算しますよ。そうするとどんな入力が嫌かというと、小さい数字が順番に並んでると、処理をまとめることができず、区間を大きくスキップして処理することもできないのが困るなと。だけどね、100 番目、1000 番目の値はすでに十分大きいわけです。100 万割る 100 は１万だし、100 万割る 1000 は 1000 なので、個々の処理量は無に等しい。もちろん１万が１万集まれば馬鹿にならないんだけど、全体で見ても処理可能な範囲に収まることは知っている。名前は出て来なかったけど高３の演習問題でいつの間にか不等号を証明させられていたような気がする。■F 問題「Distance Component Size Query」。解けなかった。セグメント木とか平方分割とか、うまく区間を分割して効率良く数えられないかと考えたけど、できそうでできなかった。でもできるのかなと思ってる。自分にはできないけど。K=0 と K=1、それと K がすごく大きいときでだいぶ様子が違ってくるなとも思った。でも、じゃあ K=1 の場合に限れば問題が解けるかというと、そうでもなかった。■■■D 問題。桁ごとにサイクルを考えるという解法を仕入れてきた☞。LSB から見ていくと、サイクルは２、４、８と倍々になっていく。その中身だけど、前半が０で後半が１という単純なもの。だから 0 から N までの N+1 個の数をサイクルと半端に分けて１の数を数えるのも簡単。提出 #54162917 (AC / 165 Byte / 42 ms)。この考え方だとずるいぐらいに実装が簡単だった。自分は自分の考え方で実装したとき式を間違えて１回 WA を出してるからね>提出 #54107427 (WA)。