(o_o)

ブログ。

KUPC2013

Cの原案とEとHを担当していました．
C
基本的に左上の頂点と右上の頂点が0flip，左辺と上辺と右辺が1flip，その他が2flipで，各行につき好きなマスをさらに+1flipできる．O(NM)．

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int a[128][128];

int main(void)
{
  int h, w;
  cin >> h >> w;
  for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++)
      cin >> a[i][j];
  for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++) {
      if (i == 0) a[i][j] = 1 - a[i][j];
      if (j == 0) a[i][j] = 1 - a[i][j];
      if (j == w-1) a[i][j] = 1 - a[i][j];
    }
  int res = 0;
  for (int i = 0; i < h; i++) {
    int num = 0;
    for (int j = 0; j < w; j++)
      num += a[i][j];
    if (num == w) num--; else num++;
    res += num;
  }
  cout << res << endl;
  return 0;
}

E
最短経路を求めて，その経路に従って進んでいくと，300*6=1800クエリくらいでゴールできる．

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int dist[512][512];
int dest[512][8][2];

int main(){
  int m, s, d;
  cin >> m;
  vector<int> a(6), n(m);
  for (int i = 0; i < 6; i++) cin >> a[i];
  cin >> s >> d;
  s--; d--;
  for (int i = 0; i < m; i++) cin >> n[i];
  for (int i = 0; i < 512; i++) {
    for (int j = 0; j < 512; j++) {
      dist[i][j] = (i == j) ? 0 : 1000000000;
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 6; j++) {
      for (int k = 0; k < 2; k++) {
        dest[i][j][k] = i + (2 * k - 1) * a[j];
        if (dest[i][j][k] >= 0 && dest[i][j][k] < m) {
          dest[i][j][k] += n[dest[i][j][k]];
          if (dist[i][dest[i][j][k]] > 0)
            dist[i][dest[i][j][k]] = 1;
        }
        else {
          dest[i][j][k] = i;
        }
      }
    }
  }
  for (int k = 0; k < m; k++)
    for (int i = 0; i < m; i++)
      for (int j = 0; j < m; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

  while (s != d) {
    int dice;
    cin >> dice;
    dice--;
    int stay = dist[s][d];
    int advance = dist[dest[s][dice][1]][d];
    int back = dist[dest[s][dice][0]][d];
    int res;
    if (stay <= advance && stay <= back) res = 0;
    else if (advance < stay && advance < back) res = 1;
    else res = -1;
    cout << res << endl;
    if (res != 0) s = dest[s][dice][(res + 1) / 2];
    fflush(stdout);
  }
  return 0;
}

H
二分探索．O((logN)^2)で1.5secくらい．

#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
  int c;
  long long n, k;
  scanf("%d", &c);
  while (c--) {
    scanf("%lld %lld", &n, &k);
    if (k * 2 - 1 > n) { printf("-1\n"); continue;}
    long long low = 1, up = n+3;
    while (up - low > 1) {
      long long med = (low + up) / 2, num = 0;
      for (long long a=med, m=n; m > 0; a=(a+1)/2,m/=3)
  num += max(min(a/2, (m+1)/2) - (m/3+1)/2, 0LL);
      if (num >= k) up = med; else low = med;
    }
    printf("%lld\n", low);
  }
  return 0;
}

