AtCoder Regular Contest 079

ooo- 95位(いえーい)

ARC 079 : 1565 -> 1691 (+126, highest!!) pic.twitter.com/08fX9OMCPx
— らず (@Luzhiled) 2017年7月29日

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

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$ で決め打ちしたい気持ちになります

数列 $a$ を $K$ 回操作した後に数列の中身が $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);
}

Luzhiled's memo

メモということです

AtCoder Regular Contest 079

C - Cat Snuke and a Voyage

D - Decrease (Contestant ver.)

E - Decrease (Judge ver.)