2/21

ARC113

A
まず、誤読があった。ABC ≦ KのところをABC = Kと勘違いしていた。
Cを固定してAB = K / CとなるABの組を探す。これは約数列挙で固定したC一個についてsqrt(C)なので全体でO(KlogK)、問題がこの通りであればまあ悪くはない回答だった

正しい問題に戻って、固定したCに対してAB≦Cを求める必要がある。これに大分時間がかかった。計算量sqrt(C)で止めたいため、for文を回しながらA < B(ただしB = C/A)で打ち切らなければならないだろうなとは思った。ただし、ans += B * 2 などとすると重複して数えてしまう組が出るのでかなり詰まった。最終的には双曲線の内側にある格子点を数えることをイメージして切り抜けた。

D
解ける人はすぐ解けそうな問題に見えたのに詰まって苦しかった(実際水色パフォらしい)
こういう数え上げはなんとなくで考察してしまって、実は重複していたり見逃しているパターンが本当に多い。(単純に手で実験している間に見逃していることもあるし、sumなどを使って式をまとめるときにあるパターンが2回数えられていたりする 具体例を簡潔に言うのが難しいが、列視点と行視点で2回カウントされているようなイメージ)

こうなってしまうとサンプルが合うまで式を微妙に変え続けるみたいな沼にハマり、厳しい。せめて実装する前にサンプルでシミュレーションをした方がいいなと思った(今回はサンプルの説明が親切でかなり助かった)

今回、どうせ行と列独立に数えて掛け合わせだろうと思ったが危ないかもしれないので気を付けたい

余談だけどコンテスト中にWolfram Alphaの力を借りるという経験ができて良かった

↑に対してアドバイスをもらった