Article Outline
はじめに
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問題ででるんやなぁ。。(ちょっとびっくりした.
B
強い回文の条件を満たすか判定する問題.
これ, 条件2と条件3が成り立つとき条件1は自明ですね..(わざわざ条件1も確認していた人
文字列の取り出しは substr メソッドを使って, 回文の判定は reverse 使えばいいですね.
ぼくは脳筋でやりました(一番実装だるかった
C
今回のA問題です(
縦, 横, 高さの長さの合計が L になるような直方体の体積の最大値を求める問題.
結論から言うと 縦 = 横 = 高さ のとき体積が最大なので L/3 をして 体積を導出するだけです.
証明は相加相乗平均を使ったらできるみたいです.
D
N個の整数が書かれたボールから k番目のボールを除き 書かれている整数が等しい異なる2つのボールを選ぶ組み合わせを答える.
Nの最大値が 2*10^5 なので O(N^2) だと TLE しますね..
先にk番目のボールを除かないときの組み合わせを計算O(N)し, 後から k番目のボールの組み合わせを引き, k-1個の中から選ぶ組み合わせを足せば導出できます.
A問題と同じく nC2 の公式で解けます.
いまだにint型でオーバーフローさせてWA出してるので直したいですね..
