perarduaadastra

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

AtCoder Regular Contest 129 反省

nosubしてないだと

 

結果を鑑みて

1200(1) 91:59

330位。微冷えして青に叩き落とされた。

あと20分あればD通せたかも、と思うが他の問題に割いた時間や明らかな嘘解法に費やした時間が自分を苦しめただけなんだよね......。

 

A - Smaller XOR

パッと見桁dpに見える300点。1≦x≦Kとして、K=L, K=Rのときの結果があればOKだと思った。

桁dpは嫌だなあ、ここでつまづくとそこから先もえらい目にあいそう......

などと思っていたが、順位表を見て4, 5分で通している人がいたので、桁dpの線を捨てた。

そういえばARCの300か400くらいの問題で桁dpっぽいけど実はふつうに数え上げられるというようなのがあった気がしたのでぐっと睨むとxの1番上のbitが固定してみたときに良い感じにできる計算式を思いつく。

 

もともとBまで潜伏のつもりだったので出さずにBへ。

 

B - Range Point Distance

あんまり記憶がない。こういうのは区間の端点だけ見れば良いと直観した。

maxをとるような直線は端っこのほうから生えているはずだから、よく考えると直線は2本あればいい。

あとは数合わせをして提出。

 

このときはそんなに順位悪くなかった気がする。(300くらい?)パフォはカスだった。

 

C - Multiple of 7

142142...みたいにできるのかと思った。違った。

三角数で貪欲に構築していって、77777177717みたいに1で仕切ったら良い感じになったので出して1ペナ。

そこから迷走しまくって悩みに悩んだ末、順位表みて爆速で通している人を見て、ad-hocな方法でなくても構築できるのでは、と思った。

区間を値の7で割った余りごとに仕分けて貪欲にNを減らしていく形で構築していった。Nがでかすぎるとどの数字を置いてもうまくいかなくなる場合がありそうで不安だったが、1000くらいまで試してもうまくいっているので出したら通った。

 

後で知ったが、三角数定理を覚えていれば楽勝の問題なのだった。(あるいは、三角数定理があればこのアルゴリズムに正当性を与えられた。)

この時点で青落ちのパフォーマンスだった。ひえ〜

 

D - -1+2-1 

どこぞで見かけた、累積和で持つと良い感じのやつだと直観したが、円環なのでどうなるんだ?と思ってheapを使った貪欲に走ってしまった。

残り10分くらいになって冷静になり、見れば見るほど累積和でうまくいきそうなことに気付いた。index 0やN-1への操作が特殊で、ここの理解が中途半端なままコンテストが終わってしまった。

あとでちゃんとそのままの解法でがんばったら解けた。勘を信じよう。

 

総括

Eで燃やす埋めるみを感じたがAC数を見て諦めたのはやや偉いムーブだった。A、C、Dでの解法ガチャの失敗が良くなかった(Dについてはガチャは当たってたのに捨ててしまった)

Cはなんとなく1+2+3+...+nの組み合わせで整数を表す方法というのが一般的な話題のような気がしたのにググらなかったのは悪手だった。

 

なんとか微冷えで済んだが、ARCでまともに戦えるようになるにはもう少し冷静な立ち回りが必要だなと思った。あとは天才的な頭脳とかがあればもっといい。