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

「M-SOLUTIONS プロコンオープン」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), D(500)] 68:17 ペナルティ: 0 ・順位: 725位 (Rated) ・パフォーマンス: 1498 ・Rating変 …

no image

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

コンテストページはこちら 結果 0完 ・順位: 1565位 ・パフォーマンス: 358 ・Rating変化: 1046 -> 992 (-54) 各問題の考察 感想 全くわからなかった。出なかったら良 …

no image

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

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

no image

「第3回 RCO日本橋ハーフマラソン 予選」に参加しました

コンテストページはこちら 結果:133位(A: 147位、B: 108位) A: 286,823点、B: 493,349点 予選突破はできませんでした。(ほぼ確実) 各問題の考察 A問題 (画像:in …

no image

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

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 57:43 ペナルティ: 0 ・順位: 662位 (Unrated) 各問題の解 …