a,b,c)を並べて前後２項で r に関する等式を作って(b/a==c/b)、通分したら b*b==a*c で判定できるらしかった。なるほどゼロがあると土台が成り立たない。Ruby には組み込みで Rational (有理数) クラスがあるのは知ってるんだけど、計算量が読めないのと、Rational がないと解けないとなると Ruby でないと解けないということになり、それは甘受できないのだった。オーバーフローに対する警戒心のなさなど普段は Ruby に甘えまくりだけども、謎の線引き。■E 問題 Reverse 2^i。２分割してそのままか前後を入れ替えるか。■F 問題 No Passage。やるべきことがよくわからなかった。できるできないは別として G 問題の方が求められていることがわかりやすかった。F 問題。あるマスの移動先(最大４つ)のうち２つまでゴールまでの手数が確定しているなら、大きい方+1 の手数でゴールできる。０手ゴールからじわじわ確定範囲を広げていく。終了２分前に間に合わせた提出 #67355089 は TLE×6 だった。判定と書き込みに時間差を付けてきっちり分けないとサンプル３が合わないのだけど、その結果キューに同一座標が複数回入るようになってしまった。９行目で事後的に弾いているけど、Ruby でその無駄は許されなかった。キューに入れましたよということだけを記録するメモを用意すると TLE×5 に減ったけどまだダメ。２次元座標を１つのキーにして配列参照を減らしたら TLE×3 だけどまだダメ。予めキューを H*W 本用意するのをやめて今と次の２本だけにしたり、キーの増減を代入してしまって演算子を減らしたりしてやっと AC (#67360123)。時間内の提出はたしかに多少の無駄はあったけど、許されないほどではなかったと思う。そこから AC までの改善は、はっきりいってしょうもない。■G 問題 Big Banned Grid。問題の概要はすぐわかる。それをどう実装するか。思いつけば実装は軽かった。提出 #67363448 (AC)。グリッドの左辺下辺に接した障害物からスタートして、障害物を伝って上辺右辺まで辿り着けるかどうか。F を捨てて G に粘着していれば時間内に解けたかもしれんけどね、気持ちが負けてるからあわよくば G をという発想にならないのであって、実際には可能性はなかった。■G 問題は ARC076-C「Connected?」っぽさがある。どちらも何が障害なのかを見切るのが大事で、実装は難しくないという点が共通。障害の正体も共通。これは解いたあとの感想であって、コンテスト中に一読したときの印象はフレンズさんのツイートの通りに ABC361-G「Go Territory」だった。あれは UnionFind なんだけど碁石(障害物)の配置から隣接頂点を引くあたりの実装が重かったので、今日の問題におすすめできる解法ではない。今日のは障害物で BFS/DFS をするだけで良かった。■■■F 問題。自分のやり方は実はあまりうまくなかった。どうやっていたか。ゴールまでの手数が確定したマスがあるとする。これを自マスとする。その隣接４マスに未確定のマスがあるとき、未確定のマスの隣接４マスに自マス以外の確定マスがあるなら、未確定マスを確定予定であるとしてキューに入れる。これは自マスを中心とした周囲８マスに加えて上下左右に２マス離れた４マス(合わせて 12 マス)の確定状況を調べることになる。定数倍が重いですね。どうやら想定解法(フレンズさん情報)は訪問済みフラグを数値で持って２回目の訪問で初めてキューに入れる BFS であるらしかった。なーんだ。TLE×2。←想定解法でもダメです。提出 #67382500 (AC / 1440 ms)。自分の不器用な解法が 1941 ms だったのに比べると想定解法は 25 % 速い 1440 ms になるポテンシャルがあるみたいだけど、配列を１次元化するような定数倍の改善なしでは TLE が避けられないのに変わりはなかった。どうあっても制約に泣かされたんだな。制限時間が通常と違う 2.5 秒であることの意味は、C++ と Python で解法の優劣により AC と TLE が分かれるように制約と時間でぎりぎりの調整をしていますよ、ということであって、これは即ち Ruby では針の穴を通すような最適化をして初めて AC になるかもしれないし不可能かもしれない、ということを示唆している。要するに、2.5 秒を見たときから予想はしていた。だからこそ最初の提出からループを展開したコピペコードを書いていたのだけど、足りなかったのだなあ。■■■D 問題。半年前にあった ABC390-B に Geometric Sequence というドストレートに等比数列の判定を行わせる問題があったらしく(覚えていない)、自分の提出を見てみたらこれ #62034196。to_r して b/a を比較している。「Rational がないと解けないとなると Ruby でないと解けないということになり、それは甘受できないのだった」とはなんだったのか。きっちり楽してるやんけ。あ、でも次の日に今日と同じ式変形を試して提出してる (#62124460)。覚えてないけど。