もふふろぐ

by

ARC 079

atcodercompetitivecppprogram

7月29日のAtCoder Regular Contest 079の感想です。3問を解いて1500点39:47で85位でした。自己最高記録が出た喜びで踊っています。

C Cat Snuke and a Voyage

重みなし無向グラフの頂点1と頂点Nの距離がちょうど2であるかを判定する問題。頂点1、頂点Nと辺がつながっている頂点をそれぞれ記録し、両方から辺が伸びている頂点があればPOSSIBLEです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  bool p[200000] = {}, q[200000] = {};
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (a == 0) {
      p[b] = true;
    }
    if (b == n - 1) {
      q[a] = true;
    }
  }
  bool r = false;
  for (int i = 0; i <n; i++) {
    r |= p[i] && q[i];
  }
  cout << (r ? "POSSIBLE" : "IMPOSSIBLE") << endl;
  return 0;
}

D Decrease (Contestant ver.)

すべての要素に1回ずつ操作を行うことは、すべての要素の値を1ずつ減らすことと同じです。そこでK回の操作を、前述の操作K / N回と残りのK % N回に分けて考えました。Nを縛る条件は無さそうなので適当に50とします。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  ll k;
  cin >> k;
  int n = 50;
  ll a, b;
  a = k / n;
  b = k % n;
  cout << n << endl;
  for (int i = 0; i < n; i++) {
    cout << n - 1 + a - b + (i < b) * n << ' ';
  }
  cout << endl;
  return 0;
}

ABCのA問題からD問題までは問題名の頭文字がA～Dになっています。

E Decrease (Judge ver.)

D問題と対になった問題。入出力が逆になっています。

必ずしも「数列のうち最も大きい要素」を選ぶ必要はなく、N以上のどの要素を操作しても結果は同じになります。N <= 50なのでループを回してシミュレーションしても間に合いました。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  int n;
  ll a[50];
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int l = 0, r = 0;
  ll k = 0;
  do {
    if (a[r] >= n) {
      ll t = a[r] / n;
      a[r] -= t * n;
      for (int i = 0; i < n; i++) {
        if (i != r) {
          a[i] += t;
        }
      }
      k += t;
      l = r;
    }
    r = (r + 1) % n;
  } while (l != r);
  cout << k << endl;
  return 0;
}

F Namori Grundy

解けず。なもりグラフという言葉を学びました。

いちいちincludeしたりint64_tを使ったりしていたものを、今日初めてbits/stdc++.hを利用したりtypedef long long llしたりと競技プログラミングらしいことを試してみました。これからも続けていきたいところ。

今回の結果が絶好調だったため、ついに念願の青レート（1600以上）になることができました。WAもTLEも無かったのは奇跡です。果たしてこのレートを維持することはできるのか。