JMO / JOI 2012 本選

JMO JOI Algorithm

JMO

他の予選免除者が軒並み4完している中3完しかできず死亡

  • 1: 適当に中線を取ると平行が示せて平行と垂直を使うと垂直が示せる
  • 2: 適当にやるとf(x)の形がすぐに限定できて、適当に条件に代入してf(x)を一意に限定できる。多分「これはみたす」ぐらいは書かないと減点される
  • 3: 二項定理ですぐに必要条件がわかって、Fermatの小定理からすぐにそれが十分条件だと分かる
  • 4: しらない
  • 5: いつか不可能になることを示そうとして死亡

JOI

今年から、問題解説終了後に暫定点数が配られるようになりました。
100 * 5 = 500
暫定で満点(金)3人、銀2人、銅3人いてやばい
追記：この500や金3銀2銅3というのは正式な結果になりました

以下、mm分ss秒と書いてあったらそれはその問題を送ってACを得られた時間を表します。

  • 1: とても簡単。12分55秒

解法の概略：やるだけ

#include <cstdio>
#include <cstring>

using namespace std;

const int SIZE = 1000005;
char in[SIZE+1];
int N, js[SIZE], os[SIZE], is[SIZE];

int max(int a, int b)
{
  return (a<b)?b:a;
}

int min(int a, int b)
{
  return (a>b)?b:a;
}

int main()
{
  scanf("%s", in);
  N = strlen(in);

  for(int i=0;i<N;i++){
    js[i] = os[i] = is[i] = 0;
    if(i==0){
      if(in[i]=='J') js[i]++;
      if(in[i]=='O') os[i]++;
    }else{
      if(in[i]=='J') js[i]=js[i-1]+1;
      if(in[i]=='O') os[i]=os[i-1]+1;
    }
  }
  for(int i=N-1;i>=0;i--){
    is[i] = 0;
    if(i==N-1){
      if(in[i]=='I') is[i]++;
    }else{
      if(in[i]=='I') is[i]=is[i+1]+1;
    }
  }

  int ret = 0, tmp;
  for(int i=1;i<N-1;i++){
    if(in[i]=='O' && in[i+1]=='I'){
      int v = min(is[i+1], js[i-os[i]]);
      
      if(v < os[i]) continue;

      ret = max(ret, os[i]);
    }
  }

  printf("%d\n", ret);

  return 0;
}
  • 2: とても簡単。17分16秒

解法の概略：やるだけ

#include <cstdio>
#include <algorithm>

using namespace std;

int A, B;
int va[5000], vb[5000];

int main()
{
  scanf("%d%d", &A, &B);
  for(int i=0;i<A;i++) scanf("%d", va+i);
  for(int i=0;i<B;i++) scanf("%d", vb+i);
  
  int ret = 0;
  for(int i=0;i<B;i++){
    int p1=0, p2=i;
    for(;p1<A&&p2<B;p1++){
      if(va[p1]==vb[p2]) p2++;
    }
    ret = max(ret, p2 - i);
  }
  printf("%d\n", ret);

  return 0;
}
  • 3: 簡単。27分24秒

解法の概略：DP

#include <cstdio>
#include <algorithm>

using namespace std;

const int MINF = -1000000000;

int N, T, S;
int A[3001], B[3001];

int dp1[3002][3001];
int dp2[3002][3001];

int main()
{
  scanf("%d%d%d", &N, &T, &S);
  for(int i=1;i<=N;i++) scanf("%d%d", A+i, B+i);

  //solve about dp1
  for(int i=0;i<=S;i++) dp1[0][i] = MINF;
  dp1[0][0] = 0;
  for(int i=1;i<=N;i++){
    for(int j=0;j<=S;j++) dp1[i][j] = dp1[i-1][j];
    for(int j=B[i];j<=S;j++) dp1[i][j] = max(dp1[i][j], dp1[i-1][j-B[i]] + A[i]);
  }

  int S2 = T - S;
  //solve about dp2
  for(int i=0;i<=S2;i++) dp2[N+1][i] = MINF;
  dp2[N+1][0] = 0;
  for(int i=N;i>=1;i--){
    for(int j=0;j<=S2;j++) dp2[i][j] = dp2[i+1][j];
    for(int j=B[i];j<=S2;j++) dp2[i][j] = max(dp2[i][j], dp2[i+1][j-B[i]] + A[i]);
  }

  int ret = MINF;
  for(int i=0;i<=N;i++){
    int tmp1=0, tmp2=0;
    for(int j=0;j<=S;j++) tmp1 = max(tmp1, dp1[i][j]);
    for(int j=0;j<=S2;j++) tmp2 = max(tmp2, dp2[i+1][j]);
    ret = max(ret, tmp1 + tmp2);
  }
  printf("%d\n", ret);

  return 0;
}
  • 4: 簡単。40分53秒

