読者です 読者をやめる 読者になる 読者になる

るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

AOJ演習

AOJ

最近、理論固めやバイトで忙しくて問題をほとんど解いていなかったのでひさしぶりにAOJ。
最近追加されたPCK2012予選過去問を解きました。


AOJ256(PCK 1): 10問解いたら何点取れる?
AIZU ONLINE JUDGE
書くだけ

int main(){
  int sum = 0;
  rep(i,10){
    int tmp; scanf("%d",&tmp);
    sum += tmp;
  }
  printf("%d\n",sum);
}


AOJ257(PCK 2): 乗車券
AIZU ONLINE JUDGE
書くだけ

int main(){
  int b[3];
  scanf("%d %d %d",&b[0],&b[1],&b[2]);
  if((b[0] == 1 && b[1] == 1 && b[2] == 0) || (b[0] == 0 && b[1] == 0 && b[2] == 1)) printf("Open\n");
  else printf("Close\n");
  
}


AOJ258(PCK 3): 家庭菜園
AIZU ONLINE JUDGE
最初から等差数列になっていることはないらしい。

bool isOK(vector<int>t){
  int d = t[1] - t[0];
  rep(i,t.size() - 1)
    if(t[i + 1] - t[i] != d) return false;
  return true;
}
int main(){
  int N;
  while(scanf("%d",&N) != EOF,N){
    N++;
    vector<int>h(N);
    rep(i,N) scanf("%d",&h[i]);
    rep(i,h.size()){
      vector<int>t;
      rep(j,h.size()){
	if(i == j) continue;
	t.pb(h[j]);
      }
      if(isOK(t)){
	printf("%d\n",h[i]);
	break;
      }
    }
  }
}


AOJ259(PCK 4): すべての数は6174に通ず
AIZU ONLINE JUDGE
書くだけ

bool all_same(string s){
  rep(i,s.size() - 1)
    if(s[i] != s[i + 1]) return false;
  return true;
}
void f(string N){
  int res = 0;
  if(all_same(N)) printf("NA\n");
  else{
    while(N != "6174"){
      string big,small;
      big = N;
      small = N;
      sort(big.rbegin(),big.rend());
      sort(all(small));
      int diff = atoi(big.c_str()) - atoi(small.c_str());
      char buff[100];
      sprintf(buff,"%d",diff);
      string nxt = buff;
      string zero(4 - nxt.size(),'0');
      nxt = zero + nxt;
      N = nxt;
      res++;
    }
    printf("%d\n",res);
  }
}
int main(){
  string N;
  while(cin>>N,(N != "0000")){
    f(N);
  }
    
}


AOJ260(PCK 5): パイプつなぎ職人の給料
AIZU ONLINE JUDGE
貪欲。
とりあえず、パイプをすべてつなげる。その時の長さの合計をS、本数をJとする。
この時の価値は V = SJ
となる。ここから、長さpのジョイントを1本取り除くと、価値は
V2 = (S - p)(J + 1) = SJ + S - p(J + 1) となる。
この作業による価値の変化量は
V2 - V1 = S - p(J + 1) となる。
(上式) > 0 の場合、この作業によって価値が増加する。逆に(上式) < 0の場合は減少する。
S - p(J + 1) > 0 <=> S - p > pJ .......① (増加の場合)
S - p(J + 1) < 0 <=> S - p < pJ .......➁ (減少の場合)
①式をなるべく維持するにはpを現在接続されているジョイントのうち最も短いものの長さとすればうまくいくことがわかる。
➁式において、一度この式を満たすと何度作業を繰り返しても、この式が崩れることはない。(なぜなら、Sはジョイントの長さだけ単調減少していき、pとJは単調増加するから)
よって、価値は単調減少していくため、以降作業をする必要はない。

ちゃんとした証明にはなっていないですが、とりあえずこんな感じで解きました。

