think-cell Round 1

　D1まで。D2もEも分からず、またレートを下げる。

コンテストへのリンク

コンテスト後のツイート

think-cell Round 1 D2もEも分からなかった。
A ソート。
B 大小交互におく。
C A[i]+iで大きい順にソート。xが二つ以上あるならx-1にする。
D f(S)の求め方は、1がきたとき、1、010、001100、……のいずれかを置くというDPで解ける。このDPをまとめようとしたが分からず。

— titia (@titia_til) February 17, 2024

D2. Sum over all Substrings (Hard Version)

　解法ツイートを見てAC。

　大事なことを見逃していた。「1、010、001100、……のいずれかを置く」と考えていたが、置くのは基本的に「010」だけで良かった。

　これに気付かなくてもD1がACできてしまうから、DPの遷移について考えなかったなぁ。

　そう気付けると、D2のDPは自然に書けた……のだが、思いつくまで結構時間がかかった。時間がかかった原因は「配るDP」が頭にあったせいかなぁ。「もらうDP」で書こうとすると簡単に書けた。

E. 2..3...4.... Wonderful! Wonderful!

　解説AC。

・出来上がりったsequenceがgoodになる条件を見つける

・goodでないsequenceの数える

　の二つができなくてはいけなかったが、どちらもできていなかった。

　できなかった一因は、実験して数を数え、oeisなどでどうにかしようとしてしまったことか。二項係数の和みたいになることは分かったが、そこから考察が進まなかった。

　実験すること自体は間違っていないので、そこから情報を得ようとするところに問題があった。自分には、実験した後、頭を使わずどうにかしようとしてしまう傾向がありそう。実験の結果を眺めて、なんで二項係数の和になるんだろう？　という方向で考えなくてはいけない。（そういう風にしたら思いついていたかはまた別の話だが）