脳log[20220911]

2022年09月11日 (日) [AtCoder] 今日あった ARC148 のふりかえり。自分のすべての提出。■■■A 問題「mod M」(茶 diff)。２以上の好きな数で割った余りの種類を最小化するのだから、答えは１か２。それを見分ける問題。ある数 M があって、A 数列のすべての要素が割り切れるときは種類数１。ある数とは GCD。ところでこの他にも、定数 B を使って A 数列のすべての要素がある数 M の倍数+B で表せるときも種類数は１になる。サンプルの３がこれ。■提出 #34784727 (WA×5)。A 数列の GCD を使う代わりに隣接２項の差の GCD を使えばサンプルの３も通る。WA は gcd メソッドが０を返す場合があることを知らなくて判定条件を間違えた。■提出 #34785321 (AC / 96 Byte / 177 ms)。■■■B 問題「dp」(緑 diff)。DP は解けないので貪欲法でやろうとした。先頭から見て最初の p は必ず反転させなければいけない。L が決まる。R の候補をすべてリストして１文字ずつふるいにかけた。■提出 #34791453 (WA×18/TLE×1)。AC が 60 個あるからそれほど悪くない。終了後の提出 #34804071 は WA 無しの TLE×1 なんだけど、10 行目の L+1 を L に変更しただけなんだな。off-by-one エラーってやつ。TLE である 04_corner_11.txt はどんなコーナーケースか。ppppp....ppppp だろうことは想像に難くない。■提出 #34804490 (AC / 64 ms)。連続する p を一塊で扱うようにした。一番後ろの p を使わないで得をすることがないので。■■■C 問題「Lights Out on Tree」(水 diff)。与えられた頂点集合の上下関係を知るためにダブリングを書いたり、深さの偶奇が関係するかと思って深さを記録したりしたけど、実は直接の親子関係しか関係しなかった。ボタン操作の基本は「表向いてる親を裏返して、つられて反転した子孫ノードを裏向きに戻すために直接の子を再度裏返す」なんだけど、直接の子が最初に表向きだったノードなら操作回数が節約できる。■提出 #34798597 (TLE×18)。クエリのたびに子ノードのリストをたどる愚直解。■提出 #34799643 (AC / 422 ms)。子ノードは数だけ数えておいて一律に操作回数を計上し、子から親を調べることで足しすぎた分を引く。終了 12 分前に２完のノルマ達成。■■■B 問題と C 問題の配点が同じだから AC の２完遅解きは AB の２完遅解きと同じであり、２完遅解きは A の１完早解きに毛が生えたパフォーマンスしか出ない。-27。ARC にはレートを吸われてばかり。上昇したレートだけ数えたらもう赤なのではないか(頭がパー)。未来のレート上昇を演出するために現在のレートを捧げるのだ。