int main(){
  int N;
  while(scanf("%d",&N),N){
    vector<int>pipe(N);
    vector<int>joint(N - 1);
    ll sum_length = 0,joint_c;
    joint_c = 1;
    rep(i,N){
      scanf("%d",&pipe[i]);
      sum_length += pipe[i];
    }
    rep(i,N - 1){
      scanf("%d",&joint[i]);
      sum_length += joint[i];
    }
    vector<int>jj = joint;
    sort(all(jj));
    ll res = sum_length * joint_c;
    for(int i = 0; i < jj.size(); i++){
      if(sum_length < jj[i] * (1 + joint_c)) break;
      sum_length -= jj[i];
      joint_c++;
      res = max(res,sum_length * joint_c);      
    }
    printf("%lld\n",res);
  }
}


AOJ261(PCK 6): マヤの大予言
AIZU ONLINE JUDGE
思ってたより楽だった。

const ll START = 735224;
int month[2][12] = {{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
int maya[5] = {144000,7200,360,20,1};
vector<int> split( string s, string c )
{
  vector<int> ret;
  for( int i=0, n; i <= s.length(); i=n+1 ){

    n = s.find_first_of( c, i );
    if( n == string::npos ) n = s.length();
    string tmp = s.substr( i, n-i );
    ret.push_back(atoi(tmp.c_str()));
  }
  return ret;
}
ll Sum_Day(vector<int>datas){
  ll sum = 0;
  if(datas.size() == 3){    
    for(int y = 0; y <= datas[0] - 1; y++){
      if(y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)) sum += 366LL;
      else sum += 365LL;
    }
    for(int m = 1; m <= datas[1] - 1; m++) sum += month[(datas[0] % 4 == 0 && (datas[0] % 100 != 0 || datas[0] % 400 == 0))][m - 1];
    sum += datas[2];
    sum = sum - START;
  }else{
    rep(i,5) sum += datas[i] * maya[i];
    sum = sum + START;
  }
  return sum;    
}
vector<ll> GreToMaya(vector<int>datas){
  ll sum = Sum_Day(datas);
  sum %= 1871999 + 1;
  //  printf("SumG:%lld\n",sum);
  vector<ll>res;
  rep(i,5){
    res.pb(sum / maya[i]);
    sum %= maya[i];
  }
  return res;
}
vector<ll> MayaToGre(vector<int>datas){
  ll sum = Sum_Day(datas);
  //  printf("SumM:%lld\n",sum);
  vector<ll>res(3);
  ll y = 0,m = 0,d = 1;
  for(y = 0;; y++){
    bool isleap = (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0));
    for(m = 0; m < 12; m++){
      for(d = 1; d <= month[isleap][m]; d++){
	sum--;
	if(sum == 0){
	  res[0] = y,res[1] = m + 1,res[2] = d;
	  return res;
	}
      }
    }
  }
  return vector<ll>();
}

int main(){

  
  string data;
  while(cin>>data,data != "#"){
    vector<int>s = split(data,".");
    vector<ll>res;
    if(s.size() == 3) res = GreToMaya(s);
    else res = MayaToGre(s);
    rep(i,res.size()){
      printf("%lld",res[i]);
      if(i == res.size() - 1) printf("\n");
      else printf(".");
    }
  }
}


AOJ262(PCK 7): すごろくを作る
AIZU ONLINE JUDGE
とりあえずグラフにしてみたけど、どう解こうか迷ってしまった。他の人の解法見て、探索するだけということに気付く。

閉路になるかどうかを判定して、そのようなノードに辿り着く可能性があるかを探す。

const int MAX_N = 300;
int Max,N;
int d[MAX_N],visit[MAX_N],acy[MAX_N];
int Acyclic(int start){
  if(visit[start]) return false;
  visit[start] = 1;
  if(start == N - 1) return true;
  for(int r = 1; r <= Max; r++){
    int next = min(N - 1,start + r);
    next += d[next];
    next = min(N - 1,next); next = max(0,next);
    if(Acyclic(next)) return true;
  }
  return false;
}
bool solve(int start){
  if(!acy[start]) return true;
  if(visit[start]) return false;
  visit[start] = true;
  for(int r = 1; r <= Max; r++){
    int next = min(N - 1,start + r);
    next += d[next];
    next = min(N - 1,next); next = max(0,next);
    if(solve(next)) return true;
  }
  return false;
}
int main(){
  while(scanf("%d",&Max),Max){
    memset(d,0,sizeof(d));
    scanf("%d",&N);
    N += 2;
    for(int i = 1; i < N - 1; i++) scanf("%d",&d[i]);
    for(int i = 0; i < N; i++){
      memset(visit,0,sizeof(visit));
      acy[i] = Acyclic(i);
    }
    memset(visit,false,sizeof(visit));
    cout<<(solve(0)?"NG":"OK")<<endl;
  }
}


