AtCoder ABC 159 復習メモ

A - The Number of Even Pairs

えっ、難しい…
天地開闢以来最も意味がわからないと話題に
(頭がA問題だったので…)
人類の希望、サンプルエスパーに全てを託します

というわけで入力例4に的を絞り
13, 3からなんとか81を捻り出せないか
5分ほど考えていたらなんかわかりました(適当すぎる)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  cout << (N + M) * (N + M - 1) / 2 - N * M << "\n";
}

ですがこの問題
・N個の偶数、M個の奇数からなる配列を生成して
・全ての組み合わせを試して和が偶数になるものをカウントしなさい
と言い換えると瞬殺できる方がかなり増えそうです

自分もサンプルエスパーなどしている間にこちらでやった方が1000％早かったと思います

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> V(N + M);
  for (int i = 0; i < M; i++) V.at(i)++;

  int cnt = 0;
  for (int i = 0; i < N + M; i++) {
    for (int j = 0; j < i; j++) {
      if ((V.at(i) + V.at(j)) % 2 == 0) cnt++;
    }
  }

  cout << cnt << "\n";
}

A問題はfor文が使えなくてもAC出来るようになっている(確か)とのことで
考え込んでしまいましたが固定観念に囚われず
さくっと楽な方向に切り替えられるようになりたいです

B - String Palindrome

サブストリング(a, b)の引数が
C++ だと index a から b文字分
Java だと index a から index b - 1 まで
という違いがあって混乱している今日この頃です

#include <bits/stdc++.h>
using namespace std;

bool pal(string s) {
  string t = s;
  reverse(t.begin(), t.end());
  return s == t;
}

int main() {
  string S;
  cin >> S;
  int N = S.size();
  cout << ((pal(S) && pal(S.substr(0, N / 2)) && pal(S.substr(N / 2 + 1))) ? "Yes" : "No") << "\n";
}

ところで最後の回文判定は要らないそうです
pal(S)がtrueなら後ろのsubstrは前のsubstrをリバースしたものなので
前者が回文なら後者も必ず回文だから、だそう。天才すぎる
これからも3回判定して生きていくと思います…

C - Maximum Volume

思い込みと直感で生きているのであまり悩みませんでした

#include <bits/stdc++.h>
using namespace std;

int main() {
  int L;
  cin >> L;
  cout << fixed << setprecision(6) << L / 3.0 * L / 3.0 * L / 3.0 << "\n";
}

今回はこれでも通りましたが何度も割り算すると誤差が大きくなってしまうので
L * L * L / 27.0 と書くべきでした。基礎がなってない

なるほどな～～(小学生)

D - Banned K

解けたときは天才かと思いましたが5000人近く通しているし
mapとか要らなかった。かなC

#include <bits/stdc++.h>
using namespace std;

long c2(long n) { return n * (n - 1) / 2; }

int main() {
  int N;
  cin >> N;
  vector<int> A(N), cnt(N + 1);
  for (int i = 0, a; cin >> a; i++) A.at(i) = a, cnt.at(a)++;

  long sum = 0;
  for (int i : cnt) sum += c2(i);

  for (int a : A)
    cout << sum - c2(cnt.at(a)) + c2(cnt.at(a) - 1) << "\n";
}

このコードで実行時間87ms
最後の "\n" を endl に変えると389ms
"\n" に戻して ios::sync_with_stdio(false); を唱えると39ms
差がすごい
これだと scanf + printf と速度差は無かった気がします

B問題もそうですが何度も同じ操作をするときは
ささっと関数にまとめてしまう習慣を身に付けたいと思いました
本番だと焦ってだらだら書いてしまう…

E - Dividing Chocolate

本当はこれをACしてから書きたかったのですが
出来ね～～時間ね～～となっています
数学問題は解けなくても仕方ないかなと思ってしまいますが
こういう問題は書けるようになりたいです。がんばります

さようなら～