perarduaadastra

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

AtCoder Regular Contest 116 反省

4完、遅解き...... とはいえ微減少なのでARCとしてうまく立ち回れたほう。

 

結果を鑑みて

1700(1) 80:27

全体491位、レート-6となった。Dで時間かけ過ぎたとは思うが、その割に減少は優しかった。

 

A - Odd vs Even

最初は何もわからなかったが、偶奇性はあるなと思って、{2, 2以外の偶数, 奇数}で場合分けした。この時点でサンプルは通るが、さすがに4や6で試してみると答えが異なっており、そこからなんとか解法を思いつくことができた。

4分半かかって、まあそこそこだろうと思ったら600位くらいだった。びっくりした......

 

B - Products of Min-Max

最初は主客転倒オーラがすごいのでその方針で少し考えた。さすがにminとmaxではうまくいかないから、とりあえずソートすると、区間についてごにょごにょする問題に見えてきた。

あとはいい感じに値を累積しながらmaxかminの値を固定して計算すればいいことに気付いたが、添字ガチャでごちゃごちゃになってしまい、結局11分かかった。

 

順位表を見て、まあARCだしそうだよねという気持ちになった。ここまでのムーブのせいで焦りが生まれてしまったかどうかはあまり覚えていないが、そこまで精神は乱れていなかったと思う。

ちなみに、ここでmodの取り忘れでペナをつけた。

 

C - Multiple Sequences

読んですぐ、Mまでの全探索となんかの約数列挙が思い浮かんだ。sieveは整備済みなのでこれを引っ張り出して取りかかった。

解き進めていくと、1~Mの整数の素因数をN個の箱に突っ込んでいってその際の場合の数を数える問題になった。 ここの数式ガチャで手こずり、とんでもないコードを書いてしまった。

16分かかった。

 

思えば、この時点で何だか脳死コードを書いているし集中力が破滅しかけていた。部屋が少し暑かったせいだと思う。春の訪れだろうか。

 

D - I Wanna Win The Game

序盤〜中盤はなんだか意識が朦朧としていて、何を考えていたのかまるで覚えていない。20~30分ほどを何だかよくわからない解法に費やして破滅しかけていた。ここで順位表は見ないぞと(精神安定のために)決め込んだのは悪くなかったと思う。

考え方を変え、解法ガチャに再度戻ってくると実に素朴なO(M^2logM)のdpが生えた。いやいや、pypyでこんなの通るわけないだろと思いつつコードテストに放り込むと存外高速で、なんとか通すことができた。

 

解法ガチャを最初にやるときは紙に解法を書き出しておいていつでも参照できるようにしておくべきかもしれない。

 

E - Spread of Information

パッと見では木の中心からのdpと二分探索に見えた。これのおかげで意識がはっきりし、以後の考察はいい感じに進めることができた。解けてないけど。

木の中心に情報伝達すると、まず最初のサンプルで落ちる。代わりに、葉からなるべく直接情報伝達する点が少なくなるように配置する方法を思いついた。葉から見るとそれが最適な配置になる上に無駄がないように見えたが、このdpの結果直接伝達する点が0個になってしまう場合や多すぎる場合などに対処する方法が思いつかず、そのままタイムアップとなった。

 

総括

だんだん気温もあったかくなってきたので、体温調節をしっかりするように気をつけよう。解法ガチャは時間かかりそうな問題(ARCやAGCなら400点~)ならば紙に書くなどしよう。

 

なんだか終わってみるとどっと疲れた回だった。今これを書くのも結構しんどい。Dで自分が今書いているコードの意味がわかっていないような状態が中盤続いてひどかった。体温の問題なのだとしたら、次回以降対策できると思うのでしっかりやっていきたい。