脳log[20220910]

2022年09月10日 (土) [AtCoder] 精進１。今日あったユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)-E「Chinese Restaurant (Three-Star Version)」(青 diff)。やることは即座にわかった。ズレの大きさと回転に応じたズレの変化量。制約が大きいので変化量の増減を記録してその累積で変化量を知る。変化量の累積で操作後のズレを知る。N の偶奇に注意が必要なこともわかっていた。でも完成させられなかった。■提出 #34765127 (AC / 487 Byte / 200 ms)。結局終了後２時間近く時間をかけることになった。一発 AC は嬉しい。類題を２問知っている。ABC240-F「Sum Sum Max」(水 diff)と ARC077-E「guruguru」(黄 diff)。■尺取りで変化量を増減させても良かったみたい>ツイート。ややこしさは変わらんけど、特徴点とその取り扱い方はもうわかってるので、最初から整理して書けるはず。あとでやってみよう。■いや、だめだ。頭が爆発する。もう考えたくない。(ゲーム実況見てる)。提出 #34779383 (AC / 513 Byte / 236 ms)。尺取りです。二重累積和とどちらがわかりやすい？ どっちももう見たくねー。■■■精進２。同 ABC268-F「Best Concatenation」(青 diff)。制約の大きさと制限時間が特に長くないことから、１回通り過ぎるだけでスコアが求まるのがわかる。そうするとソートが問題。最初は X が多い順かつ数字の和が小さい順でソートした。これは、X が多いけど数字も大きい文字列の配置を間違える。X が多ければ配置は前だけど、数字の大きさを優先すれば配置は後ろだ。■提出 #34767243 (AC / 308 Byte / 742 ms)。ヒントを見ました。「アライグマ「F問題は変なソートなのだ！　2つの文字列のどっちを前にした方が得か考えてソートするのだ！」 フェネック「どっちを前にした方が得か考えてソートするのはDPの前処理でよく出るから覚えてねー」 https://t.co/rr67x9BfRi https://t.co/BlGbkt3aBV https://t.co/NkWMSVs5Yu」 すでにわかっていたことに確証を与えただけにも見えるけど、「2つの文字列のどっちを前にした方が得か考えてソートするのだ」というのが無意識に作用していた。二項関係だけでソートしていいんだと、知らずに気付かされていた。推移律はどうですか？ よくわかりませんよね。祈りながら提出したら AC だっただけです。■ゴルファーの提出(#34766963)を見てると複素数を使ってるんだけど、そういえば自分が書いたソートのための比較関数が外積と同じ式だった。この前の外積を使う問題(ABC266-C「Convex Quadrilateral」)を自分は複素数で解いたから(#34376180)、なにかしら関係があるのだろうか。ソートからどうして複素数が出てくるのか飛躍がありすぎてさっぱりわからんけど。「（解説を見て）なるほどこれ「Xの個数/1の個数」の降順にソートしてたのか」という声もあるけれど、こちらもさっぱりわからない。俺にもなるほどさせてくれ。