ei1333の日記

ぺこい

GCJ 2018 Round2

ABCが通って393位.

A. Falling Balls

問題概要

{C(2 \le C \le 100)} 列の2次元グリッドがあって, 各列の一番上からボールを落下させる.

グリッドは '/', '\', '.' のいずれかから構成されて, '/' ならそこに落ちてきたボールは左の列に, '\' ならそこに落ちてきたボールは右の列に移動する. 他のボール同士は重なることができる.

一番下の {i} 列目に到達したボールの個数は {B_i} 個だった. 下の行と, 左右の列はすべて '.' で構成されていたことがわかっている. そのようなグリッドが存在するか判定し, 存在する時考えられる最小の行からなるグリッドの例を出力せよ.

解法

まず, 左右の列の {B_i} が {0} のとき, IMPOSSIBLE. 3秒考えるとそれ以外のときは必ず構成できることがわかる.

具体的な構成方法は, 左に落ちてくるボールの数から順番に調整する. その列に落ちてくるべきボールの列の範囲 {[l, r)} がわかるので, 一番下のその列から斜め方向に適切な数だけ '\' と '/' を {1} 本ずつ生やせば良い.

{O(TC^2)}.

#include<bits/stdc++.h>

using namespace std;

void beet() {
  int W, C[100];
  scanf("%d", &W);
  for(int i = 0; i < W; i++) {
    scanf("%d", &C[i]);
  }

  if(C[0] == 0 || C[W - 1] == 0) {
    puts("IMPOSSIBLE");
    return;
  }

  int t[110][110] = {{}};

  int l = 0;
  int pos = 1;
  for(int i = 0; i < W; i++) {
    if(C[i] == 0) continue;
    int r = l + C[i]; // [l, r)
    for(int j = 0; j < i - l; j++) {
      t[104 - j][i - j - 1] = 1;
      pos = max(pos, j + 2);
    }
    for(int j = 0; j < r - i - 1; j++) {
      t[104 - j][i + j + 1] = 2;
      pos = max(pos, j + 2);
    }
    l = r;
  }
  printf("%d\n", pos);
  for(int i = 0; i < pos; i++) {
    for(int j = 0; j < W; j++) {
      if(t[106 - pos + i][j] == 1) putchar('\\');
      else if(t[106 - pos + i][j] == 2) putchar('/');
      else putchar('.');
    }
    putchar('\n');
  }
}

int main() {
  int T;
  scanf("%d", &T);
  for(int i = 1; i <= T; i++) {
    printf("Case #%d: ", i);
    beet();
  }
}

B. Graceful Chainsaw Jugglers

問題概要

{R} 個の赤いチェーンソーと {B(1 \le R, B \le 500)} 個の青いチェンソーがある. これを何人かで分け合うが, 次の条件を満たす必要がある.

  • すべての人は {1} つ以上のチェーンソーを持つ必要がある.
  • ある人と赤の数も青の数がともに同数のチェーンソーを持っている人が存在してはならない.

最大で何人にチェーンソーを分け合えるか.

解法

なんか制約的にDPを疑う.

赤を {k} 個と青を任意個のペアを作る前には, 赤を {k-1} 個と青を任意個のペアを作っておいたほうがおとく.

そこで, 再帰関数 rec(k, r, b) を, 今までに赤を1人あたりの最大で {k-1} 個使って, 赤が残り {r} 個, 青が残り {b} 個のときに得られる最大人数と定義する.

{k} 個の赤とペアリングする青は, {0, 1, 2, 3, \dots} 個の順番にするのが最適なので, まあこれは赤の数を全探索して遷移させればできる.

複数テストケースが与えられるが, メモ化配列を毎回初期化せずに使い回せるので, 全体で {O(R^2B \sqrt B +T \sqrt B)} くらいと見積もれば, 実際はもっと少なそうなので間に合う.

#include<bits/stdc++.h>

using namespace std;

int dp[505][505][505];

int rec(int blackcur, int black, int white) {
  if(~dp[blackcur][black][white]) return dp[blackcur][black][white];
  int ret = 0;
  for(int i = 1;; i++) {
    int blackrest = black - blackcur * i;
    int whiterest = white - i * (i - 1) / 2;
    if(blackrest < 0 || whiterest < 0) break;
    ret = max(ret, rec(blackcur + 1, blackrest, whiterest) + i);
  }
  return dp[blackcur][black][white] = ret;
}

