perarduaadastra

競技プログラミングとかをしています

AtCoder Regular Contest 114 反省

A, Bが明らかにABCのものより難しいのはさておいて、Cを通せなかったのでただの速解き2完になった。

 

結果を鑑みて

700 25:31

全体547位、レート-16となった。ARCで2完などをやるとだいたい-30くらいは覚悟しなければならないことが多いが、今回はちょっと優しめの減少だった。

 

A - Not coprime

パッと見でGCD、LCM系の問題に見えたのでLCMをとってみたが普通にサンプルが合わないのでよく見ると昨日見た問題に酷似していた。

恐る恐る提出するとAC 7分弱かかった。

この時点では200位ちょっとくらいだったと思うので、そこまで焦らずに済んだ。

 

B - Special Subsets

パッと見で特に思いつくものはなかった。

少し考えると、f(a)=b, f(b)=c, f(c)=aみたいに有向閉路になる部分はひとつにまとまることに気付くので、SCCを持ってきた。

そこから、強連結成分分解した有向グラフ上のパスを数える問題だ と解釈したわけだが、これは正しくなかった。入次数をうまく管理しなければならなかったりして複雑な実装になる予感がした。

そんなこんなでここで時間を使ってしまったが、有向閉路の考察に立ち返って、有向閉路の集合になることがTの必要十分条件であることを疑った。この考えは正しかった。正当性を厳密に考えることはできなかったが、辺の本数がN本であることがうまく効いてくれていることを信じて提出するとACした。この問題にはなんと20分近くかけている。たまげた......

 

順位は微妙になったがCが解けそうな見た目をしていたので取り掛かることにした。

 

C - Sequence Scores

 パッと見で最適な操作はわかった。この段階では種類数がそのまま答えになると思っていた。その線で実装すると値が合わないので、ノートで実際に実験して次の性質を洗い出した。

・種類数がそのままコストにプラスされる

・A[i + 1] > A[i]であるとき、コストに+1

 

1番目の性質は良いのだが、小さなサンプルばかり考えていたせいで2番目の性質を俯瞰して検証することができなかった。主客転倒でdpを組むと最後のサンプル以外はすべて合っており、ここから1時間ほど考えていたがついに2番目の性質を拡大することはできなかった。

毎回そうだが最後の1,2分は正常に考えるのが難しい。時間がなくなるほど俯瞰してみるのが困難になる。

 

値・要素数の比較的大きなケースを考えること。愚直実験コードを作ること。などが反省として得られた。

 

総括

愚直実験コードや大ケースでの実験は問題の考察を進めるうちの早い段階で作っておかないと精神力が足りなくなり、また、「今更作っている余裕があるのか」という逡巡が入ってしまうためミスに繋がりやすいかもしれない。

ただ、問題にどのくらいの時間を割くことになるのか推定するのは難しいので(Cはパッと見た感じうまくいけば30分以内に終わるだろうと踏んでいた)比較的難しい問題に対しての時間感覚を身につけることが必要になってきそう。