解法の概略：累積和

#include <cstdio>
#include <algorithm>

const int MAX = 5010;

int left[MAX][MAX], right[MAX][MAX];
int N, M;

int main()
{
  int x, y, d;
  scanf("%d%d", &N, &M);
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) left[i][j] = right[i][j] = 0;
  for(;M--;){
    scanf("%d%d%d", &x, &y, &d);
    --x; --y;
    ++left[x][y];
    --left[x+d+1][y];
    --right[x][N-x+y];
    ++right[x+d+1][N-x+y];
  }
  for(int i=1;i<N;i++)
    for(int j=0;j<N;j++){
      left[i][j] += left[i-1][j];
      right[i][j] += right[i-1][j];
    }

  int ret = 0, total;
  for(int i=0;i<N;i++){
    total = 0;
    for(int j=0;j<=i;j++){
      total += left[i][j];
      total += right[i][N-i+j-1];
      if(total>0) ret++;
    }
  }
  printf("%d\n", ret);

  return 0;
}
  • 5: 少し難しい。92分55秒

下の解法の概略：
まずDijkstraにより、各頂点に対して「お祭り距離」（最も近いお祭りまでの距離）を求める。
その後、各辺に対しても「お祭り距離」を定め、Union-Findを用いてお祭り距離の大きい辺から順に併合を行う。(実際には、下のコードでは辺に対するお祭り距離は考えずに、頂点に対してのみ考え、お祭り距離が接続先以下のときにのみ併合を行うという方法で対処している）各クエリに対して、クエリの両端の頂点が併合された瞬間を知りたい。
ここで二分探索が使えるとうれしいが、普通に二分探索すると明らかに間に合わない。そこで、すべてのクエリに対して一斉に二分探索をかけることを考える。
簡単のためN=8とする。最初、すべてのクエリは「解は頂点[0, 8)の間のどれかのお祭り距離」と分かっているので、[0, 8)にすべてのクエリを登録する。お祭り距離の大きい方から順に頂点をソートし、その順で併合を順次行う。ここで、4番目(0-origin)の併合を行う直前に、登録されているすべてのクエリに対して、もう併合されているか、されていないかを確かめる。併合されているなら[0, 4)、されていないなら[4, 8)の間に答えはある。こうしてすべてのクエリの範囲が半分に絞れる。
次は、Union-Findを初期化し、またお祭り距離の大きい方から順に併合を行う。今度は2, 6番目の併合の直前に、それぞれ[0, 4)、[4, 8)に登録されているクエリに対してすでに併合されているか確認する。こうして[0, 2)、[2, 4)、[4, 6)、[6, 8)まで限定できる。次も同様にすると、すべてのクエリに対して位置が特定できる。
この解法は、適切に実装するとO(M log N + Q log N α(N) )になるが、下のコードではUnion-Findでランクを見ていないのでO(M log N + Q log^2 N)になる。作為解 O( (M+Q) log N)より(Union-Findの分だけ)遅い。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int N, M, K, Q;
const int DEPTH = 17;

struct union_find
{
  int val[100000];
  
  void init()
  {
    fill(val, val+N, -1);
  }

  int root(int p)
  {
    return (val[p]<0)?p:(val[p]=root(val[p]));
  }

  void join(int p, int q)
  {
    p = root(p); q = root(q);
    if(p==q) return;
    val[p] += val[q];
    val[q] = p;
  }
  
  void print()
  {
    for(int i=0;i<N;i++) printf("%d ", root(i));
    puts("");
  }
};

struct node
{
  node *next;
  int con, dist;
};

struct query
{
  query* next;
  int S, T, id;
};

node *graph[100000], pool[500000]; int pLast;
int dist[100000];
query *qs[1<<(DEPTH+1)], qpool[100000]; int qLast;

pair<int, int> dists[1<<DEPTH]; int dLast;
int sol[100000];

void add_edge(int S, int D, int C)
{
  node* tmp = &(pool[pLast++]);
  tmp->con = D; tmp->dist = C;
  tmp->next = graph[S];
  graph[S] = tmp;
}

void add_query(int S, int T, int id)
{
  query* tmp = &(qpool[qLast++]);
  tmp->S = S; tmp->T = T; tmp->id = id;
  tmp->next = qs[1];
  qs[1] = tmp;
}

void relabel_query(query* q, int pos)
{
  //it is assumed that no query refers q any longer
  q->next = qs[pos];
  qs[pos] = q;
}

void dijkstra()
{
  int x;
  for(int i=0;i<N;i++) dist[i] = -1;

  priority_queue<pair<int, int> > q;
  for(;K--;){
    scanf("%d", &x);
    q.push(make_pair(0, --x));
  }

  while(!q.empty()){
    pair<int, int> tmp = q.top(); q.pop();
    if(dist[tmp.second]!=-1) continue;
    dist[tmp.second] = -tmp.first;
    
    for(node* nd=graph[tmp.second];nd!=NULL;nd=nd->next)
      q.push(make_pair(tmp.first - nd->dist, nd->con));
  }

}

int main()
{
  scanf("%d%d%d%d", &N, &M, &K, &Q);
  for(int i=0;i<N;i++) graph[i] = NULL;
  pLast = 0; qLast = 0; dLast = 0;

  int x, y, z;
  for(;M--;){
    scanf("%d%d%d", &x, &y, &z);
    --x; --y;
    add_edge(x, y, z);
    add_edge(y, x, z);
  }

  dijkstra(); //calculate F-dist

  for(int i=0;i<(1<<(DEPTH+1));i++) qs[i] = NULL;
  for(int i=0;i<Q;i++){
    scanf("%d%d", &x, &y);
    add_query(--x, --y, i);
  }

  for(int i=0;i<N;i++){
    dists[dLast++] = make_pair(dist[i], i);
  }
  while((dLast&(-dLast))!=dLast){
    dists[dLast++] = make_pair(-1, -1);
  }
  sort(dists, dists+dLast);
  reverse(dists, dists+dLast);

  int mdepth = 0;
  for(int i=0;;i++) if((1<<i)==dLast){
      mdepth = i; break;
    }
  
  fill(sol, sol+Q, -1);
  int ps = 1;
  union_find uf;
  query* next;
  for(int i=mdepth-1;i>=0;i--){
    uf.init();
    for(int j=0;j<dLast;j++){
      if(((j>>i)&1)==1 && ((j>>i)<<i)==j){ //separate
        for(query* q=qs[ps];q!=NULL;q=next){
          next = q->next;
          if(uf.root(q->S) != uf.root(q->T)) relabel_query(q, ps*2+1);
          else relabel_query(q, ps*2);
        }
        ps++;
      }
      
      //join
      if(dists[j].second==-1) continue;
      for(node* nd=graph[dists[j].second];nd!=NULL;nd=nd->next){
        if(dists[j].first <= dist[nd->con]) uf.join(dists[j].second, nd->con);
      }
    }
  }

  for(int i=dLast;i<2*dLast;i++){
    for(query* q=qs[i];q!=NULL;q=q->next){
      sol[q->id] = dists[i-dLast].first;
    }
  }

  for(int i=0;i<Q;i++) printf("%d\n", sol[i]);
  return 0;
}

その後適当に、validatorを書いて完全フィードバックでない3, 4, 5をverifyする。

  • 6(テトリス): だんだん難しくなって手に負えなくなる

3のコードに美しくない部分があったので(なくても関係ないと知りつつ)resubmit。