Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 124

ようやく、全完。

REとかWAとかあるけど(とりあえず)気にしない。

f:id:mdstoy:20190413223154p:plain

各問題

A - Buttons

これは考えている暇があったら全通り並べたほうが速いと思って(3通りですしね)、前回の公式解説YouTubeで覚えたmax({a, b, c})を早速使いました。

つまりmax({A+A-1, A+B, B+B-1})を出力ですね。

B - Great Ocean View

これはforとifを組み合わせて使えれば解ける、いかにもABCのB問題、って感じのやつですね。

常に全部比較する必要はなくて、手前にある山で最も高い山との比較さえすればよいというところが肝要。

C - Coloring Colorfully

これは塗り替えた後の状態は偶数番号白/奇数番号黒か偶数番号黒/奇数番号白の二通りなので、両方にかかる手数をそれぞれ計算して、少ないほうが答えです。

こういう解法が浮かんでくるあたり、だいぶ競プロに慣れてきてるのかなぁと思ったり思わかなったり。

私の回答 : https://atcoder.jp/contests/abc124/submissions/4944713

実装中にも、もうちょっと効率よくできると思ってはいましたが、うっかりREとか出さないように紛れのない実装にした、つもりです。

D - Handstand

最終的に通しましたが、1REと2WAはだめですね。

実装の方針は

010011100

こういうのを、状態ごとにカウントした配列に落として

1, 1, 2, 3, 2

k の数に応じて和を取って、最も大きいものを答えとする、というもの。 たとえば上記の例でK=1なら

2, 6, 5

なので答えは6、 K=2なら

7, 8

なので答えは8、という具合。

カウントした配列の偶奇、最初が0なのか1なのか、あとKの数と0の区間の大小関係で細かい場合分けが必要な実装になってしまったのですが(そのへんのコーナーケースの不備がRAやWAの理由)、もっと効率のいい実装があるんでしょうね、きっと。(←まだ公式解説配信前)

追記

公式解説によると、0 or 1の切り替わる位置を記憶すればよいとのこと、たしかにそれだと無駄に和を取る必要がないですね。

あとは二分探索やしゃくとり法でも解けるとのこと。しゃくとり法は、確かに言われてみればそりゃそうだなー。

まとめ

しゃくとり法は、まだトレーニングしていないのでやらねば・・・。

なにはともあれ初の全完は嬉しいですね。方針がわりとすぐ浮かぶようになってきているのは大きいと感じます。

f:id:mdstoy:20190413230219p:plain

次回予告、「緑になるまでにしたこと」乞うご期待。(うそ)