コンテスト後のツイート
E 下にいくのをx回した後、斜め移動して折り返す。累積和で。 F 個数が奇数の素数を管理し、積がA_iの奇数の素因数の積と一致する個数を足す。積が大きい場合で悩んでmodを取ったらWA。10^6を超えたら打ち切るようにしてAC。 G 最小全域木を取る。あとはdが大きい方から削る。xが大きい方から尺取り。
— titia (@titia_til) October 7, 2026
H. A Problem to Warm Up the Eyebrows
解説AC。
解説も自力では解読できず、ChatGPTに説明してもらってACした。
解説は式変形で解こうとしているが、式変形から導出するのは難しい。
主客転倒で解けないか？ と疑わなくてはダメ。
A[i][j]*A[x][y]が何個寄与するか？ と考えると、そのbounding boxの上下左右に何個行や列があるか？ を見れば答えが求まることが見えてくる。
そう思えば、具体例を考えるとどれくらい寄与するかが見える。
難しいが、主客転倒というアイディアさえ思え付けば無理な問題ではなかった。
0 件のコメント:
コメントを投稿