脳log[20211118]

2021年11月18日 (木) [AtCoder] 精進。ARC107-C「Shuffle Permutation」(水 diff)。７か月前に「緑がほぼ埋まってきて残っているのは解けなかった問題ばかり。そこで水色下位に手を出すも下位とはいえ水色はぱっぱっと解ける雰囲気ではない。あれもこれも行列の問題で、問題のその操作で何ができるのかさっぱりわからない」と書いたとき念頭にあった問題の１つだけど、今日は特に詰まるところなく解けた。操作の前後が可換であること、行の操作と列の操作が独立していることを読み取ってから UnionFind を道具として選んで順列を計算するところまで。むしろ無効な交換を考えなくてもいい問題設定の優しさが目についたくらい(行や列のアイデンティティをどう定義すると効率がいいのか考えるのに一番時間を使っていたのだけど、不要だった)。成長しているのだなあ。提出 #27321607 (AC / 513 Byte / 66 ms)。■直近の ARC128 が茶 diff も緑 diff も解けないゼロ完だったとしても(成長しているのかなあ)。