脳log[20211026]

2021年10月26日 (火) [AtCoder] 精進。ARC063-E「木と整数」(黄 diff)。提出 #26833318 (AC / 1419 Byte / 463 ms)。すごく、難しかったです。ノードに持たせた情報は、入力で与えられた確定数字と、数字までの距離。たとえば数字が P で距離が D なら、そのノードが取り得る値は P-D から P+D の間で１つおきの数字のどれか。これを頑張って子ノード間でマージしながら矛盾なく根っこまでたどり着けたら答えは Yes。根っこの値を１つ選んで今度は下りながら子の数を確定していく。今のところ Ruby での AC は３つなんだけど(「Ruby によるすべての提出」)、どれも異なる考え方で書かれている気がする。どういうことなんだ？ さておきこれで黄 diff の AC は 10 個目。着々と増えている。■解説を読むとノードに持たせるのは数字と距離ではなく取り得る数字の範囲にすると楽そうだった。それでやると Corvvs さんのこちらの提出になるようだ>#4817029。自分でもやってみた>提出 #26837318 (AC / 722 Byte / 434 ms)。枠組みはさっきのとほぼ共通なんだけど、子ノードのマージ部分であれこれ考えずに min/max で済ませられるのがすごく楽。他にはプライオリティキューで解いている人もいますが……(根本の方針がさっぱり想像できない)。小さい数字から順番に埋めていってるっぽい。それで自然と均衡点が定まってくるというのはなんとなく想像できるけど、なんとなくだよ。そのやり方でうまくいくときは必ずうまくいくということに確信が持てない(ので自分では書けない)。こちらが参考になる>「ARC063E 木と整数(800) - tekiheiの日記」。ひっくりかえっても自分の頭からは出てこない発想。