Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2218-39c4e8f0
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #96 DIV1 B問題/DIV2 D問題 - Piet (この記事を編集する[管理者用])

Source

Codeforces Beta Round #96 DIV1 B問題 (1500pt)
Codeforces Beta Round #96 DIV2 D問題 (2500pt)
Problem description

問題概要

m*mのグリッドの各セルに0~9までの数字が1つ書かれている.(mは50以下)
上下左右につながっているとして,1~9までの数字の連結成分は必ず中の詰まった長方形の形をしている.
最初一番左上のセルにいて,大きい矢印は右側,小さい矢印は上を向いている.
毎ターン,以下の行動を行う.
 今いるセルの連結成分から,飛び出さないまで,小さい矢印方向に移動する.
 今いるセルの連結成分から,1歩飛び出すまで,大きい矢印方向に移動する.
 ただし,移動する先が,そこが0だったり,グリッドの外なら移動せず,
  小さい矢印が,大きい矢印から見て左方向だったら,小さい矢印を反転させる.
  そうでなければ,大きい矢印を右に90度回転して,小さい矢印を大きい矢印から見て左方向にする.
nターン後 (5*10^7以下) にいるセルの数字を求める問題.
ただし,一番左上のセルは0でない.

解法

どこの連結成分にいるか,大きい矢印の向き,小さい矢印の向きで,状態数は高々50*50*4*2程度.
どういう風に状態遷移するかを最初に全部計算しておいて,シミュレーションする.
もしくは,ループを検出して,適当に端折る.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x,y;
char in[60][60];
int block[60][60], xa[6060], xb[6060], ya[6060], yb[6060], block_size;

int fst[6000][4][2];

int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};

int main(){
  int i,j,k,l,m,n;
  int a, b, tm;
  int now, d1, d2;
  int nx, ny;

  scanf("%d%d",&x,&n);
  rep(i,x) scanf("%s",in[i]);
  y = strlen(in[0]);

  rep(i,x) rep(j,y) block[i][j] = -1;
  
  block_size = 0;
  rep(i,x) rep(j,y) if(block[i][j]==-1 && in[i][j]!='0'){
    REP(k,i,x) if(in[k][j] != in[i][j]) break;
    REP(l,j,y) if(in[i][l] != in[i][j]) break;

    xa[block_size] = i; xb[block_size] = k-1;
    ya[block_size] = j; yb[block_size] = l-1;
    REP(a,i,k) REP(b,j,l) block[a][b] = block_size;
    block_size++;
  }

  rep(i,block_size) rep(j,4) rep(k,2) fst[i][j][k] = -1;

  tm = 0;
  now = 0; d1 = 0; d2 = 0;
  while(tm < n){
    if(fst[now][d1][d2] >= 0){
      int step = tm - fst[now][d1][d2];
      k = (n-tm-10) / step;
      if(k > 0) n -= step * k;
    } else {
      fst[now][d1][d2] = tm;
    }

    tm++;
    if(d1==0 && d2==0) nx = xa[now], ny = yb[now]+1;
    if(d1==0 && d2==1) nx = xb[now], ny = yb[now]+1;
    if(d1==1 && d2==0) nx = xb[now]+1, ny = yb[now];
    if(d1==1 && d2==1) nx = xb[now]+1, ny = ya[now];
    if(d1==2 && d2==0) nx = xb[now], ny = ya[now]-1;
    if(d1==2 && d2==1) nx = xa[now], ny = ya[now]-1;
    if(d1==3 && d2==0) nx = xa[now]-1, ny = ya[now];
    if(d1==3 && d2==1) nx = xa[now]-1, ny = yb[now];

    if(nx < 0 || nx >= x || ny < 0 || ny >= y || block[nx][ny]==-1){
      if(d2==1) d1 = (d1+1)%4;
      d2 = (d2+1)%2;
    } else {
      now = block[nx][ny];
    }
  }

  nx = xa[now];
  ny = ya[now];
/*  printf("%d %d %d %d\n",(int)(in[nx][ny]-'0'), now, d1, d2);*/
  printf("%d\n",(int)(in[nx][ny]-'0'));

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2218-39c4e8f0
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。