ほんとはO(logN)の解答を用意していて，TLE1.0secの900点問題として出したかったが，諸事情によって×．0.4secくらい．
(1/2)^3>(1/3)^2であることを利用すれば，二分探索の中のループが高々3回で良いことがわかる．

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
  int c, piv;
  long long n, k;
  long long r[64], l[64], two[64], three[64], nthree[64];
  scanf("%d", &c);
  two[0] = 1; three[0] = 1;
  for (int i = 0; i < 63; i++) two[i+1]=two[i]*2, three[i+1]=three[i]*3;

  while (c--) {
    scanf("%lld%lld",&n,&k);
    n=(n+1)/2*2-1;
    if (k * 2 - 1 > n) { printf("-1\n"); continue; }
    if (k >= n/3+1) { printf("%lld\n", 2*k-1); continue; }
    piv = 0; nthree[0] = (n+1)/2;
    for (piv=0; n>0; n=(n/3+1)/2*2-1, piv++) {
      nthree[piv+1] = (nthree[piv]+1) / 3;
      r[piv] = (n+1)/2; l[piv] = n * two[piv];
      if (piv > 0) r[piv] += max(min((l[piv]+two[piv-1])/two[piv]  , nthree[piv-1]) - nthree[piv], (long long)0);
      if (piv > 1) r[piv] += max(min((l[piv]+two[piv-2])/two[piv-1], nthree[piv-2]) - nthree[piv-1], (long long)0);
      if (k > r[piv]) break;
    }

    long long low = min(l[piv-1]-1,l[piv]), up = l[piv-1];
    while(up - low > 1){
      long long med = (low + up) / 2, num = nthree[piv];
      for(int i = max(0, piv-3); i < piv; i++)
  num += max(min((med+two[i])/two[i+1], nthree[i]) - nthree[i+1], (long long)0);
      if(num >= k) up = med; else low = med;
    }
    printf("%lld\n", low+1);
  }
  return 0;
}

KUPC2013予定

KUPC2013は7/6に開催します．

京都大学プログラミングコンテスト(KUPC)は，アルゴリズムの問題を決められた時間内に解く能力を競うコンテストです． 問題は入門者向けの易しいものから上級者向けの難しいものまで幅広く用意される予定です．

京都大学の関係者かどうかに依らず，どなたでもご参加いただけます．
コンテストは AtCoder 上で行います．オンライン・もしくは会場から参加できます．
オンサイト会場は現在調整中です．
オンラインで参加される場合は事前申し込みは必要ありません．AtCoder より直接ご参加下さい．
コンテストは個人戦とします．

問題数は11問，コンテスト時間は5時間です．
問題文は日本語で記述されます．
問題はジャッジの想定する難易度の順番で並べられる予定です．
各問題に対し，部分点が設けられる可能性があります．

詳しくは http://www.kupc.jp/ を参照下さい．

質問等があればコメント下さい．

AtCoder#13

writerやってました．
いままで原案だけ投げつけて問題文とかテストケースとか全部AtCoderの中の人に任せてきたけど，今回の反省を踏まえてテストケースも問題文も自分で作ろうと思った．

A.
過去のA問題のなかで最も難しい．6通りの置き方について詰められる荷物の個数を求め，最も大きい物を返す．
First AC: Komakiさん(121sec)
Second AC: kyuridenamidaさん(124sec)
Third AC: mamekinさん(142sec)

B.
xに最も短い辺，yに二番目に短い辺，zに最も長い辺がくるように設置したとき容積最小．
First AC: aroshさん(271sec)
Second AC: Komakiさん(310sec)
Third AC: kyuridenamidaさん(348sec)

C.
典型的なNimの問題．NimだけじゃつまらないのでM=0のケースも入れたかったが，Cには難しすぎるのでやめた．
First AC: mamekinさん(864sec)
Second AC: uwiさん(936sec)
Third AC: climpetさん(1216sec)

D.
二部グラフの最小辺カバー．フローで解く．Mathじゃないよ．
WA多いから俺がミスってんじゃないかってかなり焦っていた
https://twitter.com/asi1024/status/313269693228126208
https://twitter.com/asi1024/status/313270257496227840
First AC: Komakiさん(3025sec)
Second AC: hirosegolfさん(3534sec)
Third AC: cgy4everさん(3741sec)

最終結果：http://arc013.contest.atcoder.jp/standings

ARC#008 問題C

「問題Cの解説をもっと詳しく書いてほしい」という要望が多かったので、詳しめに書きます。

問題文： http://arc008.contest.atcoder.jp/tasks/arc008_3