void beet() {
  int x, y;
  scanf("%d %d", &x, &y);
  int ret = rec(1, x, y);
  for(int i = 1;; i++) {
    int whiterest = y - i * (i + 1) / 2;
    if(whiterest < 0) break;
    ret = max(ret, rec(1, x, whiterest) + i);
  }
  printf("%d\n", ret);
}

int main() {
  memset(dp, -1, sizeof(dp));
  int T;
  scanf("%d", &T);
  for(int i = 1; i <= T; i++) {
    printf("Case #%d: ", i);
    beet();
  }
}

C. Costume Change

問題概要

{N \times N(2 \le N \le 100)} のグリッドが与えられる. {i} 行 {j} 列目には {A_{i, j} (-N \le A_{i,j} \le N, A_{i,j} \ne 0)} が書かれている.

次の操作がコスト {1} でできる.

  • あるマスの符号を反転させる
  • あるマスの値を同符号の範囲で絶対値が {1} 以上 {N} 以下の数に変更する.

すべての行, 列をみたときに同じ値が存在しないようにしたい. このために必要な操作の最小回数を求めよ.

解法

貪欲は無理そうとなると, どうみてもフロー以外の選択肢は残されていないのでフローを考える.

変更するマスの数の最小化はつまり, 残すマスの数の最大化である. そこで, {-N} から {N} の値ごとに残すマスの数を最大化したい気持ちになるが, これは蟻本にも載っている一方に行, もう一方に列をおいた二部マッチングにより解ける.

使わなかったセルをどうしようかなーと思っていると, 適切に操作することでなんとなくコスト {1} で変更できそうな気がしてきて, 変更できないと解ける問題には見えないので投げると通る(?).

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > dist, match;
  vector< bool > used, vv;

  Bipartite_Matching(int n, int m)
  {
    graph.resize(n);
    match.assign(m, -1);
    used.assign(n, false);
  }

  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
  }

  void bfs()
  {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a)
  {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }
};


void beet() {
  int N, X[100][100];
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      scanf("%d", &X[i][j]);
    }
  }
  int ret = 0;
  for(int i = -N; i <= N; i++) {
    Bipartite_Matching flow(N, N);
    for(int j = 0; j < N; j++) {
      for(int k = 0; k < N; k++) {
        if(X[j][k] == i) flow.add_edge(j, k);
      }
    }
    ret += flow.bipartite_matching();
  }
  cout << N * N - ret << endl;
}

int main() {
  int T;
  scanf("%d", &T);
  for(int i = 1; i <= T; i++) {
    printf("Case #%d: ", i);
    beet();
  }
}

D. Gridception

