雑記

競技プログラミングについての話題(?)

AtCoder Regular Contest 079

ooo- 95位(いえーい)

せっかく水から上がったのでまた潜水しないように頑張ります




C - Cat Snuke and a Voyage

arc079.contest.atcoder.jp

深さは2なので問題文の通りにdfsかけばいいか〜とか言ってdfs書いた

書いた後にfor文2つでよくないか...?みたいな気持ちになった

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

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const double eps = 1e-9;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ")
{ if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

vi g[202020];

int n = in(), m = in();

bool dfs(int d = 0, int v = 0) {
  if (d == 2) return v == n - 1;
  bool f = false;
  for (int i = 0; i < g[v].size(); ++i) {
    if (dfs(d + 1, g[v][i])) f = true;
  }
  return f;
}

signed main() {
  rep(i, m) {
    int a = in() - 1, b = in() - 1;
    g[a].pb(b);
    g[b].pb(a);
  }

  cout << (dfs() ? "POSSIBLE" : "IMPOSSIBLE") << endl;

}

D - Decrease (Contestant ver.)

arc079.contest.atcoder.jp

  • 2 \leq N \leq 50
  • 0 \leq K \leq 50 \times 10^{16}

↑怪しい(特に0 \leq K \leq 5 \times 10^{17}と書かれていないところが怪しい)

Nが小さすぎると 0 \leq a_i \leq 10^{16} + 1000が険しそうだなあみたいな感じになって、分散させるためにN = 50で決め打ちしたい気持ちになります

数列aK回操作した後に数列の中身が49になっているといいなあと考えると、そこを基準にK/50だけ足したものを構成するといいことがわかる(説明が世界一下手)

正確にはK/50が整数ではないので、そのあまりの分は適当に分散させるとよい

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

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const double eps = 1e-9;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ")
{ if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

lint k = in();
vector<lint> a(50);

signed main() {
  rep(i, 50) {
    a[i] = k / 50;
    if (i < k % 50) a[i]++;
  }

  rep(i, 50) {
    lint d = a[i];
    a[i] *= 50;
    a[i] += 49 - (k - d);
  }

  cout << 50 << endl;
  print(a);
}

E - Decrease (Judge ver.)

arc079.contest.atcoder.jp

一回一回操作していたら明らかに死んでしまうことはさすがにわかるので、まとめてできないかなあみたいに考える。

N個全部に対して一気に操作しても正当性としては問題ない気がしてきて、その計算量を考えても問題ない気がしてくるので実験をするとどうやら間に合いそうだなあみたいな感じに落ち着く(最悪)(WAが怖いので一応ちゃんと考えました)

結構時間ロスしたのでサンプルがあった時点で提出するべきだったなあみたいな気持ちになった

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

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const double eps = 1e-9;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ")
{ if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

signed main()
{
  int n = in();
  vector<lint> a;

  rep(i, n) a.pb(in());

  lint ans = 0;
  while (true) {
    bool f = true;
    rep(i, n) if (a[i] >= n) f = false;
    if (f) break;

    lint cnt = 0;
    rep(i, n) {
      cnt += max(0ll, a[i]) / n;
    }
    rep(i, n) {
      lint d = max(0ll, a[i]) / n;
      a[i] = a[i] - d * n + (cnt - d);
    }

    ans += cnt;
  }

  print(ans);
}