Toy と帽子と ADP BE

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

AtCoder Beginner Contest 159

5完5WA。ラスト1分を切って、バグが取りきれてない実装を祈りながら投げたら、通ってました。(おい

各問題

A - The Number of Even Pairs

問題の解読が一番の難関。

冷静に見てみると、偶数同士を選んだ場合か奇数同士を選んだ場合に和が偶数になることがわかります。

なので、偶数N個の中から2つ選ぶ組み合わせの数と、奇数M個の中から2つ選ぶ組み合わせの数を足したものが答えです。

Aにしては算数パートが難しくないですか?

B - String Palindrome

制約が小さいので、Sそのものと、最初から(N-1)/2文字目までの文字列と、(N+3)/2文字目から最後までの文字列について、愚直に回文かどうかをループを回してチェックすればよいです。

C - Maximum Volume

Lを3等分して掛けるのが一番体積が大きくなるので*1、Lを3で割ったものを3乗すればよろし。整数じゃなくて実数(double)で計算することにだけ注意。

D - Banned K

あらかじめどの数がいくつ出現したかと、ボールを除かなかったときの場合の数を求めておきます。

あとはi毎に、どの数字が1減ったかと、減った数字の分だけ場合の数を調整すればよいです。

例えば1がA全体で4つ含まれていてA_1が1なら、全体の場合の数から6*2を引いて3*3を足す要領です。

私は場合の数の計算でバグを仕込んで2WAしました・・・。耄碌してるなー。

E - Dividing Chocolate

Hの制約がくそ怪しくて、bit全探索であることがわかります。(おい

あらかじめ二次元累積和で、区切りの位置に対するホワイトチョコレートの数をすぐ取り出せるようにしておいてから、Hつまり横方向の区切りをbit全探索、縦方向は累積和を見ながら貪欲に区切ります。

全探索した中で、最も少ない区切りの数が最終的な答えなのですが、区切れてない時(縦1区画分に区切ってもKを超えてしまう場合)にちゃんと弾くことには注意です。(私はそこで無限にバグらせて3WAしました。そして通ったけど実はバグが取り切れていないという・・・)

F - Knapsack for All Segments

チラ見しただけ。

まとめ

Eは本当に手元でバグが取り切れていないことがわかっていたのですが、残り1分を切ったのでエイヤで投げると、なんと通りました。

コンテストはね、通したら勝ちなんですよ!!(ごめんなさいごめんなさい

拾った形ではありますが、久々にABC5完でレート回復させたので、とりあえずはよしとします。

f:id:mdstoy:20200322230315p:plain

*1:証明は?

*2:4つから2つ選ぶ場合の数

*3:3つから2つ選ぶ場合の数