AtCoder 「みんなのプロコン 2019」

競技プログラミング

初めて本番でC問題を通すことができた。そして8回目の参戦でようやく茶色になれた。非常に嬉しい。

調子に乗って軽めの解説でも書こうと思う。より優れた解説記事は他にいくらでもあるので、以下の内容は競プロ初心者がどのような思考を経て回答にたどり着いたのかを眺める感じで楽しんでもらえたらなと思う。

A問題

差が2以上の数がどれだけあるかを愚直にforループを回して数えた。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  int N,K; cin>>N>>K;
  int cnt = 0;
  for(int i=0; i<N; i += 2) {
    cnt++;
  }
  string ans = cnt >= K ? "YES" : "NO";
  cout << ans << endl;
}

B問題

どこを始点・終点にすべきか判断させるコードが書けなかったので、脳死で3回以上登場する番号があればNOを出力するコードを出したらACだった。うけた。
今回はこんなんでも解けたが、普通はワーシャル・フロイド法なるものを使うのがセオリーらしい。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  map<int, int> dict;
  for(int i=0; i<3; i++) {
    int a,b; cin>>a>>b;
    a--; b--;
    dict[a]++;
    dict[b]++;
  }

  string ans = "YES";
  for(auto p: dict) {
    if(p.second >= 3) {
      ans = "NO";
    }
  }
  cout << ans << endl;
}

C問題

なんとなく貪欲法なるものが使えそうだと思った。A >= B の場合はいちいち換金する意味がないので K + 1 を出力する。
A < B の場合、とりあえずA枚貯まるまでビスケットを増やしていき、溜まったら (-A+B) していく(この時、2ターン消費されることに注意する)。
でもこれだけの実装だと、入力サンプルで通らないものがあった。普通に1枚ずつ増やしていくほうがいい場合があるからだ。この入力サンプルがなければ、WA頻発で半泣きになっていたことだろう。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  ull K,A,B; cin>>K>>A>>B;
  ull have = 1;

  if(A >= B) {
    have += K;
  } else {
    for(ull i=0; i<K; i++) {
      if(have >= A && i != K - 1) {
        have -= A;
        have += B;
        i++;
      } else {
        have += 1;
      }
    }
    have = max(have, 1+K);
  }

  cout << have << endl;
}

D問題

調子こいて挑んでみた。意味不明で泣きそうになった。問題文のストーリーもホラーだ。なんや耳を植えて石を詰めていくって。新手のスタンド使いかなにかか？

見てもらえればわかる通り、おれの思考過程は論理的でなくあまり褒められたものではない。解説も非常に雑だ。これが現時点での能力のすべてである。まあこのへんは競プロやってたらおいおい身につくやろみたいな気分ではいる。
今後については、C問題を安定して解けるようになることを目指す。これができるようになれば緑も夢ではないだろう。逆にできなければ茶のまま停滞するか、最悪の場合灰に逆戻りする羽目になるかもしれない。
まあ今日のところはあまり悲観的にならず、ぐっすり寝ようと思う。