02/22(月)
週記を投稿してからしばらく、以前追いついてから更新を放置していたなろうを数作品読んでいた。一度一気読みして追いついただけあって、やはり面白いのだが、どうにも少し溜めると手が伸びなくなってしまうようだ。正午就寝。
午後6時から30分おきに目覚ましをかけていて、午後7時半に起床。サークル解説会は午後8時からで、それの準備をしようと余裕を持たせていたのだが、眠すぎて起きられなかった。残り30分しかないが、何とかARC112-ABの解説スライドを作る。正直公式解説がそこそこ丁寧なので目新しいことは言えない。今日はChanyuhさんがE問題の解説をしてくださるらしいので、なかなかレベルの高い解説会になりそうだ。
何事もなく終了。E問題の解説は公式解説の方法と形式的冪級数の方法2つを紹介してくださった。
2021/02/22 定例会 | puzzleknot 公式サイト
Eは、「まだ動かしていない区間」の両端を持つDPをO(N^2M)で書いてみると、サンプルが合う。
週記（2021/02/08-2020/02/14） - kotatsugameの日記
僕はこのような（解説とほとんど同じ）考察ステップの踏み方をした。ここからだと形式的冪級数にたどり着くのはかなり不自然に見える。どちらにせよ「先頭に置くのも末尾に置くのも（あとからcomb(A+B,A)を掛ければ）同じである」ということに気づく必要があって、その気づきを最初に得るか最後に得るかの違いとも考えられる。
終了して公式サイトの更新やツイートをし、少しAOJ-ICPCを開いたが、眠気に負けてすぐ布団に戻り、寝た。午後9時から午前0時まで寝ていたらしい。本当はこのタイミングでガッと睡眠負債を返済したかったのだが、やはりというべきか、それほど長くは眠れなかった。長く眠るには長く眠るだけの準備とか気合いが必要である。
起きてからまたなろうを読む。午前3時くらいに起き上がり、食事してAOJ-ICPCから1問解いた。500点で、以前チャレンジして解けなかった「The Two Men of the Japanese Alps」。問題概要はまだ覚えていた。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5244797#1
ありうる標高をすべて列挙して、直線を分割するのは良い。ここで新たに作成される点の個数をN^2/2以下と評価したのもピッタリ合っていた。問題は、そこから最短経路問題にするときの辺の張り方であった。左右2人とも後ろ向きに移動することはないと思っていたが、実はあるらしい。適当に遷移を増やしたら通ったので最初はよくわかっていなかったが、この遷移がないと答えが無限大になる小さいケースを作成できた。
7 0 0 1 2 2 1 3 4 4 0 5 3 6 0
3 4で出会うことになる。右の人は最初に0→3→0という標高の遷移をしなければならず、左の人は0→2→1→3(→4)を往復してそれに対応する。往復するので、復路において1→2と後退するが、この時右の人は3→0の真っ最中であるため、こちらも後退しなければならなかった。わかってみれば簡単なことだった。
明日は昼からICPCのチーム練がある。午前6時半就寝。
02/23(火)
午前11時起床。弁当を温めて食べるくらいの時間はあった。午前11時半からチーム練。今日はこのセットだった。
https://codeforces.com/contest/1070
ABCDEFGHIJKの11完だった。僕はDKHFAEIBをこの順で解いた。
DKHは自明。Fはやるだけ。Aは最初読んだときSmall Multipleが頭にチラついてうまく考察できなかったが、*10+0から*10+9までを全部書くとただのBFSでも値の昇順に計算することができる。Eは適当にBIT上で二分探索する。Iは結構難しかった。uとvを結ぶ辺があったとき、これと同じ会社の辺はuとvのどちらか一方にしか存在できない。どちらに存在するかは辺の向き付けに対応して、この言い換えのもとで入次数・出次数が定まるので、フローを流して復元する。Bは気合い。blacklistの区間に対して、whitelistのいかなる区間も含まないような極大なsubnetをとることにしてよい。これは、subnet間の関係として、どちらかがもう片方に完全に含まれるか全く交差しないかの2通りしかなくて、中途半端に重なるようなものが存在しないことからわかる。
最後1時間Lを考えていて、答えが2以下になりそうなことはエスパーできたが、構築ができなかった。Um_nikのコメントを読んでupsolveした。答えが2であるとすると、次数に関する条件は各頂点にZ/2Zの元を割り振る連立方程式の形で書ける。この連立方程式は必ず答えを持つことが示せて、このときbitsetでガウスの消去法をするとO(N^3/wordsize)で解ける。
https://codeforces.com/blog/entry/62570?#comment-465420
午後6時からCF #704 Div.2。全完。pretest時点では20位だったが、システスでかなり上がって11位になった。
ABは明らか。Cも明らかだけど実装ミスで1WA。↓これだ。
tに同じ文字が連続しているとき、sの1文字で両方をマッチさせてしまっていませんか？（僕はこれで落ちたので聞いてみます）
— こたつがめ (@kotatsugame_t) 2021年2月23日
Dは3回もWAを生やしてしまった。まずB-1<=K<=A+B-2の場合の構築を思いついて、それとA=0、B=1を実装して提出した。WA。次にK=0で必ず作れることに思い当たり再度提出。これもWA。K<=Aが作れることに気づき提出するも、さらにWAだった。結局、実は0<=K<=A+B-2の全てが作れることがわかり、A+B-2は理論上最大なので、これで正解。
Eはよくわからない。N<=MとN>=Mで処理を分けるやつかと思い、簡単そうなN>=Mから考えていたところ、O(NM^2)っぽいのができる。多分速そうなので出したらpretestを通った。このM^2の項は、第1行のどことどこを変えるかに対応している。しかし実のところ、変えることでこれまでダメだった行がOKになる箇所というのはほとんどないらしい。第1行と4か所異なる行が存在すれば、4C2通りのどれかを選ぶしかない。3か所異なる行が存在すれば、片方は3C1通りで、あとは（だいぶ甘い評価だが）高々M通りである。結局O(NM)なので、これでよかった。計算量解析は日記を書いている今考えたことであって、システス中はTLEしないかとヒヤヒヤしていた。
午後9時からサークルバチャ。今日はCF #542 Div.1。aABCを解いた。
Aはよい。O(N^2)が通る制約でびっくり。ちょっと頑張るともっと速くなりそうな気はするし、解説にも線形時間で解けるとは書いてあるが、考えていない。Bは、正数の項を1つだけ作って残りを-1で埋めることを考えた。このままだとKが素数の時などに困るので、-1を一つだけ-1-aにしてみる。項数nで-1,...,-1,-1-a,xと並んでいるとすると、Aliceのコードはxを返す。翻って正しい解はn(x-n-a+1)となる。……と思ったが、実際は正しい解がもう少し大きくなる場合があるらしい。区間の幅に対する答えのグラフが上に凸の放物線になって、その頂点が実現可能な値の場合にそのようなことが起こる。n=2000決め打ちでやってみたらWAになったので、n=2..2000で毎回チェックしてみたところ、通った。
Cは題意を取るのにちょっと手間取った。10は4通りのアルファベット列を生成する："1"、"0"、"10"、"1""0"。文字列Sのある区間から生成されうるアルファベット列の個数、というのを全ての区間に対して計算する。これは、区間に1文字足すことを考えればO(M^2)でできる。次に、以前にまったく同じ区間が出現していないような区間のぶんだけ答えを増加させる。文字列を反転してZ-algorithmを使うと、今の文字列の末尾から何文字までは以前に出現したことがあるのかわかるので、それ以降を足せばよい。わかってみれば簡単。
Dをずっと考えていたが解けなかったので、バチャ後にupsolveした。基本は平方分割で、rをfixしたとき[l,r]における1回しか出現しない値の個数がsum b[l..r]と等しくなるような数列bを構成できるというのも重要。rをインクリメントしたとき、bは高々3か所しか変更されないので、変更のあったブロックを毎回再計算しても間に合う。
https://codeforces.com/contest/1129/submission/108320562
ラノベを1冊読んだ。「ワールド・ティーチャー」14巻。実はキャラクターの名前を忘れてしまっていたらしく、うまく集中できなかった。Nardackさんのイラストが良い。大軍vs大群の戦いだったり、その中での主人公組の無双だったりの上手な描き方とはどのようなものなのだろう。読んでいて戦場の風景をうまく想像できなかったが、これは一般的な城壁のつくりとか兵士の様相を知らない僕に責任がありそう。
午前5時半就寝。
02/24(水)
午後5時半起床。布団でゴロゴロしていたらatgolferの更新が流れてきた。
こういうのまだ残っていたのか。そのあとに別の人に同じ方法でもう一つ最短を取られている。
食事をしつつ、AOJ-ICPC 550点の「夕食」を考えていた。これは星もたくさんついているしsolvedも多いが、全然わからずに今まで残っていた。これまでにした自炊の回数だけでなく日付が幸福度の総和に影響を及ぼすので、うまく独立に考えるためにこれをどう解消するかが問題。解消せずとも自炊の回数も持つdpをすれば当然できるが、そのままだと間に合うわけがない。これをデータ構造か何かで改善する方法も考えたが、うまくいかない。
毎日食堂に行くか自炊するかに寄せて、貪欲にずらしていく方法はどうだろう。これは以前にも考えていたが、結局これまでにした自炊の日付も評価に含めなければならないこと、また何らかの極小値にはまりこんで抜け出せないことを予感し、あまり細かく式を立ててはいなかった。これまでにした自炊の日付を評価に含めるのに、区間add・区間maxの遅延セグメント木などは使えないだろうか。評価値を毎回更新していくということだ。とりあえず、この方針で式を立ててみよう。まず最初に、毎日自炊する状態を考える。
毎日自炊する状態から日目（0-indexed）に食堂に行くことにすると、得られる幸福度の総和は
増えて
下がる。またこれとは別に、以後
日の自炊パワーは2下がるので、さらに
下がると考えてもよい。よって
、これが初期状態からの
日目の評価値だ。その状態のまま、次に
日目に食堂に行くとどうなるだろう。
まず、のとき。このとき、得られる幸福度の総和が
増えて
下がるのは変わらない。しかし、以後
の自炊パワーについては、すでに
日目に自炊しないことが確定しているのだから、下がる値は
になる。足して
。よって評価値は
されると考えてよい。
次にのときを考えよう。この場合、以後の自炊パワーの下がり幅は
で変わらないが、
日目の自炊パワーが
日目に食堂に行った影響で2下がっているので、得られる幸福度の総和の下がり幅は
ではなく
となる。よって評価値は
。奇しくも先ほどと同じ形をしている。
なんとも驚くべきことに、これで自炊の日付の影響はなくなってしまったようだ。評価値の更新にもセグメント木を持ち出す必要はなく、の降順に並べて都度
の係数を増やせばよくなった。極小値にはまりこむというのも依然として残っているが、これは食堂に行く日を全探索できるので問題ない。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5248766#1
かなりびっくりした。以下の解説ブログでは、もっと直接的に自炊の日付の影響を消している。+1と-1を+2と0にする、という部分だけ見れば見覚えがないこともなさそう。
SRM801に出た。roomに18人いて、そのうち9人が赤だった。EasyとMedを解いて14位。システス前は22位くらいで、Hackが大量に出て一度は26位まで落ちたが、システスで上の人が大量に落ちたようだ。レートは2481→2521(+40)でhighest。いい感じ。
Easyは謎。最初はmapで個数をカウントして、毎回インクリメント・デクリメントしようかと思っていたが、このmap（またはsetを用いても同様）で付くlogは非常に重いらしい。この方針で大量の人が落ちていた。僕は何となくvectorをsortして毎回舐める方針に切り替えていたので難を逃れた。
Medも謎。0と1のように差が1しかない文字同士はswapできないので順番が保たれる。逆にそれ以外はどうとでもなるので、9個の差が1である文字のペアについて、それぞれを抜き出した文字列をarray<string,9>に入れ、これを比較して重複を削除する。見た瞬間解けてよくわからなかった。最悪ケースでは長さ2500の文字列2500個に対し、それぞれ9回ずつ舐める処理をして、その上2500個のarray<string,9>をsortするので、不安になって試してみたが、普通に速かった。
Hardはカス。各折れ線は凸包をとって考えてもよくて、どうせ長方形の一辺はどこかの辺に沿う（これは論文があるらしい）ので、それを全探索して頑張ると解けそうである。ここまではすぐわかるのだが、微妙に未証明なので書くのをためらっていて、結果残り20分くらいで書き始めたものがCEのままコーディング時間が終了した。後から書き進めたところ、どうにもデバッグ含めて残り20分くらい必要だったらしいので、すぐ書き始めても間に合わなかったのかもしれない。サンプルを合わせて半信半疑のままシステスを走らせたら一発で通ってびっくり。そもそもSRMは一発で通さなければならないんだよな。
え、通った。
— こたつがめ (@kotatsugame_t) 2021年2月24日
・各線分の頂点の重複を削除して凸包を取る
・凸包の各線分について、それがX軸と並行になるように回転させる
・xminとyminを引いて第一象限に寄せ、xmaxとymaxを記録する
・xmaxでソートしてymaxが降順になるように適宜削除しておく
・全ての凸包の全てのxmaxに対し、各凸包でupper_bound-1のymaxのmaxを取る。これがW=xmaxに対するHの候補になる。HW<2e10なるものを見つける。
— こたつがめ (@kotatsugame_t) 2021年2月24日
・各凸包に対して復元する。第一象限で長方形を作って、3点にxminとyminを足して逆回転させる。
こんなの、嫌だろ
コンテスト後は本を読んだり少しAOJ-ICPCを進めたりしていた。金曜日にまた夕方から遊ぶ予定があるので、生活リズムを少し整えておく必要があると思い、午前7時くらいに布団に入る。
SRMのHardについて、長方形のサイズを1e5x2e5に決め打っても通るらしい。なぜそうなるのか全然わかっていなかったのだが、制約をよく読みなおすと、折れ線の長さが2e5以下であるという文言を見つけた。これが効いているのだろう。辺の長さが1.4e5の正方形、みたいな図形は入力に存在しないということだ。
しばらくハーメルンを読んでから午前10時くらいに寝ようとしたが、眠れなかった。パックご飯を食べ、読んでいた「盤上の向日葵 上」を読み切って、下巻を50ページくらい進めたところでいい感じの眠気が来たと思い、午後0時半就寝。
02/25(木)
午後9時半起床。まずい。
食事をしてから3時間くらいかけて「盤上の向日葵 下」を読み切った。ラストに向けた大きな流れと、その結末に衝撃を受け、しばらく動けなかった。帯の煽り文句にも「しばらく立てないくらい素晴らしかった」とあるが、看板に偽りなしといったところか。
腕は確かだが口も態度も悪い刑事・石破と元奨励会員の巡査・佐野の警察ペアが主となる章と、幼くして母親を亡くし父親から虐待を受けていた、長じて将棋のプロ棋士となる上条桂介が主となる章がそれぞれあり、並行して話が進んでいく。警察ペアの章では現在の視点から過去に起こったことを探り、上条桂介の章では少年時代から現在に至るまでの過程を丹念に描いていく。最初は独立しているように感じられる2つの物語だが、時を経るごとに、あるいは捜査が進むごとにだんだん焦点が明らかになってきて、ついに最終章で2つの物語は完全に一致することになる。上条桂介とその周囲の人々の、どことなく危険で波乱に満ちた生活、また捜査によってその足跡を着実にたどっていく警察ペアの追体験が印象的だった。
このような本を読んだ後は、しばらく次に何を読むか迷うことになる。ラノベでは、何らかの感動を得ようとして読んではいないので、たいてい薄い読書体験になる。そんな中でたまにこうやって一般に高い評価を受けた本を読むと、得られた感情のあまりの違いにこういう本しか読まなくてもよいのではないかと考えてしまうが、しかしラノベを読むのは止められないし止めたくもない。
しばらく呆けていたが、そうもしていられないので、意識的に競技プログラミングに取り掛かる。AOJ-ICPCで昨日開いた問題は幾何だった。幾何の計算について、入力は整数なのだから、許される限り整数の範囲で計算するようなライブラリは作れないだろうかということを以前から考えていた。直線の交点を具体的に求めたりするのは不可能だが、例えば交差・接触判定は可能だろう。今回の問題もそれが使えそうなので、思い切って実装してみることにした。まず現在の幾何ライブラリを複製して、doubleの部分を全部long long（ただしもっと柔軟性を高めるためにusingで適当な型名をつけている）にして、割り算が含まれる計算をなくす。
おおむね書きあがってから問題を解いてみると、しょっぱなから直線の交点を求める計算が必要になってまったく役に立たなかった。残念。せっかく書いたので残しておくが、一切verifyしていないので不安がいっぱいだ。問題自体は、通常の幾何ライブラリで通すことができた。幾何の問題の難易度はよくわからない。円の半径を二分探索するか、直線の極端なケースだけ考えることで通る点の候補を絞るか、この2つの解法のどちらかしか使ったことがない気がする。
AOJ-ICPCで新しく埋めた問題のうち、AtCoderにも収録されているものを探してコピペして提出する作業をした。AC数が7問増えて2777になった。キリが良いように見える。いくつか単純なアルゴリズムの問題があったので、コードゴルフしておいた。
最初は124Bで、そこから二分累乗法を普通の累乗にすると115Bになった。さらに別の箇所の計算量を定数倍悪くして105Bのコードを作ったら、150msくらいTLをオーバーした。そこで元に戻すのではなく、二分累乗法に戻してみたら、TLに間に合う111Bになった。
昨日解いた「夕食」だ。昨日の解法ではまず毎日自炊する状態の幸福度を計算してから、徐々に食堂に行く日数を増やしていったが、もともとの最短コードを読んでみると、逆になっていた。一旦は昨日の解法で縮めておいて、105Bになったが、もともとの最短コードの解法を使うと88Bまで縮んでびっくり。確かに式の形がシンプルである。
仕送りで来たパスタソースを使ったが、シーズニングタイプのもので、パスタに絡める際にサラダ油か何かが必要なようだった。パッケージを開けてから気づいたが、家には油の類は何一つない。やむなくパスタのゆで汁を用いたが、まあ問題はなかった。
布団に入ってからうっかりなろうを読んでしまい、午後1時就寝。明日起きる気ある？
02/26(金)
午後4時半起床。執念でベッドから身を起こす。今日はホスフィン・たいぺーと3人で今セメスターのお疲れ様会をする。
集合は午後5時45分で、集合場所までは地下鉄で行くことを考えると、30分前には家を出たい。お金も下ろしておく必要があるだろう。準備もそこそこに家を飛び出したところ、午後5時半くらいに集合場所についてしまったが、どうもホスフィンが微妙に遅れているらしいので、近くのゲーセンでチュウニズムを2クレプレイした。
無事合流して、ホスフィンが予約したお好み焼きの店に行く。
𝓕𝓐𝓥𝓞𝓡𝓘𝓣𝓔焼き pic.twitter.com/lFkNZBxtV9
— こたつがめ (@kotatsugame_t) 2021年2月26日
午後8時半くらいに出て、少しゲーセンによってマッチングしたあと、先週の金曜日にも行ったバーに再度入店した。
そのあとバーに移動して飲んだ。
週記（2021/02/15-2021/02/21） - kotatsugameの日記
前回はコラボメニューに執着するあまりお酒の好き嫌いを考えなかったが、そもそも僕は苦みのあるお酒らしいお酒が好きではない。この反省を生かし、今日は甘いお酒ばかりを延々頼み続けた。相変わらず腹は下した。今日の注文も以下のリプライツリーにまとめてある。
リスポーン地点 https://t.co/u3VRnmalUb pic.twitter.com/cjOGEkQNuU
— こたつがめ (@kotatsugame_t) 2021年2月26日
3人でずっとソートなぞなぞを出題し合って、午後9時から午前3時まで6時間くらい滞在した。見て瞬時にわからないならすぐ出題者にどういったジャンルの言葉か尋ねたりしていたため、どちらかというとなぞなぞに近くなったような問題もあったと記憶している。記録が一切残っていないため、ほとんどの問題は忘れてしまったが、少しだけ覚えている問題を書き記しておこう。
- えきこさつぬのばろ*1
- おたちのまやろ*2
- あぃてでふろー*3
- かくたっでねのるろー*4
- ぐせとどまらるん*5
- おたどはるん*6
- いいいかかざせっめん*7
- いいじすせはひゅりんん*8（これはめちゃくちゃ不評だった）
- おかしたのは*9
- いきけばん*10
どういう語をソートすると面白く感じられるのかがよくわからないまま終わった。店を出て深夜の街を歩く。飲み屋街はまだ人がたくさんいた。なか卯でそばを食べ、ドンキに寄って買い物をし、帰宅。しばらく下した腹をなだめすかしながらハーメルンを読み、午前7時就寝。
02/27(土)
中途覚醒を挟みつつ、午後8時起床。あんまり疲れが取れた気はしないが、コンテストがあるので起きなければならない。食事として、昨日ドンキで買ってきたサラダチキンを食べた。あまり好きな味ではないようだ。
ABC193に出る。65分全完、42位。Dに信じられないくらい時間をかけたのと、Fが普通にわからなかった。
Aはよい。解いてからしばらく留まって考え、4分半でdcの10Bコードを作った。11Bのコードは1分半の時点で提出されていたらしいので、速度的には負けていたが、運よく短縮に成功した感じ。B、Cもよい。Dは難しい。真っ先に#を全通り試すコードを書いたはいいものの、最後のサンプルが合わない。これは手札の点数の計算ミス（c_i=0のとき点数に寄与しないとしていた）によるものだが、気づかず、確率計算を間違えているのだと思って必死に考えていた。カードの数字に重複があったりして、適当に確率を考えるとヤバそうな雰囲気が出ているが、実際は全然そんなことはないらしい。結局20分かけた。
Eは見た瞬間atcoder::crtを使う解法を思いつけたが、どうして思いつけたのかの言語化が不可能。Fは見た瞬間フローっぽさを感じてグラフを考え始めたが、どうにも条件が表現できそうにない。ここで市松模様に反転すると便利そうだと気づいたが、そのあと謎の貪欲を考え始めてしまった。しばらくしてようやくフローに戻ってきて再度グラフを考えると、今度は条件が表現できたので、実装してAC。
コードゴルフをする。Aはコンテスト中のものでよさそう。Bはいくつか言語を試したが、AWKの35Bがシンプルかつ強力だった。CもAWKの勝ち。Dはコードゴルフする気がない。E、FはACLを使うのがよさそうで、C++で適当に縮めておく。Eはclimpetさんとバトルして負けてしまった。熨斗袋さんのツイートでYQ通りではなくY+Q-1通りしか考えなくてよいことを知り、これを適用してループを減らしたりもしたが、さらに更新されてしまった。unsigned longを使う発想が非常に美しい。
ICPCのチーム紹介ドキュメントは締め切りが28日である。夜中の2時から朝の9時までずっとそれの作成をしていた。昨年は締め切りをほとんど故意に放棄した結果白紙のページになってしまったが、今年もそうなりかけていた。どのようなものを作ったかは、印刷したものが配布されてからのお楽しみである。完成したものをメールで送る前に、チームのSlackに貼って確認してもらう。さらにチーム紹介ドキュメントに関係してブログ記事を1つ作成しておいた。これの公開も、印刷したものが配布されてからである。
2021/03/09追記：公開した。
午後0時半就寝。
02/28(日)
午後9時起床。急いで弁当を温め、食事してyukicoderとCGRに備える。
yukicoderは2完。Aでつまらないペナを生やした。Bはよくわからないが適当に二分探索したら3700msで通ってFAだった。円周上を動く点に、ある特定の位置からスタートして一定の速度Wで動く点が追いつけるのは最短で何秒か？という問題は、一般の場合は簡単には解けないだろうが、Bの制約下においては円周上を動く速度よりWのほうが大きいことから二分探索で解ける。このことはコンテスト後に改めて考えたのであって、コンテスト中は微妙な怪しさを感じていた。Cは頑張ったがわからなかった。数え上げが苦手であることがいよいよ明らかになってきた。
CGR13に出る。ABCDE5完。レートは2633→2658(+25)。
Aはよい。Bは上下の障害物の座標の差を見ればよい。Cは前からやっていいことが直感的に正しく感じられる。ぐっとこらえてしばらく考えたが、どうにもよさそうなので、そのまま実装に入った。実装も、ただシミュレートして間に合うような制約ではあるが、累積和を使う線形時間の実装を思いついたので、そちらに切り替えた。Dは下の桁から貪欲して1WA。下から見た場合はほんの少しだけ自由度があるようだ。上の桁から見るようにしたが、下の桁から見ていた時の文脈を引きずってしまい、サンプルを合わせるのに手間取った。結局、一度すべて忘れて再度問題を捉えなおしたところ、うまくシンプルな問題への言い換えが得られてAC。
Eは全然わからなかったが、雰囲気で書いたコードが通った。部分木の根を飛び越えて葉の方と組み合わせるのがまずいので、順番を保ったままvectorでF_kを保持するようにした。ある頂点を見ているときは、その子らのvectorを全部マージして、さらに先頭に親の1頂点を表すF_0=1を付け加える。先頭の2つが足せる限り足して、これを今見ている頂点に関係するvectorとする。同じF_kが2つ連続するまではよい（F_{k-1}が来ると順に足して両方消せる）が、3つ以上連続したり、さらにはsortedな状態が崩れたりした瞬間、できないことが確定する。できないことが確定していない場合は、条件からvectorの長さはそれほど長くならない。
Fは「1つと残り全部」をn回聞くことを考えたが、これはNとSの個数の差が1のとき上手くいかない。そこで、先頭から順にiとi+1..nを聞くことにした。これで非ゼロなiが検出でき、それを用いてi+1..nから-でないものを探せる。nがどうであるかは、これまで見つかった結果とiとi+1..nを聞いたときの値から復元できるので、これにかかるクエリ数はn-1。NとSの個数の差が1以下のとき、0..i-1にまだ1個-でないものが残っている可能性があるが、これは二分探索で見つかる。0..i-1に-でないものが残っているかどうかを判定するため、さらに1回聞く必要があって、合計でだいたいであるようだ。微妙に回数をオーバーしているのに気付かず投げてしまい、pretestで落ちた。修正できずにコンテスト終了。
問題は、-でないものが残っているかを1回使って判定しなければならないことにある。1..i-1とiを聞くことにすれば、非ゼロなiを検出したとき、1..i-1には必ず1つ-でないものがある。これで判定の必要がなくなり、でACできる。
ラノベを1冊読んだ。「魔王2099」というもの。非常に面白かった。昨今は「長い眠りから目覚めると魔法が退化しており、古代の技術で無双する」系の話が多い中、この作品では眠っている間に高度に発展した社会に翻弄される魔王が描かれる。正直無双を期待して手に取ったので少しストレスがかかったものの、くじけず頑張る魔王のキャラクターが心地よかった。恵まれた容姿を武器に顔出し配信者として活躍するのも面白い。それでいて舞台は練りこまれたSF社会で、物の名前や慣用句まで世界観に合わせて変更する手の込みよう。
昨日のBが縮められていた。AWKで抜き出してsortでソートしてdcで出力・エラー処理をするbashコード。うーん、なるほど。
