最終更新: 2021-07-12T20:54+0900
A 数列を後ろから見ていく方針は早くに決まったのだけど、初項を [1,0] ではなく [1,1] にしていたミスでいつまでも答えが合わなかった。あと余りを取り忘れて 1 TLE。
もう 54 分経っている。
A 数列をソートすれば賢く答えが求められそうだけど、何も考えずに探索しても良さそう。この前の ABC204-E Rush Hour 2 と違って最初から実数解が求められているあたり、罠もなく素直なのでは？
デバッグ出力を消し忘れて 1 WA。bsearch メソッドで極小値を求めようとして 1 WA。三分探索(名前だけは知っていたが初めて書いた。「三分探索を救いたい - Qiita」)を 100 回試行しようとして 1 TLE。ざっくり半分の 50 回にして AC。本当は探索範囲の幅が許容誤差以下になったかどうかを終了条件にすべきだったそれもダメ？。
AC までおおよそ 30 分だから B 問題は A 問題より簡単。
盲滅法な探索では時間が足りない。考えても時間の無駄なので興味本位で解説を読んだ>「C - Calculator 解説 by maroonrk_admin」
フィボナッチ数？ 「競プロ典型 90 問」でも見かけたが、この数列がどうして頻繁にあちこちに登場するのかわからない。限りなくありふれたジェネレータなのか(知らなかったけど A 問題にもフィボナッチ数が現れていたらしい)。あと、計算途中で１を足すという行為が、新しい系列のフィボナッチ数列を開始すること、それらずれたフィボナッチ数列を串刺しにした和が数列として現れるということもあまりピンとこない。そうなの？ そんなこと漸化式を見てわかる？ 足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。
とりあえず実験をした。x,y=1,1 を初項として操作３と４を繰り返すとどのように値が増加するか。大体 80 数回で N の上限を超える。今度は x,y=0,0 でスタートして 80 数回の１か所でだけ +1 をすると、80 数回の操作３、４の結果がどういう値になるのかを調べた。これは並べるとフィボナッチ数列になった。
つまり、次の提出における A 数列というのは、フィボナッチ数列を貼り付けたものではなく、+1 するタイミングによって操作３と４を繰り返したのちのちにどれだけの影響を及ぼすかというのを予め調べた実験結果なのである。
「貪欲をすればよい
」と解説に書いてあったので貪欲をした。フィボナッチ数列の増加のしかたを見れば組み合わせでどんな数字でも作れそうな雰囲気はある(基数の冪乗を大きい方から取っていくのと同じように)。
「この時，i と i+1 両方で操作することはありません． なぜなら，
」は読み飛ばした。解説の細かい部分にこだわってもわかりません。
WA の原因は問題を読み誤っていたこと。x か y のどちらかが N になればいいと思っていたが、そうではない。
x と y を取り替えればいいのだから、仮の操作列を作ってから必要に応じて操作１と２、操作３と４を交換するようにした。最初からきれいな解答を作ろうという努力はあきらめている。
ARC-C が自分のいるところからどれだけ高くにあるかは垣間見られたのでは？ 時間内に B 問題まで解けただけで上出来なのに、レイティングは下がるんですよ。緑に対してあまりにひどい仕打ち。A、B がどちらも茶 diff だといっても、ARC に参加する層にとっての茶 diff だという意味で、ABC の茶 diff 問題とはくらべられないと思うんだ。へなちょこながら ARC に参加する意気にレイティングで報いてほしい(嘘です)。
それもダメ？ [[実数の二分探索・三分探索はループ回数を決め打ちしようね - えびちゃんの日記|https://rsk0315.hatenablog.com/entry/2020/04/29/155009]]。探索範囲が過大(過小)な値に寄っていったときに、浮動小数点数の密度が足りなくなって無限ループする？ 無限ループしていないことをもって OK としていい？
