kichi2004's BLOG

競技プログラミングの参加記とか日常とか。(※Google Analyticsを使用しています)

競プロ

「AtCoder Grand Contest 034」に参加しました

投稿日:2019年6月14日 更新日:

コンテストページはこちら

結果

2完 [A(400), B(600)] 49:18 ペナルティ: 3 (-> 64:18)
・順位: 736位 (Rated)
・パフォーマンス: 1552
・Rating変化: 1326 -> 1351 (+25) [Rating最高値]

各問題の解法

A問題 (400点)

提出詳細
A~Cの間と、B~Dの間に ‘##’ があると飛び越えることができないため、No。
D < C の場合は、すぬけ君がふぬけ君を飛び越える必要があるため、B-1~D+1の間に '...' が存在する必要がある。 計算量 O((C-A) + (D-B))

int N, A, B, C, D;
cin >> N >> A >> B >> C >> D;
string s;
cin >> s;
A–; B–; C–; D–;
bool ans = true;

for (int i = A; i < C; i++) {
  if (s[i] == ‘#’ && s[i + 1] == ‘#’)
    ans = false;
}

for(int i = B; i < D; i++) {
  if (s[i] == ‘#’ && s[i + 1] == ‘#’)
    ans = false;
}

bool ret = D > C;
for (int i = B; i <= D; i++) {
  if (s[i – 1] == ‘.’ && s[i] == ‘.’ && s[i + 1] == ‘.’)ret = true;
}

cout << (ans && ret ? “Yes” : “No”) << endl;

各問題の解法

B問題 (600点)

提出詳細
まず、BCは移動してもその形を壊さないため、これをXとおく。
前から線形探索をして、Aならカウントを1増やす、Xならカウントを答えに足す、それ以外ならカウントをリセットする。

計算量 O(N)

string sr;
cin >> sr;
int N = sr.size();
if(N < 3) {
  cout << 0 << endl;
  return 0;
}
string s;
for(int i = 0; i < N; i++) {
  if (i < N - 1 && sr[i] == 'B' && sr[i + 1] == 'C') {
    s += "X";
    i++;
  }
  else
    s += sr[i];
}

int cnt = 0;
long long ans = 0;
N = s.size();
for (int i = 0; i < N; i++)
{
  if (s[i] == 'A') cnt++;
  else if (s[i] == 'X') ans += cnt;
  else cnt = 0;
}
cout << ans << endl;

感想

600まで解いたけど+25で、なかなか厳しい世界になったなって感じがします。

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA


関連記事

no image

「AtCoder Beginner Contest 145」A~E問題解説 / 参加記

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 53:22 ペナルティ: 1 (-> 58:22) ・順位: 321位 (Rat …

no image

「Tenka1 Programmer Beginner Contest 2019」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:53 ペナルティ: 0 ・順位: 8位 ・パフォーマンス: 1600 (Inner: 2556) ・Rat …

no image

JOI 2020 / 2021 二次予選 参加記

はじめに おひさしぶりです.kichi2004 です.競プロ関係の記事は今年の 3 月以来 9 か月ぶりなので,まずはそれについて簡単にお話します.今年の 2 月に,JOI に二次予選落ちしたことや …

no image

「AtCoder Beginner Contest 121」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:16 ペナルティ: 0 ・順位: 1006位 ・パフォーマンス: 1108 ・Rating変化: 1039 …

no image

「diverta 2019 Programming Contest」に参加しました

コンテストページはこちら 結果 4完 [A(100), B(200), C(400), D(500)] 47:04 ペナルティ: 1 (47:04 -> 52:04) ・順位: 446位 (Unrat …