kumamotone’s blog

iOS/Android アプリエンジニアです　https://twitter.com/kumamo_tone

AtCoder Beginner Contest 159 (ABC159) A,B,C 解説

atcoder.jp

自分は出なかったのだが、全体的に数学っぽい問題だったっぽい。実際（実際って何？）、AからCまでfor文ひとつ書かずに解くことができる。

自分はコンピュータサイエンスで修士取ったくせに数学苦手意識がすごく強いので、Twitterの感想見てて自分が参加してたらつらそうだったな〜と思った。

ついでに見たPDF版の解説が分かりにくかったのだが（すいません、個人の感想です）解説動画の内容がわかりやすいと思ったので、補足しつつ書き残しておく。

PDF: https://img.atcoder.jp/abc159/editorial.pdf

www.youtube.com

A - The Number of Even Pairs

問題概要

偶数が書いてあるN個のボールと奇数が書いてあるM 個のボールがある。ここから2つ選んで、書かれた数の和が偶数になるパターンの数を求めよ。

答え

偶数が書いてあるボールのグループ、奇数が書いてあるボールのグループから、それぞれ1個ずつ取る場合は絶対に奇数になる。

逆に、同じグループから選ぶ場合は絶対に偶数になる。

なぜなら、偶数、奇数の性質上、

  • 奇数＋奇数＝偶数 // いいね‥

  • 偶数＋偶数＝偶数 // いいね‥

  • 奇数＋偶数＝奇数 // ダメです

となるので。

そのため答えは

N個のボールから2個選ぶ= {} _NC_2 = \dfrac {N(N-1)}{2} パターン

M個のボールから2個選ぶ= {} _MC_2 = \dfrac {M(M-1)}{2} パターン

を足したものになる。

ちなみに {} _nC_r ってなんだっけとなったときは、ググると

{} _nC_r = \dfrac {n!}{(n-r)!r!}

ということがわかり、今回 r=2 なので

= \dfrac {n!}{(n-2)!2!}

= \dfrac {n(n-1)(n-2)(n-3)...}{2(n-2)(n-3)...}

= \dfrac {n(n-1)}{2}

となる。

int main() {    
    int N, M;
    cin >> N >> M;
    int ans = N*(N-1)/2 + M*(M-1)/2 ;
    
    cout << ans << endl;
    return 0;
}

書きながら N*(N-1)/2 の結果って常に整数になるの？って一瞬思うが、これも偶数と奇数の性質上、

  • Nが奇数だったらN-1は偶数
  • Nが偶数だったらN-1は奇数
  • 奇数×偶数は常に偶数

のため、絶対 N(N-1) は偶数となり、2で割っても大丈夫。

B - String Palindrome

atcoder.jp

問題概要

akasaka のような、回文な上に、中心の文字の左右の文字列も回文になっている文字列かどうか判定せよ。

答え

問題文が厳密な書き方をしているので一見”"強い""回文って何？って思うが、上記の概要みたいなことを言ってるというのに気付ければ、そのまま実装すれば良いとなる。

まず回文かどうかは、以下の関数で求められる。

bool isPalindrome(string s) {
  string t = s;
  reverse(t.begin(), t.end()); // t をひっくり返したやつが
  return s == t; // 同じだったら同じ
}

文字列をひっくり返す方法は最近の大体の言語で関数化されてるはずなのでC++以外の場合はそういうのを使うとよさそう。

あとは、全体を回文かどうか判定したあとに、真ん中の文字から左の文字が回文になっているかどうかだけ判定すれば実は右側の文字は判定しなくて良くて、以下のようになる。

int main() {
    string s;
    cin >> s;
    bool ans = true;
    if (!isPalindrome(s)) {
        ans = false;
    }
    string leftSub = s.substr(0, s.size()/2);
    if (!isPalindrome(leftSub)) {
        ans = false;
    }
    
    cout << (ans ? "Yes" : "No") << endl;
    return 0;
}

C - Maximum Volume

問題概要

縦、横、高さの長さの合計が L の直方体としてありうる体積の最大値を出力せよ。

答え

直感的に（は？）、縦、横、高さが同じの場合に体積が一番でかそうだと気づいた場合、縦、横、高さがLの1/3のときの体積を求めればいいじゃんとなる。

なので、シンプルに

(L/3)3

を計算すれば良い。

int main() {
    double l;
    cin >> l;
    double ans = pow(l/3,3);
    cout << fixed << setprecision(12) << ans << endl;
    return 0;
}

なんだその直感は

これだけで問題は解けるが、マジでそれで大丈夫か？となる。

これは相加相乗平均不等式というやつで証明できるっぽいが、もっと直感的に（？）確かめる方法がある。

まず、縦、横、長さが同じときの体積を a×a×a …(1)とする。

その状態から、ほんのちょっと ε だけ長さを変えたときの体積は、 a(a + ε)(a - ε) …(2) になる。

このとき、 (1) と (2) を比較すると、

a×a×a と a(a + ε)(a - ε)

a×a と (a+ε)(a-ε)

a2 と a2 - ε2 // 左のほうが絶対デカいね

となり、ε>0 （ほんのちょっとって言ってるのに0だったらズルじゃん？）から、 (2) は (1) より ε2 ぶん小さいので (1) のほうが確実にデカい、となる。

なので 、縦、横、長さが同じときの体積が一番デカい。よかったですね。

感想

ここまででもむずいなあとなり筆をおいてしまったのだけどCまで8,201人中7,134人解けてるので、たぶん標準的な参加者的にはそうでもないんだろうな…と思うとぐんにょりしてしまった