リンク
全体的に
C問題で1ぺなが終わっている。B問題が滅茶苦茶難しくって、そこで動揺してしまったのかもしれない。
全身全霊をささげたE問題も実ることなく、撃沈。
解説ACのあとの学習の質が弱かったのか、自分の考察に自身を持てなかったことが恐らく今回の敗因。
A問題(灰)
mod処理だと、ループと中断を含む処理の特性から解法が分かった。
B問題(灰)
問題文を読み直したら、勘違いに気づいて解けた。
元々は、重複部分列をすべて洗い出す鬼畜問題かと思っていたけど、全然連続してていいらしい。簡単な仮説を立てる習慣がもっと身についてたら、逆に早々に読み間違いを自己誘導できたかも。
C問題(茶)
削除処理が後ろからしかあり得ないとのことなので、$)$が先に来てたら、そのあとに来るのは全部不適切だということで、そういったフラグで二重に管理する発想が芽生えて解けた。
フラグが立っているときに、$)$と$($のバランスを更新すべきでないんだけど、if文をクエリ2に書きそびれて1ぺな(終わってる... upsolveして原因を見つめ直す)
D問題(水)(X)
式に落とすことで段階的に考えよう！という方針だったけど、平方数を$CC$でmodしたときに$x$が手に入るというあさーい考察までしか及ばなかった。
脳死全探索を試みたけど、探索対象の取り得る最大値が$\sqrt{10^{17}}$ありそうで、やめた。
順位表ではE問題の方が解かれてたので、5分くらいかけてこれは見限る。
追記：解法を見た。その値以下の最大の平方数と平方数の数は等価である性質を利用することが鍵らしい。どうにも、僕は数字を数え上げる系統の問題の細分化が苦手で、こういった重要な性質に気づく前に、諦めてしまうらしい。共通の最大約数の数え上げに倍数を用いることが見つけられなかったのと同様に、主客転倒的な考えがまだ未熟である今こそ、段階的に考える能力を最大限に磨いていきたい。(今回であれば、どうやら対象の桁を1パターンに絞ることが発案のきっかけになりそう)
追追記：upsolveもとても難しかった。朝方なことを言い分けの材料にできないほど、実力不足を感じた...仮に考察の欠片を得たとしても、体調全快でも、絶対実装までは持ってこれない。
詰みポイント(時系列順に)
- 最大の平方数は正の平方数の数の総和と同じという発見
- fの返し値の変動範囲が桁ごとに扱えるという発想
- Cとxを分離することで安全な設計をするという冷静さ
- xの範囲を間違えることなく指定する数学力
- 間違えずに$d$の条件式を構築する集中力
- 探索範囲の複数条件を$\min$と$\max$で適切に取り扱う実装力
- 探索対象で$x$ではなく、しっかり$f(C,C+x)$を求める冷静さ
- オーバーフローしないよう桁ループの上限を設定して確信を得るメンタル
- 精密なSqrtを実装する必要があると気づく観察力
- 精密なSqrtの必要条件を列挙し実装できる根性
- どこでもバグらせない未来の自分への優しさ
正直類題でも攻略できる自信ない...遅くても、次のABCまでにはもう一度upsolveしたい。
E問題(緑)(X)
解けなくてつらい。単支点からの距離メモ比較だと、分岐の処理が難しそうなので、LCAを用いて、次数が$1$のすべての頂点に対して距離を足し合わせるという処理をした。見事TLE...
恐らく水色問題だから木の直径を使うんだろうという漠然とした気持ちはあったけど、作図もうまくいかないし、全然性質を把握してなかったから解法の根拠もないで、挫折。
気づけばコンテストは終了していました。
追記：本記事を書いている当時の僕は、経験していなければ解けないなどの舐めた発想をしていた。でも、背理法を用いたり、外部サイトに調べにいくなどして、根拠を見つける手段は幾らでもあったはずだ。絶対的にperfが必要なんだとの強い意志を持つために、まずは生活習慣から矯正したい。