えーなんかたぶん誤読しているので(悲しいね

RUPC2018参加記

たぷたぷー

Day1

睡眠RTAをしたけど睡眠自体ができなかったので、大丈夫かこれーってなってるけど。

寝坊はしなかった(それはそう) なので、いい感じの時間に駅についてうく(@ukuku09)さんと合流する。一緒に新幹線着席を失敗。うくすぎる。

えーなんか前日のARCの話になって, うくさんがARCのEを頑張って考察してる。京都駅に着く前に解法ACをしててははっやっぱうくさんってやっぱすげえやって思った。

南草津駅くんで合流するびーと(@beet_aizu)くんに対して、言語不明瞭リプをn回送って混乱させようと思ったけど、ちゃんと合流した。一方でらてまるた(@lattemalta)くんとは合流できなかった。

にぼー

つりーわん(@treeone79)さんとかｼﾝﾔｶﾄｰ(@0x19f)さんとかうくさんとかの自己紹介面白い。びーとぽまえツイッターやってるだろ

コンテストはらてうしびーとで出る。僕はAのFAとCの方針じゃんけんとFの最悪遷移を雰囲気で書く係をする。Fが一発で通ってウケるをしていた気がする。びーとらての実装も異常にはやかかったため39分で全完して、終わったあとはらてが寝てびーとは壺をして僕はデレステをするをしていた。チーム戦としては上手く行ったのかな？？

懇親会では人と話せないをする。いつものメンバーでいつものをしていたきがする。

らてさんとツイン部屋を予約したので一緒に行ったらシングルベッドだった。らてさんが床で寝る。なんか帰ったら3秒くらいでともに寝落ちした気がする。

Day2

7時ごろ起きてシャワー浴びて、準備を済ませる。まだ時間あるなーって思ってぼーっとしているといつの間にか寝ていて面白かった。

そういう人生もまた悪くないよね。

コンテストはtsutaj(@TTJR)さんとtreeoneさんとでる。11時開始のコンテストだったけど11時に会場に到着したためAのFAを逃す。寝ていたのでDの読解を失敗して、不可能であることをチームメートに伝える（は？）Fが自明だったのでFを通す。Gはマッチングっぽいけど解けないので考えてると一般グラフの最大マッチングじゃんとなったのでAOJを信仰して誰かのライブラリをコピペして提出すると通る。Iをtsutajさんと確認するとbitdpで、最小包含円を貼れば良いことが分かるので、これもまた誰かのライブラリをコピペする方針を投げると、tsutajしゃんが実装してしばらくするとサンプルが合ったらしい。よさそうなので出すとTLE。こわれる。僕がどうせfloatとかにすれば通るんじゃないとか適当なこと言って試すとTLEするのでうくじゃーんってなる。そのうち再帰が重いとかいう話になり、非再帰にすると通ったみたい。Hを読むと実家だったのであー破滅、こわれるみたいな独り言をいいながら実装するとすぐ通る。Jはセグ木を使うと解けるらしい。Kは解法は分かったけど実装時間がTLE, Lは老後ゆっくり解きたいので、Eを考えることにする。Dをつりーわんしゃんが無限に考えてるけど。このあとなんですが、Eをダイクストラ実装して通そうとするけど19WAして冷えたり、Dわかんないなーって言ってるとコンテストが終わる。

ai1333なのにどうして僕のID名で提出するねん。びーとさんがマトロイドとセグメント木抽象化の布教でイキってたのが面白かった。

このあとなぜかうさみみを被って公道を歩いたら社会的に終了した。懇親会では共食いをしに行く。ぽまえしゃんとかうくしゃんとからてなどどアをする。らてさんが競プロに使える情報を流していてははっらてさんってやっぱりすげえやってなった。

ホテルでは言語不明瞭をしたりよりもいを見るをしたりしながら寝る。

Day3

起床成功。ぽまえしゃんからモーニングコールがかかってきたりする。 バスで、知見を得たり考察が成功したりする。

btkさんからNEW GAME!7巻を買い取る。

おるふぇ(@_olphe)さんとりか(@wk1080id)さんと出る。AのオンサイトFAをとったあと、Bをりかさん、Cをおるふぇさんの順で順調に解く（あとから解説聞くと難しそうだったのに順調に解いててすごいね）。Eが実家だったのでライブラリ芸をしてEを通す。DはDのDPなんですが、なんか向いていなさそうだったのでおるふぇさんに考察などを投げると、これもいい感じの速度で一発で通しててすごいなぁってなる。F全然わからないなぁをしているとフローじゃんとなって、おるふぇさんが全てを分かっていそうだったのでおるふぇさんが解く（なんか最短路DAGの作り方など微妙に方針を投げたりする）。Gをりかさんと考えるんですが、僕が蟻本で既出なのでDPとかイキっていると制約がヤバなので解けないじゃんということがわかったあとに、りかさんに貪欲でできない？と言われて天才じゃんってなる。現在の文字列からどのパターンにもマッチしない最右位置みたいなのが知りたくなるんですが、これはAho-crasickというライブラリを持っているため終わってしまった。まあGは普通に通る。 Fが微妙にバグっていたためなんかサンプルを確認したりソースをみたりしてみんなでデバッグをするんですが、目が悪くて目最短路を失敗したりしてた。そのうち、そもそもバグってないことがわかり（は？）提出するんですが、TLE（人生終了）。定数倍高速化か？とかいいながらフロー貼り替えたりなんか意味不明をしたりして高速化を試みるんですがデバッグが苦手なので6WAしちゃった（ゆるして）。

全完してからはwriterのtsutajさんをふぁぼ爆したり、NEW GAME!を見たりして平和に過ごす。

感想

ねねっちーはかわいいぞ。がおー。

みんなのプロコン2018 決勝 参加記

油そば　東京油組総本店 赤坂見附組
らてまるたしゃっふりゅーびーとで食べに行きました.
えーおいしい, おいしいね.

東京駅一番街　仙台牛タンねぎ塩ラーメン 㐂蔵
らずひるどびーとで食べに行きました.
らずひるどくんに会う難易度が高すぎる.
えーおいしい, おいしいね.

続きを読む