競プロ日記 ABC159

はじめに

ABC159の参加記です.

https://atcoder.jp/contests/abc159

成績

https://atcoder.jp/users/kazki/history/share/abc159

はじめての4完でした！
しっかり前2日で精進したおかげです..

A

N個の偶数書かれたボールとM個の奇数の書かれたボールから2つ選んで書かれている数の和が偶数になる方法の数を答える問題.

和が偶数になる組み合わせは 偶+偶, 奇+奇 しかないので NとMそれぞれから2つ選ぶ組み合わせを足せばいい.

組み合わせのこうしきは nC2 のとき (1/2)n(n-1) で求めれるので以下の式ででます.

cout << N*(N-1)/2 + M*(M-1)/2 << endl;

ただ nCr ってA問題ででるんやなぁ。。(ちょっとびっくりした.

https://atcoder.jp/contests/abc159/submissions/11102854

B

強い回文の条件を満たすか判定する問題.

これ, 条件2と条件3が成り立つとき条件1は自明ですね..(わざわざ条件1も確認していた人

文字列の取り出しは substr メソッドを使って, 回文の判定は reverse 使えばいいですね.

ぼくは脳筋でやりました(一番実装だるかった

https://atcoder.jp/contests/abc159/submissions/11098074

C

今回のA問題です(

縦, 横, 高さの長さの合計が L になるような直方体の体積の最大値を求める問題.

結論から言うと 縦 = 横 = 高さ のとき体積が最大なので L/3 をして 体積を導出するだけです.

証明は相加相乗平均を使ったらできるみたいです.

https://atcoder.jp/contests/abc159/submissions/11105905

D

N個の整数が書かれたボールから k番目のボールを除き 書かれている整数が等しい異なる2つのボールを選ぶ組み合わせを答える.

Nの最大値が 2*10^5 なので O(N^2) だと TLE しますね..

先にk番目のボールを除かないときの組み合わせを計算O(N)し, 後から k番目のボールの組み合わせを引き, k-1個の中から選ぶ組み合わせを足せば導出できます.

A問題と同じく nC2 の公式で解けます.

いまだにint型でオーバーフローさせてWA出してるので直したいですね..

https://atcoder.jp/contests/abc159/submissions/11123314