ACM-ICPC 2018 国内予選参加記

15位. 大学別6位.

去年が大学別11位なのでぼちぼち.

A をuoo38さんに任せる.
どうせei1333さんが実装してもFirst WAをとるのが目に見えているため.
B をgottoさんに任せる.
読みたくない&虚無をやりたくないため(最悪).
C をuoo38さんに任せる.
これ解法わからなかった.
しゃくとりっぽくないって言いながらしゃくとり書いたら, 有限時間で終わったため勝ちらしい.
D を僕が考える.
D は D の DP なので DP を考える.
不可能.
制約が小さすぎるため全探索くらいしかわからない.
これ豆知識なんですがね, ICPCの入力ケースには最悪ケースが書かれている場合が多いんですよね.
書いてあった.
10^6 通りくらいなので全探索するしかないでしょーとなる.

#include<bits/stdc++.h>

using namespace std;

int N, M;
int mat[9][9];
int rest[9];

int rec(int team, int enemy) {
  if(team == N) return 1;
  if(enemy == N) return rec(team + 1, 0);
  if(~mat[team][enemy]) return rec(team, enemy + 1);
  int ret = 0;
  if(rest[team] > 0) {
    rest[team]--;
    mat[team][enemy] = 1;
    mat[enemy][team] = 0;
    ret += rec(team, enemy + 1);
    mat[team][enemy] = -1;
    mat[enemy][team] = -1;
    rest[team]++;
  }
  if(rest[enemy] > 0) {
    rest[enemy]--;
    mat[team][enemy] = 0;
    mat[enemy][team] = 1;
    ret += rec(team, enemy + 1);
    mat[team][enemy] = -1;
    mat[enemy][team] = -1;
    rest[enemy]++;
  }
  return ret;
}

int main() {
  while(cin >> N, N) {
    cin >> M;
    memset(mat, -1, sizeof(mat));
    for(int i = 0; i < M; i++) {
      int x, y;
      cin >> x >> y;
      --x, --y;
      mat[x][y] = 1;
      mat[y][x] = 0;
    }
    bool flag = false;
    for(int i = 0; i < N; i++) {
      rest[i] = N / 2;
      mat[i][i] = 2;
      for(int j = 0; j < N; j++) {
        if(mat[i][j] == 1) rest[i]--;
      }
      if(rest[i] < 0) flag = true;
    }
    if(flag) cout << 0 << endl;
    else cout << rec(0, 0) << endl;
  }
}

全探索くらいならね, 橙コーダーの僕にかかれば数分で実装できるので.
なんかよくわからないけどはやい.
通ってウケる.
あと E か F か G なんですが, 問題文の見た目から E をチームメート 2 人に投げる.
E ぜんぜんわからねえ.
F を考える.
底辺の y 座標を固定してみる.
なんかある位置に／があったときに、＼を可能な最も右の位置に配置することを試したい気持ちになる.
／は左から右に走査していけば効率的に, ／よりも左上側と右下側にある点を管理できそう.
＼を置いたときに、正三角形に含まれうるものは、／より右下側にある点のうち＼よりも左下側にある点なので, これもなんかうぇいするとできそう.
／と＼は単調増加なのでしゃくとりできる.
ところで 60° 上の直線／や＼にある点ってどうやって求めるんですか？？
わからない(人生破滅)
チームメート3人で頑張って考えると, これは三角形の比 1:2:√3 の関係を使えば解けそうなことがわかる.
この三角形の比を解く問題しか3人で考えてなくないか(えぇ...)
三角形の比知らねえ.
ほんまやんけ, 終わりです.
多少実装重いけど, 頑張って実装する.
ところで O(n^2 log n) って破滅しませんか？
テストケースを試して tailf コマンドみたいなのを使って眺めると, 無限時間かかってるなーってなる.
定数倍改善をする.
えーまだ終わらないけど.
天才なので tailf コマンドは, プログラムの出力が全ておわっても終了しないことに気づく.
おわってるやんけおいおいおい.
提出する.
WrongAnswer(人生終了).
30分くらいデバッグしても間違いを発見できない.
よくみると提出ファイルが間違っています(意味不明).
出し直すと通る.
えぇ....

#include<bits/stdc++.h>

using namespace std;

int N, K;
int X[10000], Y[10000];

void beet() {
  cin >> K;
  vector< int > vs;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
    vs.push_back(Y[i]);
  }
  int need1 = N - K;
  sort(begin(vs), end(vs));
  vs.erase(unique(begin(vs), end(vs)), end(vs));
  double ret = 1e30;
  for(int y_0 : vs) {
    vector< pair< int, int > > need;
    for(int i = 0; i < N; i++) { // y_0 yori ue
      if(y_0 <= Y[i]) need.emplace_back(X[i], Y[i]);
    }
    vector< pair< double, int > > hidari;
    vector< pair< double, int > > migi;
    for(int i = 0; i < need.size(); i++) {
      auto p = need[i];
      if(p.second == y_0) {
        hidari.emplace_back(p.first, i);
        migi.emplace_back(p.first, i);
      } else {
        double dist = p.second - y_0;
        hidari.emplace_back(p.first - dist / sqrt(3), i);
        migi.emplace_back(p.first + dist / sqrt(3), i );
      }
    }
    sort(begin(hidari), end(hidari));
    sort(begin(migi), end(migi));

    vector< int > st(hidari.size()), inner(hidari.size());
    int ptr = 0;
    double last = -1e9;
    int add = 0;

    for(int i = 0; i < hidari.size(); i++) {
      st[hidari[i].second] = true;
    }

    for(int i = 0; i < hidari.size(); i++) {

      while(ptr < migi.size() && add < need1) {
        if(st[migi[ptr].second]) {
          inner[migi[ptr].second] = true;
          last = migi[ptr].first;
          ++add;
        }
        ++ptr;
      }


      if(add >= need1) {
        ret = min(ret, last - hidari[i].first);
      }

      if(inner[hidari[i].second])  {
        inner[hidari[i].second] = false;
        --add;
      }
      st[hidari[i].second] = false;
    }
  }
  cout << fixed << setprecision(15) << ret * 3 << endl;
}

int main() {
  while(cin >> N, N) beet();
}

そもそも僕が実装したコードがバグっているわけがなくて(頭がバグってる).
E を考える.
終了5分前くらいにチームメートが閃いたって言ってる.
間に合わないね.

えー僕の意味不明ムーヴがあったり, Eの終了直前解法閃きみたいなのがありそこらへんは改善の余地ありそうですがまずまず. チームのそれぞれで適正のある問題を考察とか実装できてたと思う..

ei1333の日記

ぺこい

ACM-ICPC 2018 国内予選参加記