STEP 1
まず、それぞれの参加者について、自分が食べるたこ焼きが投げられてからそれを受け取るまでにかかる最短時間を求めます。求め方として、ダイクストラ法というものを使います。ダイクストラ法は始点から各点までの最短経路を求めるアルゴリズムですが、各点を参加者として、各辺の長さを「その二人の間の距離/投げる側の投げる速さの上限と受ける方の受ける速さの上限の小さい方」とすることで、ダイクストラ法を用いて最短時間を求めることができます。
http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
http://www.deqnotes.net/acmicpc/dijkstra/

  • かかる最短時間を配列tに入れます。最初は、たこ焼きを投げる人についてt=0、参加者についてt=∞を入れておきます。そして、すでにその人について最短時間が求まったかどうかをflagで管理します。最初は全ての人についてflag=falseです。
  • そして、「最短時間がまだ求まっていない人、すなわち、flag=falseとなっている人の中でtの値が最小の人(この人をAとする)について、全ての人に対してAからその人に投げた時にその人が受け取る時間を計算し、その結果がその人についてのtの値よりも小さい場合はtをその値に更新する」という操作を参加者の人数の回数だけ繰り返します。
  • これでそれぞれの参加者について、自分が食べるたこ焼きが投げられてからそれを受け取るまでにかかる最短時間を求めることができます。

このC問題において、全ての参加者にたこ焼きを投げてから最短時間でたこ焼きを届けることができます。言い換えると、全ての参加者に最短時間でたこ焼きを届けようとすると途中で中継する参加者が1秒以内に2個以上のたこ焼きを投げなければならないので不可能である、となる可能性は無いということです。何故ならば、最短時間で参加者にたこ焼きを投げる時、各中継者にも最短時間でたこ焼きが届くはずであり、同じ中継者に届く2個のたこ焼きがa秒の間を空けて最初に投げる人に投げられた場合、そのたこ焼きは必ず中継者にa秒の間を空けて届くはずだからです。したがって、全ての参加者にたこ焼きを投げてから最短時間でたこ焼きを届けることが可能なのです。

STEP 2
STEP1で、各参加者について自分が食べるたこ焼きが投げられてからそれを受け取るまでにかかる最短時間を求めました。しかし、これは最初にたこ焼きが投げられてから各参加者が受け取るまでの時間ではありません。何故ならば、「投げる人はたこ焼きを投げてから1秒間は次のたこ焼きを投げてはいけない」という制約があるからです。
ある参加者について、自分の食べるたこ焼きが投げられてから受け取るまでの最短時間をt、そして、自分のたこ焼きが最初のたこ焼きが投げられてからi番目に投げられた時、最初のたこ焼きが投げられてから自分のたこ焼きが投げられるまでの時間はi-1であり、最初のたこ焼きが投げられてから自分がたこ焼きを受け取るまでの時間はi+t-1です。したがって、全ての参加者についてのi+t+1の値の最大値がたこ焼きを配り終えるまでにかかる時間となるわけです。
i番目に自分のたこ焼きが投げられた人のtの値をt_iとします。たこ焼きを配り終えるまでにかかる時間が最小となるようにたこ焼きを配った時に、k番目の人が最後にたこ焼きを受け取る場合、t_k+k-1の値がたこ焼きを配り終えるまでにかかる時間となります。
ここで、t_kは全てのtのうちk番目に大きな値であるということを示します。

  • すべてのmより大きなkについて、t_k>t_mとなる。(kt_k+k-1となり、k番目の人よりも後にたこ焼きを受け取る人が存在することになるので矛盾。)
  • すべてのmより小さなkについて、t_kmについて、t_k>t_mとなるようなmが存在すると仮定すると、k番目とm番目の人のたこ焼きを投げる順序を入れ替えると、t_k+m-1
  • 以上より、t_m>t_kとなるmの個数はちょうどk-1個あることがわかるので、t_kは全てのtのうちk番目に大きな値であることがわかる。

ここで、全てのa,bについて、at_bとなるように投げる。そうすると、全てのiについて、i番目の人のtの値t_iはすべての参加者のtの中でi番目に大きな値となります。したがって、kの値がわかっていなくても、t_kの値をk番目に大きな値とすることができます。すなわち、
投げてから受け取るまでの時間のかかる人から順に優先的に配達する
ようにすればいいのです。

注意
自分にたこ焼きを投げないように注意。STEP1では最初に投げる人を考慮しますが、STEP2では除かなければいけません。

2
0 0 100 100
1 0 100 100

正
0.01

誤
1.00

各問題の解答ソースコード例
http://asi1024.hatenablog.com/entry/2012/09/22/220805

質問等あれば何でもコメントorリプライ下さい。