",,,,,".split(',') は空になる。論理的な結果が欲しければ第二引数に -1 を渡せばいい。nil を足し算してランタイムエラーを出すのを避けるには .to_s する方法があるけど、自分の好みは文字列埋め込みかな。明示的な型変換はダサいと思ってる。他には文字列と配列の明示的な .dup も書きたくないものの例。なんでだろうね。文法的なキーワード(これも書きたくないもののひとつ)と同じく、形式的で冗長で、必要ではあるかもしれないけどノイズであり、自分が書いているロジックとは無関係だと思ってるからかな。もっとも、アプリケーションドメインとソリューションドメインの対比で考えると、形式的だろうが冗長だろうが足下の物理的側面を無視すべきでない状況があるのかもだけど。■B 問題「Delimiter」。Ruby が入力を改行区切りで与えてくれるので reverse して出力するだけ。■C 問題「A+B+C」。予め全組み合わせを試して作れる和を列挙しておける制約。判定は Hash で。Hash も二分探索も使わないのは横着なのよ。■D 問題「String Bags」。なんの工夫もなく試行して答えを出して許される制約。何回の操作で何文字目まで作れたかの DP。■E 問題「Insert or Erase」。効率的な insert/delete ということで、SortedSet がない Ruby の頼りになる味方 BIT の影がちらつくけども、次の要素/前の要素をポイントするリンクリストを構成すればいい。■F 問題「Earn to Advance」。制約が小さく見えるけど制限時間が４秒。パラメータが多くなりすぎるのをどうすれば良いのか。位置(i,j)、待機した回数、パス上の最大の P、所持金。所持金は必ず P 未満になるはずで、待機した回数が増えるほど所持金も多くないと割に合わないというあたりで候補を整理できそうに思ったが、それでは TLE×20 が TLE×14 になっただけだった。Array#bsearch_index と Array#insert でソート列を維持する仮実装でそれなのでまだ改善の余地はあるのだけど、それで TLE が完全に解消されるのかどうかがわからない。実装をがんばるより頭を使うべきところなのではないか。■■■@2024-03-13 F 問題。ルートを逆順に見ていきながら、待機数と残コストのペアを候補として記録していく DP をした。ゴールまでの残コストがわかっているので、各マスで即座に待機数を決めることができて、パラメータリストから経路上で最大の P というパラメータを消すことができる。提出 #51184903 (WA×9 / TLE×6) のち 提出 #51185273 (AC)。WA の原因は 22 行目と 25 行目にあって、十分に待機してみる候補が不足していた。TLE の原因は 26 行目にあって、配列を比較するソートが遅い。■十分に待機しない候補とは何かという補足。最初に候補として考えていたのは、まったく待機せずにコストを先送りする候補と、ゴールまでのコストを賄うのに１回だけ少なく待機する候補。これは何かというと、(1,1) から最大の P に到達するまでのパスで、待機して得た所持金と負担したコストの差分次第では、最大の P で待機する回数を１回だけ節約することができると思ったから。そういう例外的なケースに注目するあまり、最大の P で十分に待機するという当たり前のケースが抜けていた。■気になるのは、各マスにおける候補の数がどれだけ膨れ上がるかということ。22 行目と 25 行目を見て上か左に１マス移動するごとに３倍になると考えるなら破綻する。実際には待機数が増えたなら残コストは減らなければいけないという選択が働くので、待機数０の候補も残コスト０の候補もそれぞれ１つだけしか残らない。３つの候補のうち２つがそういうものだ。大体は効率的な待機と効率的なパスによって淘汰されると期待しているんだけど、待機数０、待機数１、待機数２、……と、ゾンビのように目のない候補が列をなして処理コストを引き上げる懸念がないではない。最悪の場合はどうなっているだろうか。ゴールまでのパスの数だけ候補があるという最悪のケースがありうるだろうか。その数は 2N から N を選ぶ組み合わせみたいな数になるんだけど。それよりは P や R、D の上限から待機数とコストの種類数が 10^9 に制限されている方が先に天井になるが、それでも解説と同じ O(N^4) にはならない。候補数の上限が N^2 で抑えられて初めてそう言えるが……抑えられるんですか？■さっき「待機数が増えたなら残コストは減らなければいけない」と書いたけど、現在のマスで待機して得られる所持金が p だとして、「待機数が ds 増えるなら残コストは p*ds 以上減らなければいけない」と主張しても良いのではないか。提出 #51204120 (AC / 1666 ms)。マイナーチェンジを無視すると実質的な変更は 26 行目のみ。条件式が２つ増えている。最初の AC が 2167 ms だったから、まあまあ早くなった。個別のケースを見ると４桁 ms かかっていたケースが１つを除いてほぼ 10 倍早い３桁 ms になっている。最後に残った４桁 ms が 1666 ms だということ。けっこう効いたね。そして、自分の解法はハックケースによって撃墜されうるものだったと、詰めの甘さが明らかになったような気がします。テスターさんの想定嘘解法に入っていなかったのでしょう。