AtCoder Regular Contest 078

C - Splitting Pile

arc078.contest.atcoder.jp

すぬけくんがカードの山の上から何枚かのカードを取ったあと、アライグマは残ったカード全てを取ります。

↑これ誤読してすぬけくんは任意の枚数を任意の場所から取れるものだと思っていた(ア)

問題文にある通り、すぬけくんもアライグマも少なくとも1枚は取らないといけないため、 通りを全部試す。

最初にアライグマに全部持たせると考えると差は あって、すぬけくんがアライグマから をもらった時に差は されるなあみたいな気持ちになると楽

#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(n);

  lint ans = linf, sum = 0;

  rep(i, n) {
    cin >> a[i];
    sum += a[i];
  }

  rep(i, n - 1) {
    sum -= 2 * a[i];
    chmin(ans, abs(sum));
  }

  cout << ans << endl;
}

D - Fennec VS. Snuke

arc078.contest.atcoder.jp

片方が塗れなくなったらゲームが終了と考えるのではなく、塗れなくなったらパスをするルールの元で、相手より多くのマスに色を塗るゲームだと考えても支障がないのでこのゲームを考える。(このとき、マスの個数が偶数かつ塗ったマスの個数が同じだった場合後手のすぬけくんが勝つことに注意)

まずはすぬけくんとフェネックの気持ちになって最適な行動を考える。

適当に手を動かしてみると、相手が通れないようにしてさえいれば後から自由に塗れることがわかって、この問題のグラフは木であることが保証されているのでそれが簡単にできる(これは雑な実験でもわかる気がする)

相手が確実に塗れない場所を塗るのは後回しでいいため放置すると考えると、できるだけ放置できる場所を増やすこと、自分が塗れない場所を増やさないことが最適な行動である気がしてくるので、相手との最短経路上をできるだけ急いで塗るゲームになる。

最短経路上を塗るついでに確実に自分が塗れるマスは塗ってしまうと実装が楽だった

#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<vi> g(n);

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

  int used[101010];
  memset(used, -1, sizeof(used));
  queue<pii> q;
  q.push(mp(0, 0));
  q.push(mp(n - 1, 1));

  while (!q.empty()) {
    pii p = q.front();
    q.pop();

    int v = p.fs;

    for (int i = 0; i < g[v].size(); ++i) {
      int u = g[v][i];
      if (~used[u]) continue;
      used[u] = p.sc;
      q.push(mp(u, used[u]));
    }
  }

  int cnt = 0;
  rep(i, n) if (!used[i]) cnt++;

  cout << (cnt <= n / 2 ? "Snuke" : "Fennec") << endl;
}

E - Awkward Response

arc078.contest.atcoder.jp

本番は(誤読しており)Cが明らかに解ける形じゃなかったため、これを考えていた

上位の桁から二分探索して全部の桁を決めていけばいいかなあみたいな気持ちになったので本番はそれを書いていたが、結局ACはできませんでした(悲しいね)

コンテスト終了後に桁数を二分探索すればいいみたいな話を聞いたためその方針を考えると、みたいな数字は性質がいいことがわかり(文字列としてかなり小さいため)、これを利用すると簡単に桁数が求められる。

みたいな自体がコーナーケースになるためそこだけ注意

桁数が求められたら二分探索してを求めておわり

初めてインタラクティブな問題を解いた*1

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

typedef long long lint;

void ans(lint n) {
  cout << "! " << n << endl;
}

bool q(lint n) {
  char c;
  cout << "? " << n << endl;
  cin >> c;

  return c == 'Y';
}

lint N;
bool debug(lint n) {
  cout << "? " << n << endl;
  return ((n <= N) == (to_string(n) <= to_string(N)));
}

int main() {
  int s;

  cin >> N;
  // cin >> s;

  bool f = q(1000000000000);
  if (f) {
    s = 1;
    for (lint i = 9; !q(i); i = i * 10 + 9) s++;
  } else {
    s = 0;
    for (lint i = 1; q(i); i *= 10) s++;
  }

  lint l = pow(10, s - 1) - 1, r = pow(10, s) - 1;
  while (r - l > 1) {
    lint m = (l + r) / 2;
    if (q(10 * m)) {
      r = m;
    } else {
      l = m;
    }
  }

  ans(r);
}

最終的な回答をするとか質問を投げるだけのとか手元実行用のとかを用意してみると一気に幸せになったので実装上のテクとして覚えておきたい

インタラクティブな問題での実装上のテクが他にもあったら教えてもらえると嬉しいです。