脳log[20230219]

2023年02月19日 (日) [AtCoder] 精進。今日あった Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）-E「Make it Palindrome」(水 diff)。時間中は、各数字がすべての連続部分文字列の中で左側に何回出現するかと右側に何回出現するかを数えようとしていた。それはうまくない。ヒントを読みました。「E: バケットソートしてから端から貪欲」。すべてのペアについて個別に考えるのが許されない制約だけど、端から貪欲が可能ならペアを考えても良い。ただし何らかの属性でひとまとめに取り扱う必要はある。■提出 #39053926 (AC / 210 Byte / 342 ms)。グループ化してソートして積算しました。ある要素について左右にある要素数のうち少ない方を考える。少ない方の要素数が M1,M2 である２つの要素がペアになったらそのペアを回文の中の比較対象として含む部分文字列は min(M1,M2) 個ある。■Ruby によるすべての提出を見てると自分の 342 ms は目に見えて遅い。最遅である。左右にある要素数の規則的な増え方減り方に注目すればソートする手順が余分で、そのせいで遅くなっている。提出 #39117164 (AC / 162 Byte / 157 ms)。遜色ない速さになった。実はこの書き換えは全然すんなりいかなくてバグに苦しんだ。理解の浅さが露呈したわね。■■■D 問題「Marking」の設定が灘校文化祭コンテスト 2022 Day2-A「ACPN」と同じだということに遅まきながら気が付いた。それを解いたときの日記に「実験したら M 個の剰余が出現する周期は K と M の最大公約数で分割されるようだった。たとえば M が 10 なら剰余は 10 種類あるが、K が 5 のとき最大公約数は 5 で、M 個の値は周期 2 の組が 5 組となって出現する。あとはこの周期で N が割り切れるかどうか」と書いてあるんだけど、えっと、なんで「割り切れるかどうか」なのかよくわかりません。去年は今より頭が働いていたのだなあ。