kichi2004's BLOG

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

競プロ

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

投稿日:2019年4月13日 更新日:

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

結果

全完 [A(100), B(200), C(300), D(400)] 39:46 ペナルティ: 1 (+5:00 -> 44:46)
・順位: 313位
・パフォーマンス: 1600 (Inner: 1718)
・Rating変化: 1142 -> 1198 (+56) [Rating最高値]

各問題の解法

A問題 (100点)

提出詳細
やるだけ。

int A, B;
cin >> A >> B;
if (A > B) {
  cout << A + max(A - 1, B) << endl;
} else {
  cout << B + max(A, B - 1) << endl;
}

B問題 (200点)

提出詳細
やるだけ。

  int N;
  cin >> N;
vector<int> H(N);
int max, ans = 1;
cin >> max;
for (int i = 1; i < N; i++){
  int h;
  cin >> h;
  if (max <= h) {
    ans++;
    max = h;
  }
}
cout << ans << endl;

C問題 (300点)

白黒白黒・・・・ と 黒白黒白・・・・ をそれぞれ試して小さい方を取る。
提出詳細

string S;
cin >> S;
int N = S.size();
vector<int> ans(2);

for(int i = 0; i < 2; i++) {
  //i = 0: 1010101....
  //i = 1: 0101010....
  //でそれぞれ塗り替える必要のある回数を数える
 int cnt = 0;
  for (int j = 0; j < N; j++)
  {
    if (S[j] != '0' + (j % 2 == i))
      cnt++;
  }
  ans[i] = cnt;
}
cout << min(ans[0], ans[1]) << endl;

D問題(400点)

提出詳細
0が連続する区間を求めておいて、K個埋めるものを N-K+1 パターン試す。

int N = ReadInt;
int K = ReadInt;
string S = Read;

var list = new List<Pair<int, int>>();
int l = 10000000, r = 0;
//0が(1つ以上)連続する区間について、(開始のindex, 個数)をメモしてlistに入れる
for (int i = 0; i < N; i++)
{
    if (S[i] == '0')
    {
        l = Min(l, i);
        r++;
    }
    else if (r != 0)
    {
        list.Add(make_pair(l, r));
        l = 10000000;
        r = 0;
    }
}

//最後が0だったときは、最後の区間も追加
if (r != 0) list.Add(make_pair(l, r));
//すべての区間について指示できる場合は、全員の人数を出力
if (list.Count <= K)
{
    Console.WriteLine(N);
    return;
}

//count: ループ回数, max: 答え
int count = list.Count - K + 1, max = list[K].first;
for (int i = 1; i < count; i++)
{
    //範囲の左端
    int A = list[i - 1].first + list[i - 1].second;
    //範囲の右端+1
    int B = i == count - 1 ? N : list[i + K].first;
    max = Max(max, B - A);
}

Console.WriteLine(max);

感想

初めてABCで全完しました!!!!
かつ、Beginnerで初1600perf!!!
めちゃめちゃ嬉しい!!
次落とさなければ無事に水色になれそうです!

-競プロ

執筆者:


comment

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

CAPTCHA


関連記事

no image

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

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

no image

JOI 2020 / 2021 本選 参加記

JOI (第20回日本情報オリンピック)の本選に参加しました.146 点(100 – 0 – 12 – 34)で本選落ちでした. ARC や AGC にも OI に …

no image

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

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

no image

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

コンテストページはこちら 結果 4完 [A(100), B(200), C(300), D(400)] 57:43 ペナルティ: 0 ・順位: 751位 (Rated) ・パフォーマンス: 1466 …

no image

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

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