6完。競プロは面白いと思っていたけど、問題の面白さに関係なく負けるとつまらないクソゲーだった。ぷよぷよみたいだな。
A - Weird Function
「f(f(f(t)+t)+f(f(t)))」を問題文からコピペ。
B - Longest Segment
std::hypotを使う。
C - Happy New Year!
2進法みたくなるっぽい。下位からやってreverse。
D - Prefix K-th Max
priority_queueかmultisetを2個使うやつが思い浮かぶ。それで解けるはずではある。出力回数がN-Kより1回多いのも難しかった。考え続けると、そこまでの上位K個の集合を持ってその中の最小を出力すればいい。priority_queueが1個あればいい。pushしてpopするのを繰り返すだけ。相当頭が混乱した。これは瞬殺できない。
E - Arithmetic Number
難しそうに見えるが、冷静になると「等差数」は初項と公差と長さだけで決まるので全列挙できる。列挙するときは、初項と公差を決めて長さ1から伸ばしていく。桁が負や10以上になったら終わり、X以上の数を追加したら終わり。最後はlower_boundを使うと楽。
F - Reordering
各文字がいくつあるかだけが重要。その中から各文字をいくつずつ使うか決めると、例えば5個と6個と3個だとすると(5+6+3)!/(5!*6!*3!)通りになる。こういうのの和を求めたいが、全くわからない。しばらくすると、分子がいい性質を持っていることに気づく。合計何個選んだかが同じなら、1/(5!*6!*3!)みたいのを和でまとめることができる。この形の和は見えにくい。「合計何個選んだか」は最終的に、できた文字列の長さになる。各長さについて階乗ぶんを掛けて足していくと答え。この方針は難しかった。提出したときもよくわかってなかった。
G - Divide a Sequence
1個ずつ足していく方法で2乗にはなる。しかしこれの高速化は無理そう。分割統治みたいにやろうとしても、結局これより速くなる要素がない。となると最大最小を利用することだが、最大値でぶった切っても最小値がどこにあるかわからんし、各区間の寄与を考えるにも結局端の情報が必要になる。
