| A | B | C | D | |||
| 問題文 | ■ | ■ | ■ | ■ | ||
| 自分の提出 | ■ | ■ | ■ | ■ | ||
| 結果 | AC | AC | AC | AC |
全体感想
初参加！23分で全問正解。
問題Dから考え始めたのですが、かなり簡単でやや拍子抜け。問題Cが少し難しかったです。
それなりにミスなく乗り切れたと思ったのですが、3桁順位。やり込み層は本当に速いですね。
問題C – GCD on Blackboard
1元を除いて $\gcd$ を計算する問題。当然、個別の計算でループ回すと$O(N^2)$でダメです。事前計算を使って、個々の$\gcd$の計算を軽くすることを考えます。
初めはsegment木を考えました。区間内の $\gcd$ を計算していきたいので、自然な解法だと思います。この時点で「解けた」という気持ちにはなりました。segment木を迷わず実装する自信はないので、ノートに実例を書き出しながら、一旦他の問題に移りました。
問題Dが物凄く簡単だったことも合わせて、「本当にそんな難しいことさせるのかなぁ？」と思い、もう少し考えます。よく考えると、$[0,x)$や$(x,N-1]$の形の区間しか計算する必要がありません。そのような区間に対する事前計算の方法を考えると、左右からの累積$\gcd$を計算しておくだけで良かったです。
（後日考えたこと）
「左右からの累積」という発想は、
集合$S$があり、各$s\in S$ごとに部分集合$S\setminus\{s\}$を考察する必要がある場合
に使える場合がある、と一般化しておくと良さそう？他に過去問で一度同じ発想を経験しました。
問題D – Flipping Signs
やたらと簡単です。操作に回数の制限も特にないので、たいていのものを正に変更できます。
唯一、全ての要素の積が定符号という条件があるだけです。
Dは、「考察が必要」「考察すれば易しい」ような問題が多めなのか、あるいは今回だけなのか。
$0$は存在する場合などで正しく実装出来ているかを慎重に確認しながら提出。
