ei1333の日記

ぺこい

ACM-ICPC 2017 国内予選 参加記

21st. 大学別11th. ウクニキアさんの悪魔的妨害がなければとりあえずは通過っぽい.

f:id:ei1333:20170715012528p:plain

本番直前

  • 16時まで講義(しかもちょっと講義がのびて悲しい) だったので, 僕はわりと慌ただしかった.
  • なんで講義があるんだろう.
  • ファンタグレープがほしかったんだけど, 飲み物を買う時間がなくて自販機のスポーツドリンクで済ませてしまった.
  • 飲み物で 1WA.
  • あとスマホのバッテリーの充電を忘れていて, ドロップアウトしたので悲しい.
  • ぞい.

本番

  • 記憶が曖昧だけど, だいたいは合ってると思うのでゆるして.
  • 僕と1人の先輩は考察, もう1人の先輩は実装みたいな方針で.
  • まず D を読みます.
  •  {nm \le 500} なのでフローだとおもう
  • うし生終了
  • 新生うしにご期待下さい
  • 偶数個なのでなんかマッチングさせたい.
  • うーん、不可能!w(不可能なので.
  •  {nm \le 500} なので平方根とってみたい気持ちがよぎるも  {\sqrt {500} = 75} みたいにしてしまって一瞬でその解法が頭から消えた. 消えないで.
  • A 問題, B 問題が先輩  {2} 人によって通されます (7:14, 24:03).
  • B 問題の問題文が難しかったっぽい.
  • (A 問題で 1 WA してない?してない?気のせいだね)
  • C は先輩から概要を聞くとやるだけっぽいのではいとなる(ア.
  • C 問題が一番簡単らしい(32:54).
  • やる問題がなくなってしまった.
  • 悲しいね(悲しいので.
  • D がわからなかったので, E を読む.
  • 構文解析やんけ, 勝った.
  • よくよく考えると構文解析部分は自明だけど, 最小の長さみたいなのが非自明.
  • D の解法を先輩が思いつく.
  •  {nm} の大小に応じて, bitdpと貪欲で解けるらしい.
  • 解けそう(すごい).
  • チームのマスコットになった(かなしい.
  • bitset の使い方とか微妙な境界条件などを実装者に教えている.
  • 解けたらしい(1:03:59).
  • FGH を読むけどあーってなる.
  • G はフローっぽい.
  • 最大流を使いそうなのでとりあえず実装してもらう.
  • うまくいかない……
  • かなしいね.
  • 4完で終わってしまうため悲しい.
  • E いろいろ考えるけど, なんか式を整理して潰していく方法だと実装険しいなあという雰囲気を感じる.
  • 式の評価は変数に全通り入れれば構文解析投げるだけ.
  • 16 文字以下なので, 考えられる全ての valid な式を全列挙してえいっていう解法がよさそうだとおもう.
  • 計算量見積もってないけど, 間に合うでしょみたいな感情.
  • 解法を投げます.
  • がんばっています.
  • F を考えます.
  • 折り紙をします.
  • 全然法則をつかめません.
  • 法則つかめたところで復元できません.
  • 折り紙の折り方を間違えて世界一頭が悪いと思う.
  • 悲しいので G に戻る.
  • 斜めにえいすることはなくて, なんかぐるってまわる閉路ができるなぁと思う.
  • E のデバッグを一緒にすると通ったらしい(2:35:11).
  • E なんでこんな解かれていないんだろうという話になる.
  • らてさんつらそう(ア
  • ヅつよい.
  • 実質ズ(くやしい.
  • G問題, これ貪欲にできないかなぁって相談していると右手法っていうのがあるらしい.
  • 右手法を途中まで.
  • 途中で反例をみつける.
  • 難しい.
  • 残り10分くらいになって最小流量制限付きのフローがあったなぁって思う.
  • 蟻本を見てこれから勉強をします(は???).
  • よくわからないけど気合いをすればいいらしい.
  • 終了  {1} 分前くらいにサンプルが合ってしまう(ア.
  • 終了(微妙にバグってたみたいなのでよかった(よくはなさそう.
  • そもそもフローじゃキツイっぽい

さいごに

アジア予選がんばるぞい!!!!

牛肉食べたい.

おまけ

実装が軽そうだったのでEとGを解いてみた.

E

validな論理式を小さい方から生成していく.

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

string S;
int idx;
int mp[256];
map< int, int > SS;

bool E()
{
  if(S[idx] == '0') {
    ++idx;
    return(0);
  }
  if(S[idx] == '1') {
    ++idx;
    return(1);
  }
  if(isalpha(S[idx])) {
    ++idx;
    return(mp[S[idx - 1]]);
  }
  if(S[idx] == '-') {
    ++idx;
    return(1 ^ E());
  }
  ++idx;
  bool F = E();
  bool isxor = S[idx] == '^';
  ++idx;
  bool G = E();
  ++idx;
  if(isxor) return(F ^ G);
  else return(F & G);
}

int tobit(const string& s)
{
  int bit = 0;
  S = s;
  for(int j = 0; j < (1 << 4); j++) {
    mp['a'] = (j >> 0) & 1;
    mp['b'] = (j >> 1) & 1;
    mp['c'] = (j >> 2) & 1;
    mp['d'] = (j >> 3) & 1;
    idx = 0;
    bit |= E() << j;
  }
  return(bit);
}

int main()
{
  vector< string > valid[17];

  int ret = 0;
  
  for(int i = 1; i <= 16; i++) {
    vector< string > vv;
    if(i == 1) {
      vv.emplace_back("0");
      vv.emplace_back("1");
      vv.emplace_back("a");
      vv.emplace_back("b");
      vv.emplace_back("c");
      vv.emplace_back("d");
    }
    for(auto& s : valid[i - 1]) {
      vv.emplace_back("-" + s);
    }
    int sz = i - 3;
    for(int k = 1; k < sz; k++) {
      int l = sz - k;
      for(auto&& s : valid[k]) {
        for(auto&& t : valid[l]) {
          vv.emplace_back("(" + s + "^" + t + ")");
          vv.emplace_back("(" + s + "*" + t + ")");
        }
      }
    }
    for(auto& s : vv) {
      int bit = tobit(s);
      if(!SS.count(bit)) {
        SS[bit] = i;
        valid[i].push_back(s);
      }
    }
  }
  string S;
  while(cin >> S, S != ".") cout << SS[tobit(S)] << endl;
}

G

右手法(ア

#include <bits/stdc++.h>

using namespace std;

int n, m;
char g[55][55];
bool v[55][55];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

bool dfs(int y, int x, int dir, int num)
{
  if(y < 0 || x < 0 || y >= n || x >= m || g[y][x] == '#') return(false);
  if(v[y][x]++) return(false);
  if(num == 0 && y == 0 && x == m - 1) ++num;
  if(num == 1 && y == n - 1 && x == m - 1) ++num;
  if(num == 2 && y == n - 1 && x == 0) ++num;
  if(num == 3 && y == 1 && x == 0) ++num;
  if(num == 4) return(true);
  (dir += 3) %= 4;
  for(int i = 0; i < 4; i++, (dir += 1) %= 4) {
    if(dfs(y + dy[dir], x + dx[dir], dir, num)) return(true);
  }
  return(false);
}

int main()
{
  for(;;) {
    scanf("%d%d", &n, &m);
    if(n + m == 0) break;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) scanf(" %c", g[i] + j);
    }
    memset(v, false, sizeof(v));
    puts(dfs(0, 0, 1, 0) ? "YES" : "NO");
  }
  return 0;
}