脳log[20221016]

2022年10月16日 (日) [AtCoder] 今日は ARC151 があった。終了３分前にノルマの２完達成。自分のすべての提出。１完も珍しくないのですごく嬉しい。開始９分１完(早解き)と終了３分前２完(遅解き)のパフォーマンス差がないに等しいとしても、とても嬉しい(昨日書いた通り>20221015)。■A 問題「Equal Hamming Distances」。ハミング距離って初めて知った(たぶん聞いたことはあるけど興味がない)。定義をよく読む。i 文字目の不一致を数えた数らしい。S,T から等ハミング距離にあって辞書順最小の文字列を作る問題。先頭から見ていって、S[i]/T[i] が一致しているなら 0/1 どちらを選んでも(ハミング距離が増えるにしても増えないにしても) S,T 双方からのハミング距離は変わらないので 0 を選ぶ。S[i]/T[i] が異なるときはどうするか。一方を選べば他方からのハミング距離(だけ)が増えるのでバランスを取らなければいけない。そこで不可能(-1)を出力するケースが理解できた。S,T の不一致が奇数文字のときはバランスが取れないので不可。偶数のとき、その半分の回数だけ S[i] を選び、同じく半分の回数だけ T[i] を選ぶと S,T 双方からのハミング距離が等しくなる。もちろんできるだけ S[i]/T[i] のうち 0 の方を選ぶ。■B 問題「A < AP」。解説のように対称性に気付けるわけがないので、先頭から見ていって見ている文字で初めて A<AP になるケースを数える方針で考えた。そのために４つの場合分けを長らく、１時間以上考えていた。４つというのは、A[i] と A[P[i]] のそれぞれが初出の場合と既出の場合(k<i として A[P[k]] としてすでに参照されているかどうか)。既出の要素というのは A[k]=A[P[k]] という拘束条件があって独立して M 通りの値を割り当てられるわけではないので、それをまず知る必要があると思ったのだ。A[i] と A[P[i]] がどちらも未出の場合は簡単で M*(M-1)/2 通りの割り当てパターンがあり、その他の未出の要素それぞれにも M 通りの割り当てがある。しかし既出の要素の扱いに困った。値が連動する既出の要素は……。まず、既出の要素であってもほぼ自由に M 通りの値を割り当てられるということがわからなかった。k<i となる k において A[k]=A[P[k]] という拘束条件があり、A[P[k]] = A[i] であることも A[P[k]] = A[P[i]] であることもあるけど、A[i] と A[P[i]] に関わらない限り連動するその値は M 通りから好きに選べるとわかっていなかった。なにか拘束条件が連鎖して階段状の大小関係があると思っていた。既出の要素でもほぼ未出の要素と同じように M 通りから選べるとわかったときに答えの計算方法がわかり、既出要素のグループを見出して UnionFind を持ち出すところまで時間はかからなかった。B 問題は難しい問題なのではなくて、隅々まで理解するのに時間がかかる読み手に問題があった。まあ、そこが難しさなんだけど。