up<k を up<=k にした。頂点１に向かって K 階層遡っても、それって１手前にいた頂点だから無駄じゃね？ と思って、移動先を K 階層下、１階層上のち K-1 階層下、２階層上のち K-2 階層下、……、K-1 階層上のち１階層下に限定していたのだけど、まっすぐ K 階層上も移動先に加えるべきだったということ。なぜか。折れ曲がるように移動して到達した頂点からまっすぐ K 階層上というのは、初めて訪れる場合がある。K 階層まっすぐ下るだけが移動じゃないのだから「１手前にいた頂点だから無駄じゃね？」は勘違い。■Crystal で通している人の提出 #67550795 を見ましたが、えー、全然違うー。Ruby で同じことをして通りますか？ だったらだいぶ短く簡潔に解けるということだけど。■■■寝て起きたらフレンズさんのツイート(１、２)や他のブログで読んだことが頭に入ってきた気がする。たぶんだけど BFS をするのかな。頂点ごとに訪問済みフラグを持つわけだけど、追加で K 状態を区別する。これは K 歩の何歩目で訪れたのかを表す。さらに追加で直前の頂点も持つ。直前の頂点へは次の移動ができないのでこれも状態として区別する必要がある。そうすると状態数が NNK になってよろしくないのだけど、直前の頂点が２種類あるとその後の遷移はすべて網羅できているので、３番目以降の直前の頂点フラグはすでに立っているものとして良い。ということが書いてあって、同じことを(もしくは不正確なこと不十分なことを)繰り返しているだけだと思うんだけど、昨日説明を読んだときは何を言っているのかちんぷんかんぷんだったんだよね。何度文字列をなぞっても頭に入って来なかった。脳みその可塑性応答性が低い！■提出 #67610103 (WA×34/AC×19 / 665 ms)。2NK 状態の BFS を書いてみたけど WA だった。サンプルは通るんだけど何が足りないんだろう。■提出 #67610224 (TLE×2)。バグの原因はちょうど K ステップの移動の次の一歩は直前の頂点がどこかに関係なく移動できるということを考え忘れていたこと。これを直して十分に遷移ができるようになったら WA がなくなって TLE が２つ出た。3.3 秒 以下の 3098 ms と 3225 ms だからあとちょっとなんだよなあ。■提出 #67610541 (AC / 2809 ms)。変なことしないで３要素の配列をキューに入れたら良かった。自分で書いたから Crystal の人のスクリプトも読めるようになったけど、N+N の状態数で K ステップを１単位とする BFS をやっているだけに見える。本当に？ それだと K ステップの中間ステップが重複する無駄が生じない？ (K 歩ごとに直前の頂点フラグがリセットされているようだから)幅X以内であれば一つの電波塔で賄う」の解釈が自分と違うんだよな。前から見ていくと、(1,4)←距離３以下だから同じ基地局、(4,5)←距離１だから同じ基地局、(5,8)←距離３だから同じ、(8,11)←距離３だから同じ、(11,12)←距離１だから同じ、結局「幅３以内であれば一つの電波塔で賄う」ことにすると {1,4,5,8,11,12} になって必要な基地局が１つだけなので条件が緩い。次は０と３の中間である１か２を条件にして二分探索を続けよう、ってならない？ その後幅１と幅２のどちらを条件にしても今度は必要な基地局が {1},{4,5},{8},{11,12} の４つになって使える基地局の数(３)を上回ってしまうので、解は２と３のあいだ！(困る) というのは別の話でありもう書いたこと。
途中、どれくらい高い地点を通ることができるかは大気圧および液体の蒸気圧と密度による。最高地点において管内の圧力が液体の蒸気圧に近づくと液体はキャビテーションを起こしはじめ、気泡の膨張が重力による圧力差を吸収してしまい、いずれサイフォンは停止する。」 へー。持ち上げるためには大気圧に負ける圧力が必要で(？)圧力が低くなりすぎると水中から気体が出てきて(沸騰？)吸い込めなくなる？ 気泡が圧力の伝達を阻害するのは油圧ブレーキのエア抜きが大事な理由だし長い下り坂でエンジンブレーキを利用すべき理由でもある。大気圧の大きさは気泡が生じるまでの限界を高めそう？ 大気圧を固定したとき、液体が水銀のときの限界が約 76 cm で、水のときの限界が 10 メートルくらいに決まっているらしい。大気圧と液体の蒸気圧と液体の体積当たりの重さ(密度の言い換え。物理をやらなかったので重さと質量の区別は曖昧。面積当たりの力である圧力に呼応するもの？)の３つのバランス。水銀の限界は 760 mmHg (大気圧) と符合しているけれど、じゃあ水銀の蒸気圧が限界に及ぼす影響はどこに読み取ればいいのだろう。蒸気圧って？ 「
2010年、オーストラリア・クイーンズランド大学の物理学者、スティーブン・ヒューズが辞書など社会で一般に説明されているサイフォンの原理は誤りであると指摘した」とも書かれていた。今からたった 15 年前のこと。みなさんそれも踏まえたうえで「わかる」「あたりまえ」という反応をしているのだろうか。自分は名前と結果しかわかりません。
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)。覚えてないけど。10^7)に制限されている意味はわかっていたつもりだけど、区間の上限が (10^7)^2 だということとその意味に気がついていなかった。十分な大きさの素数までを列挙すれば、１つの素数のべき乗(2,4,8,16……など)とすべての合成数(4,6,8,10,……など)が列挙できて、消去法で区間内に高々１度しか現れない大きな素数も見つけられるんだけど、「十分な大きさ」を決めるのは区間の幅ではなかったのだった。提出 #67224096 (AC)。■F 問題 Socks 4。N すくみ的な状況。手持ちの靴下を C→D(→E)→C と入れ替えて戻すのは必ずどこかで判断ミスをしているので堂堂巡に陥る心配はしないけど、問題設定がすこしでも複雑になると自己ループの除去とかできなくなる。■火曜日……２晩……。６月30日は ABC412 の代わりに消えた？÷6^N をループの外に出してこれなので、もし２秒制限で TLE だったら、2,3,(4),5,(6) の N 乗までを前計算したりしたかな。あと、前後のループの後半と前半で確率の値が使い回しできそう。……ということは、ループ全体で足し引きを通算して再構成するともっと演算が減りそう。考察が足りなくて最適解が見えていない可能性。■F 問題 Contraction。制限時間が４秒。やや高の 525 点。辺をマージするだけなのかなと素朴すぎる方針を立てて実装したところ、およそ１秒で時間は間に合ったけど WA が多数 (#66981976)。必要な処理を抜かして時間を稼いでいる疑い。■■■F 問題。終了 12 分後に提出したものは WA×31 だった (さっきの提出)。翌朝目覚めたらデバッグが完了していた (#66988575)。頂点 a と b をマージして a が代表として残るとき、b とのみ辺で繋がっている頂点 c を a に付け替える。そのときに辺を a と c 双方に登録しなければいけないところ、a から生やす辺を忘れていた (30 行目)。やっぱり時間内(E 問題に 40 分かけたがまだ 30 分と少し残っていた)に解けてほしい難易度の問題だったけど、実際にはひと晩(≠ひと晩中)かかったなあ。解答に使った知識は UnionFind とマージテク。■今日ある第六回日本最強プログラマー学生選手権-予選-（ARC201）には参加しません。最初の２問が 500 点だけど、どう考えてもはりきった出題者が一筋縄ではいかないひねった問題骨太な問題を出してくるに決まってるんです。先週の ARC200 (div.2) の A 問題 (500 点) が解けなくてゼロ完だったことで私はいたく傷ついています。■■■D 問題。Array でやってもだめだった (TLE×13)。ちなみに String だと TLE×12 だったから、Array よりマシ。そして、クエリ逆読みをやってみたら WA×18 だった。「一瞬で断念した」だけのことはある。デバッグ完了 (AC)。それから最初の解法だけど、リンクリストのノードは Q 個ではなくクエリ２の数だけで十分みたいだった。クエリ１と３でコピーしなければいけない気がして自分は空文字列を追加した体で新しいノードを作ったんだけど、一度作ったノードは不変なのだから、参照をコピーしてノードを共有するやり方で問題なかった。当該車両の運転士が車両のパーキングブレーキシステムをオンにし、待機場停車時にフットブレーキ操作を行ったにもかかわらず、パーキングブレーキが有効に作動しなかった」ときにどんなフィードバックがあったのかなかったのか。これはブレーキをかけることとブレーキがかかることが一致しなかった例。自分は古い人間なのでこの２つがワイヤーで直結している(力学的)システムが好きです(大型車両で補助動力がうんぬんはおいといて、自分が乗る車は)。ちなみに自動運転のエラーではなく手動操作中の事故。しかし原因は(車内の？)通信ネットワークにある。
○○ を探す。■B 問題 Citation。１回間違えて愚直二乗解法で書き直した。与えられた値の中に答えがあると思い込んだわけではないのだ。それも想定して、でも反例が出てこなくて間違えた。とても難しい問題。以前から書いてるけど、否定で定義される MEX みたいな問題が苦手。問題名は引用かなと思ったけど意味がわからない。調べたら召喚状、出頭(罰金)命令書、賞状といった意味が出てきた。意味があまりにとっちらかっている。形式に対する名称なの？ なんにせよどれもしっくりこないような。■C 問題 Equilateral Triangle。円周 L を３等分して L/3 個の三つ組の掛け合わせの和。■D 問題 String Rotation。まず先頭に近い方から前後ペアを見つける。どのような。前後が大小の順番で並んでいるペア。次は見つけたペアの大きい文字をどれだけ後ろへ送るかを決める。より大きな文字の前か最後尾。■E 問題 Pair Annihilation。焼きなまし？(問題名←それは annealing こちらは対消滅) F 問題より考えた。最小全域木的な操作や重み付き UnionFind を考えたけど、うまくない。葉からの DP (with マージソート)を考えたけど、うまくない。実は葉から貪欲にペアを作っていくのが最善だった。それがわかればあとはがんばって書く。■F 問題 Connecting Points。２乗が通るのでやるだけですか？ TLE×3 だった(#66577100)。もうええやないですか。通してください。できることはもうやってるんです。プライオリティキューに無駄要素が詰まりがちだから、値が重複しないように気をつけました(プライオリティキューにはユニークな距離の値だけを入れ、距離に対応した頂点対リストは Hash に入れた)。新頂点を追加するときに点間距離ではなく連結成分対新頂点の最短距離をソートによらず選び出すことでさらにキューに入れる要素を減らそうとしたら、これは遅くなりました(TLE×7)。お手上げ。