最終更新: 2021-06-02T21:11+0900
緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない。
だから青色。難しかったん。１年くらい前に ABC004 を埋めようとしたときは力が及ばず C 問題までしか提出に至っていなかった。
今回も一発 AC とはいかなかった。原因はすぐに推測できて、緑色が原点から離れない想定が誤っていたのだと思った。
たとえば赤か青の片方が極端に多いとき、外側に広がっていくよりも中心にある緑色の全体を移動させてでも中心に向けて移動する方が低コストになる分岐点がある。
しかしそれを想定するとコードにするのがさらに難しくなりそうで困った。
ちなみにこの提出の方針は……。赤と青をそれぞれ -100 と 100 を中心にして原点の左右で平らに並べる。原点は超えない。数が多ければ外側により大きく広がる。そのあとで緑色を原点を中心として配置していく。左右のコストを比較して赤と青を押しのけながら。
提出に至らなかった１年前の方針は、RGB の数から重心を求めて云々という感じ。ひょっとすると緑の配置拠点を原点に限らず適切に移動することで、WA だった方針のまま AC に持って行けた可能性が？
「J - 長い長い文字列」(提出 #19035422) とか、「K - 転倒数」(提出 #18029328)とか、脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい。今回は両方出てきた。(クラスのメソッドの並びが不揃いなのが気になる。左を先に書くで統一しておきたかった)
イメージとしてはビー玉をざらざらと流し込んでから、抵抗の強弱を感じ取りつつ右に左に均す感じ。最大で900個程度の広がりしか考えなくていいからなんとかなっている。
Ruby の他の提出を見るとゴルフをしていなくても 300 バイト台の短い提出がいくつもあるし、内容も、候補を並べて最小値を選ぶ、二分探索で解(極小値)を探すなど、特に大層な道具は必要としていない。それは、頭の中で十分に理解して整理できているから書けるんだよなあ。
できないからソースコード上でメソッドと複数のインスタンスに分割して整理しています。結果としてひと味違った解法になったと思う。
たぶん抗力の計算が間違ってるんだよね。
押した力を上限として０以上それ以下の力しか発生しないはずだけど、なんだか負の抗力によって隣の障害物に引っぱられていきそうになってる。それだと引っぱってる方はともかく引っぱられる方は、必ずしも安定した、低いエネルギー状態にあるとはいえなくなる。
これが問題にならない理由もわかるけど、それはクラスの外部、インスタンスの利用方法にあるのであって、クラスの、メソッドの定義としては間違っている。