AOJ263(PCK 8): ビートパネル
AIZU ONLINE JUDGE
jubeatの譜面をビットマスクで管理して、ビットdp書くだけ。

const int MAX_N  = 50;
const int MAX_STATE = (1 << 17);
int N,C;
vector<int>norts,touch;
int dp[MAX_N][MAX_STATE];
int Score(int state){
  if(state == 0) return 0;
  return (Score(state >> 1) + (state & 1));
}
int dfs(int n,int state){  
  if(n < N){
    if(dp[n][state] > 0) return dp[n][state];
    int res = 0;//dfs(n + 1,state);    
    for(int i = 0; i < C; i++)
      res = max(res,dfs(n + 1,((state ^ touch[i]) & state) | norts[n + 1]) + Score(state & touch[i]));
    return dp[n][state] = res;    
  }
  return 0;
}

int main(){
  while(scanf("%d %d",&N,&C) != EOF,(N || C)){
    memset(dp,0,sizeof(dp));
    norts.clear(),touch.clear();
    norts.resize(N + 10,0),touch.resize(C + 10,0);
    rep(i,N){
      rep(j,16){
	int tmp;
	scanf("%d",&tmp);
	norts[i] += pow(2.0,15 - j) * tmp;
      }
    }
    rep(i,C){
      rep(j,16){
	int tmp;
	scanf("%d",&tmp);
	touch[i] += pow(2.0,15 - j) * tmp;
      }
    }
    int res = dfs(0,norts[0]);
    printf("%d\n",res);
  }
}


AOJ264(PCK 9): 有限体電卓
AIZU ONLINE JUDGE
やるだけなんだけど、構文解析慣れてなくていろいろ手間取った。
二分累乗法を使う点だけ注意する。

typedef string::const_iterator State;

ll expression(State &begin);
ll term(State &begin);
ll number(State &begin);
ll factor(State &begin);
ll mod_pow(ll a,ll x,ll mod);
ll p;
string exps;

int main(){
  string s;
  while(scanf("%lld: ",&p), p){
    getline(cin, exps);
    exps.erase(remove(all(exps),' '),exps.end());
    State begin = exps.begin();
    try{
      ll ans = expression(begin);
      cout<<exps<<" = "<<ans<<" (mod "<<p<<")"<<endl;
    }catch(int num){
      cout<<"NG"<<endl;
    }
  }
}

ll expression(State &begin){
  ll ret = term(begin);
  while(true){
    if(*begin == '+'){
      begin++;
      ret = (ret + term(begin)) % p;
    }else if(*begin == '-'){
      begin++;
      ret = (ret - term(begin) + p) % p;
    }else{
      break;
    }
  }
  return ret;  

}
ll term(State &begin){
  ll ret = factor(begin);
  while(true){
    if(*begin == '*'){
      begin++;
      ret = (ret * factor(begin)) % p;
    }else if(*begin == '/'){
      begin++;
      ll fa = factor(begin);
      if(fa == 0) throw 0;
      ret = (ret * mod_pow(fa,p - 2,p)) % p;
    }else{
      break;
    }
  }
  return ret;
}
ll factor(State &begin){
  if(*begin == '('){
    begin++;   
    ll ret = expression(begin);
    begin++;
    return ret;
  }else{
    return number(begin) % p;
  }
}
ll number(State &begin){
  ll ret = 0;
  while('0' <= (*begin) && (*begin) <= '9'){
    ret *= 10;
    ret += (*begin) - '0';
    ret %= p;
    begin++;
  }
  return ret % p;
}
ll mod_pow(ll a,ll x,ll mod){
  ll ret = 1;
  while(x){
    if(x & 1) ret = ret * a % mod;
    x >>= 1;
    a = a * a % mod;
  }
  return ret % mod;
}


AOJ265(PCK 10): ねこまっしぐら
AIZU ONLINE JUDGE
普通にやっても絶対無理だし、どうせ幾何ゲーだろとか思って放置(クズ)