ABC238

5完。青パフォでレーティング上がっても嬉しくないわ。

A - Exponential or Quadratic

Aでこれはかなり難しい。しかも、n=1,2,3を手で試した結果がヤバすぎる。nが小さいところを愚直でやるという発想がなかなか出てこなかった(nが大きいところは全部Yes)。

B - Pizza

これも簡単な典型ではあるが、Bとしてはかなりの考察難度。位置被りはないということなので、どれだけ回転させたときに切れ込みを入れたかをvectorに入れていく(角度はmod 360で管理する)。0度と360度も追加してソート。N+1個の差のうち一番大きいものを出力。これできれいに1周できている。

C - digitnum

これも重い。桁数毎に処理する。まず桁数を求める(std::to_string(N).size()とした)。まず、その桁数の正整数全部の和を求めるケースを書く。等差数列の和なので、最初の項と最後の項の平均かける項数。f(10冪)は1で、同じ桁数の間1ずつ増えていく。

D - AND and SUM

これは好き。ANDがaになるということは、aで立っているビットはxでもyでも立っている(確定)。ここにいくつかビットを足して和をsにできるかということ(aのが大きかったらできない)。aで立ってない場所はxy合わせて高々1個しか立っていないことから、よく考えるとs-a*2とaのANDが非0であれば不可能(もちろん0であればそのままxに足して可能)。

E - Range Sums

まず、整数列aの中身によって特定できたりできなかったりということがあるかどうかが気になるけどわからない(この問題文からすると、ないのだろうけど)。手で色々試していると、グラフが見える。BFSして0からNに到達できればよい(DFSでないのはダイクストラ的な見た目に引っ張られた)(UnionFindでないのは見えなかったから)。エスパー気味に通してしまったが、これが最終AC。

(解説を見て)なるほど累積和の差を教えてもらうと捉えるのか。

F - Two Exams

Gと交互に考えていた。

こっちを選ばずこっちを選んだらダメな順序付きペアを考える。最初OKな側を考えていたが、ダメがほうがよさそう。これでいくつかのDAGができる。扱いが難しそうだが、しばらく経ってトポロジカルソートを思いつく。それでも全く解ける気がしないので、DPではないかと気づく。トポロジカルソートしてあるとDPには都合がよさそうだ。しかし、何も見えず終了。各頂点の状況が異なるので(DPに必要な)「まとめる」ができない。

(追記)人を入れ替えて片方を 1 2 3 4 にするのは当然思いついていたが、一般のDAGへ逃げてしまった。トポロジカルソートするにも自由度があって、1回目の試験の順に並べることができてそれならDPできる。4乗になりそうで不安だったが、配るDPにすればシンプル(貰うDPにすると大量に貰う人がいたりして)。解説を見て解けそうだなと思ってから何時間もかかった。よくわかってないところに突っ込んでちゃんと考える勇気がない。

G - Cubic?

面白そう。素因数が大した数ないからできそうなんだけど、ほんとに色々な手段を思いつくんだけど、なんだか一つも攻撃が通らない。けっこう経ってから、素因数の個数はmod 3で持てばいいと気づく。ローリングハッシュみたいのも考えるが、3というのが厄介(複素数も考えた)。小さい素因数は愚直(?)にやるとして、大きいのをどうにかできないか考えていたが、できなかった。大きいものは個数も少ない(A_iに1000以上の素数が2個以上入っていることはない)のでなんとかなりそうに思えたのだが。

(追記)数列の中でk回目に現れた素因数pにhash[p][k%3]を割り当てる。hash[p][0]^hash[p][1]^hash[p][2]が0になるようにしておくという発想。思いつかなかった。