AtCoder ABC 155 復習メモ

AtCoder ABC

A - Poor

えっ、難しい…
if文で場合分けをしていけばよさそうですが
人類が場合分けをすると必ずミスすることが知られています
やりたくないな～と思っているとこれは前回のC問題とほぼ同じであることに気付きます

ninoi.hatenablog.jp

前回は配列をsort uniqueしてsizeが変わらなければYESでしたが
今回は配列をsort uniqueしてsizeが2ならYesです

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  vector<int> V = {A, B, C};
  sort(V.begin(), V.end());
  V.erase(unique(V.begin(), V.end()), V.end());

  cout << ((V.size() == 2) ? "Yes" : "No") << "\n";
}

sortやuniqueを毎回書くのは大変なのでスニペット登録しておくとよさそうです
前回同様setでいいのですが手癖でこちらでやってしまいます

B - Papers, Please

基本的にはans = "APPROVED"としておいて
条件を満たす整数があれば"DENIED"に書き換えればよさそうです

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

int main() {
  int N, A;
  cin >> N;
  string ans = "APPROVED";
  while (cin >> A)
    if (A % 2 == 0) if (A % 3 && A % 5) ans = "DENIED";
  cout << ans << "\n";
}

C - Poll

mapを使えますかの問題
APG4bに詳しく書いてありますので知らない人は読んでおくとよさそうです

atcoder.jp

にのいさんのコンテスト中の提出を見てみましょう

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

int main() {
  int N;
  cin >> N;
  map<string, int> MA;
  string S;
  int mx = 0;
  while (cin >> S) mx = max(mx, ++MA[S]);
  vector<string> V;
  for (auto ma : MA) if (ma.second == mx) V.push_back(ma.first);
  sort(V.begin(), V.end());
  for (auto v : V) cout << v << "\n";
}

なぜかmapのkeyをvectorに移してsortしています
mapが何なのか知らなかったようです…

余分なところを取り除くとこうなります

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

int main() {
  int N;
  cin >> N;
  map<string, int> MA;
  int mx = 0;
  string S;
  while (cin >> S) mx = max(mx, ++MA[S]);
  for (auto ma : MA) if (ma.second == mx) cout << ma.first << "\n"; 
}

mx = max(mx, ++MA[S]);
と書くとSのvelueをインクリメントしたあとmaxをとります
mx = max(mx, MA[S]++);
と書くとmaxをとったあとにインクリメントするのでWAになります
前置きと後置きの違いは大事そうです

mapやsetをまだまだ使いこなせていない気がするので鍛えていきたいですが
ABCの過去問ではそういう問題に出会うことが少ない気もします

D - Pairs

コンテスト中はひと目見て飛ばしてしまいました…

解法の概要は-1e18L-1から1e18L+1の間で二分探索
LとRどちらを動かすか決める集計をするためにまた二分探索
その二分探索、集計の仕方がA.at(i)の正負で切り替わる、といった感じ

二分探索と気付くのも難しいですし
仮に気付いてもビギナー絶対殺すポイントが5つ以上ある気がします…

必須の前提知識

qiita.com

その上で解説動画をみると
(毎回のことですが)とても詳しく解説されていてなんとか理解することができました

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

int main() {
  long N, K;
  cin >> N >> K;
  vector<long> A(N);
  for (auto &a : A) cin >> a;
  sort(A.begin(), A.end());

  long L = -2e18, R = 2e18;
  while (R - L > 1) {
    long M = (L + R) / 2, cnt = 0;
    for (int i = 0; i < N; i++) {
      if (A.at(i) >= 0) {
        int l = i, r = N;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (A.at(i) * A.at(m) < M) ? l = m : r = m;
        }
        cnt += l - i;
      } else {
        int l = i, r = N;
        while (r - l > 1) {
          int m = (l + r) / 2;
          (A.at(i) * A.at(m) < M) ? r = m : l = m;
        }
        cnt += N - r;
      }
    }
    (cnt < K) ? L = M : R = M;
  }
  cout << L << "\n";
}

当初Kをintで宣言していて無限にWAになっていました
int使うのをやめよう(制約を見よう)

動画で説明されている通り
long INF = 1e18+1;
と書くと、doubleの有効桁数が15桁程度のため+1が無視されてしまいます(情報落ち)
回避するには
long INF = 1e18L + 1;
のように足し算する前にlongにキャストするか
さらに余裕をもたせて2e18とする人も多いようです

解説動画では集計のための二分探索を毎回-1とNの間で行い
重複した部分を除く方向ですが
iとNの間で行うと重複しないので少しだけ楽になるようです(そうか？)

集計のための二分探索はlower_bound, upper_boundが使えますが
M / A.at(i) をlong doubleでキャストしないと誤差で死ぬ
正負だけでなく0も分けないとゼロ除算で死ぬ、等単純に楽とはならない感じです

ときにC++としては実行時間が長く(1195ms)どうすればとなっています

E - Payment

6以上の場合切り上げで後ろから貪欲すればいけそう、と思ったのですがサンプル3が合わず
これはやはり桁DP…できませんでした(涙)

…！？

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

int main() {
  string S;
  cin >> S;
  S += '0';
  int ans = 0;
  for (int i = 0; i + 1 < S.size(); i++) {
    int n = S.at(i) - '0';
    ans += min(n, 10 - n);
    if (n >= 6 || n == 5 && S.at(i + 1) >= '5') S.at(i + 1)++;
  }
  ans += S.back() - '0';
  cout << ans << "\n";
}

f:id:ninoi:20200218070702p:plain

…！！！？！？

1つ先をみるだけ＆なんなら前からでもOK。なんてこったい
そしてこれは諦めなければ気付けた可能性があります
証明？知らない熟語ですね…

二度とコンテスト中に諦めない(N回目)


うっ…(☍﹏⁰)