/ 最近 .rdf 追記 編集 設定 本棚

脳log[20211125]



2021年11月25日 (木) [AtCoder] 精進。ARC124-D「Yet Another Sorting Problem」(ギリギリ黄 diff。そんなアホな)。これは Swaps の仲間なのかな>20200826p0120211022p01。3つの中でこれが一番頭が爆発した問題だった。実際にソートして数を数えても許されるあたりは厳しくはないんだけど、添字と値が入れ替わって入り交じるスワップ操作で頭がこんがらかる。そして最後の最後にも罠があった>(gn-gm).abs提出 #27485094 (AC / 515 Byte / 188 ms)。ほぼ一日かかった。■考え方はいろいろあるのかな。自分はまず反対側の領域にもぐりこんでいる要素を探した。そしてそこに本来収まるべき要素を探し、探した要素があった場所に本来収まるべき要素……を芋づる式に探してグループとした。ただしグループは前半領域、後半領域のどちらかの中にだけ作って、領域をまたぐグループは考えなかった。こうやって1つずつ反対側に移動している要素の位置を移動しながらついでにソートもしていくと、最終的に反対側に移動している要素はなくなり、前半後半のどちらかに閉じて位置を交換していてソートされなかったグループが残る。反対側の未ソートグループが利用できる場合は利用して互いに交換回数を節約しながら全グループをソートする。この、手続きに基づいた解法がどのような考えからひねり出されてきたかというと、必ず行わなければいけない操作を無駄なく行う、というところから。貪欲法?