seri::diary::competitive_programming

AtCoderで茶から赤を目指す競プロ精進日記

ABC140

ABC 過去問練習 参戦記録

atcoder.jp

所要時間

  • 10分AB2完，CD分からず．．．これは情けない

解答メモ

A

  • そのまま
#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  cout << N * N * N << endl;
  
  return 0;
}

B

  • そのままsimulation
  • ほぼ解説pdfと同じでワラタ
#include <bits/stdc++.h>

#define REP(i, x) for (int i = 1; i <= (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  int A[20];
  int B[20];
  int C[20];

  long result = 0;
  
  cin >> N;
  REP(i, N) {cin >> A[i];}
  REP(i, N) {cin >> B[i];}
  REP(i, N-1) {cin >> C[i];}

  int last_a = -100;
  REP(i, N){
    result += B[A[i]];
    if(A[i] - last_a == 1){
      result += C[last_a];
    }
    last_a = A[i];
  }

  cout << result << endl;

  return 0;
}

C

  • 以下が分からなかった
    • sample1, 2が通るB_iが昇順のケースは書けたが，それ以外のケースを通す方法が分からなかった
    • つまり嘘解放しか書けていない．条件を充足する汎用的なソリューションが分からないマン． youtu.be
  • 解説放送を見て考える
    • 条件の読み替えをすると以下のようになる
      • A_1とA_N: B_1とB_{N-1}からのみ成約を受ける
      • それ以外: B_iとB_{i-1}の成約を受けるため，結果的にどちらか小さい方がA_i

この問題のキモはおそらく

B_k \geqq max(A_k, A_{k+1})

という条件を

B_k \geqq A_k \land B_k \geqq A_{k+1} \Leftrightarrow

A_k \leqq B_{k-1} \land A_k \leqq B_k

と読み替えられるかどうかにかかっていると思われる．

このように読み替え，A_iに注目すると

\displaystyle A_0 \leqq B_0

\displaystyle A_1 \leqq B_0 \land A_1 \leqq B_1

\displaystyle A_2 \leqq B_1 \land A_1 \leqq B_2

\displaystyle A_N \leqq B_{N-1}

という条件が成り立つので，このまま実装すればよい． 式の読み替えさえできてしまえば実装はめちゃくちゃ簡単なのだが，ここまで自力でたどり着くのが難しい気がする．

min, maxについては普段から使っている関数だが，他の当たり前につかっている定義についても前提を正確に意識しておかねばなるまい．例えば単純にドモルガンの法則で論理式を置き換えて解くような問題も競プロの世界ではあるのではないだろうか．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  int B[100];
  cin >> N;
  REP(i, N - 1) { cin >> B[i]; }

  int ans = B[0];
  for (int i = 1; i < N - 1; ++i) {
    ans += min(B[i], B[i - 1]);
  }
  ans += B[N - 2];

  cout << ans << endl;

  return 0;
}

D

  • 割とマジで全く手が出なかったので解説を読んで考える
  • 以下が参考になった qiita.com

考え方

  • 不幸な人が幸福に変化する条件は「目の前にいるやつが自分と同じ向きになる」のみ
  • 操作は指定範囲を「全部反転する」のみ
    • 例えば LLRRLL のようなケースでは，不幸な人はS[0]，S[3]，S[4]の3人で，幸運な人は3人である
      • 真ん中のRRを反転させると不幸な人はS[0]のみとなり，幸運な人が二人増える
      • 左端のLLを反転させると不幸な人はS[3]，S[4]の2人で，幸運な人は一人増える
      • 右端のLLを反転させると不幸な人はS[0]，R[5]の二人で，幸運な人は一人増える
    • 不幸な人が減るケースはこの「両端を含まない範囲を反転させて二人増やす」か「両端を含む範囲を判定させて一人増やす」の2パターンしか存在しない
    • また，反転を繰り返してLLLLL や RRRRR のように反転できたとしても，端の一人は必ず不幸になるため，幸福な人の最大人数はN-1
    • 一方で，端を反転させる動作は端を含まない範囲の反転をやり尽くした後の1回だけしか行わないように操作できる
      • よって最後に1回だけ幸福な人を一人増やす操作を行うことができるので，基本的に二人増やす操作を貪欲的に行えば幸福な人を最大化できることが分かる
  • 以上の条件を踏まえると，解法としては
    • 「K回全部を使って反転させて二人ずつ幸福な人を増やした場合の幸福な人数とN-1のどちらかの最小値を求める」ということになる
#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, n)
#define REPI(i,a,b) for(int i=int(a);i<int(b);++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, K;
  string S;

  cin >> N >> K >> S;

  int ans = 0;
  REPI(i, 1, N){
    if(S[i-1] == S[i]){
      ++ans;
    }
  }

  cout << min(ans + 2 * K, N-1) << endl;

  return 0;
}

感想

  • twitterでエゴサしたら結構色んな解き方があるようだったが，個人的には↑野参考リンクの説明が一番しっくり来た
  • 問題文だけを読むと決められた反転方法でしか最適解が得られないようにも読めるが，よく読めばそんなことは書いてなく，手元でいくつかのパターンを想定して試してみれば幸福な人がどのように増えるか検証できた．
  • サンプルも実はワナで，これにこだわると「LとRの並びが衝突するタイミングに注目すればいい」ということに気づきにくくなる．そのため，単純に最適化すべき指標を最適化することだけを考えてシミュレートすることが重要だと思った．