AtCoder ABC 154 復習メモ

AtCoder ABC

A - Remaining Balls

えっ、難しい…
入力を書きながら考えて流れで出力。コードが汚い。書き直したもの

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S, T, U;
  int A, B;
  cin >> S >> T >> A >> B >> U;

  (S == U) ? A-- : B--;

  cout << A << " " << B << "\n";
}

S==UならAを1減らして違うならS==TなのでBを1減らします
三項演算子を使っています。(条件式) ? 真式 : 偽式;
条件式が真なら真式が、偽なら偽式が実行されます
難しいですが入出力が出来れば100分でなんとかいけると思うので良いのかなと思います

B - I miss you...

こちらは逆にBとしてはやさしめ？提出したもの

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

int main() {
  string S;
  cin >> S;

  for (int i = 0; i < S.size(); i++) cout << 'x';
  cout << "\n";
}

Sの文字列の長さ(S.size())だけループを回して'x'を出力します
最後の改行要るっけ？いや要らないよな…
でも不安になって書いてしまう。そろそろやめたい

また範囲for文でシンプルに書くこともできます

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;

  for (char c : S) cout << 'x';
}

stringの全てのcharを1つずつ順番に取り出してcにセットします
その都度(cは放置して)'x'を出力します
灰色の頃は範囲for文、何に使うんだろうと思いましたが最近はちょくちょく使います
ここで使う必要無いですが少しずつ使い方に慣れていくと良い気がします

C - Distinct or Not

同じような問題が過去、文字列で出題された気がします
整数列でもやることは同じです

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  // 4 1 3 1 6 2   ※入力例2を使用

  sort(A.begin(), A.end());
  // 1 1 2 3 4 6
  auto i = unique(A.begin(), A.end());
  // 1 2 3 4 6 6
  A.erase(i, A.end());
  // 1 2 3 4 6

  cout << ((A.size() == N) ? "YES" : "NO") << "\n";
}

1. sortで小さい順に並べ替えます
2. uniqueで重複してるもの(この場合1)を除きます
除かれがあった場合末尾にゴミが発生しますが何番目からはゴミだよ、ということを
教えてくれるのでそれを変数iで受け取っておきます
3. iからendまでを削除(erase)します

その結果A.size()とNが一致していれば重複はなかったということで"YES"
一致しなければ重複があったということで"NO"になります

iで受け取るのはイテレータと呼ばれるものです
sort関数の引数にあるbeginやendもイテレータです
イテレータを理解すると関数を更に便利に使えたりするので
APG4bなどで少しずつ勉強していくと良いと思います
自分は理解していません

ひとまずsortしたあと
A.erase(unique(A.begin(), A.end()), A.end());を唱えれば
ユニークな文字列や整数列を得られることを覚えておけば良いと思います

またsetを使うととてもシンプルに書けます

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

int main() {
  int N, A;
  cin >> N;
  set<int> S;
  while (cin >> A) S.insert(A);

  cout << ((S.size() == N) ? "YES" : "NO") << "\n";
}

どうでもいいですがwhile (cin >> A)と書くと
cinするものがある限りcinしつつループを回してくれます

入力したものを片っ端からsetに放り込んでいくのですが
既にその数字がsetに存在していたらスルーされます

そのためS.size()とNが違ったら重複する要素があったということになります

D - Dice in Line

期待値はネトゲで学びました
入力に1を足して累積和にしてK個隣接する区間の両端の差のmaxを探して2で割ります。長い
比較的スムーズに提出できたのですが3ケース落としてしまいました…

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<long> P(N);
  for (long i = 0, sum = 0, p; cin >> p; i++)
    P.at(i) = sum += ++p;

  long ma = 0;
  for (int i = 0; i + K < N; i++)
    ma = max(ma, P.at(i + K) - P.at(i));

  cout << fixed << setprecision(6) << (double)ma / 2 << "\n";
}

なぜWAになったかわかりますか？私はわかりませんでした(2ペナ)

制約をみると明らかでK=Nの入力がありえるのですがその場合に
ループが一度も回らず0.000000を出力していたからでした

本番でやったようにif文を継ぎ足してもいいのですがそれよりスマートなのは
累積和の配列の先頭に0をinsertするか最初から用意しておくことです

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> P(N + 1);
  for (int i = 1, sum = 0, p; cin >> p; i++)
    P.at(i) = sum += ++p;

  int ma = 0;
  for (int i = 0; i + K <= N; i++)
    ma = max(ma, P.at(i + K) - P.at(i));

  cout << fixed << setprecision(6) << (double)ma / 2 << "\n";
}

N + 1の配列を宣言して、添字1から入力を始める
これでN=Kのケースでもきちんと区間の和を求めることができました
二度と忘れない

for (int i = 1, sum = 0, p; cin >> p; i++) P.at(i) = sum += ++p;
このように書くと入力、1を足す、累積和にするの3つを同時にできます
同時にやらなくていいですがタイピング量は減ります

制約上intで足りるのでintに直しましたが
本番では少しでも危ないと思ったらlongを使っています
オーバーフロー怖い

問題文に
「絶対誤差または相対誤差が10^{-6}以下」云々とあったら
cout << fixed << setprecision(6) <<
10^{-10}以下だったら
cout << fixed << setprecision(10) <<
を出力するときに付けると良いです
前者の場合小数点以下6桁まで、後者の場合10桁までの出力を約束してくれます
fixedを忘れると整数部分も含めて6桁(10桁)という意味になり誤差で死んでしまいます

E - Almost Everywhere Zero

手も足も出ませんでした
桁DP、次回までに出来るように頑張ります

おしまい