JOI予選2009

レシート

---

コンパイルせずに通したら1回TLE食らった。ループが10回になっていた。
サンプルは一応通そう(いましめ)

#include<iostream>

using namespace std;

int main(){
  int sum, in;
  while( cin >> sum, sum){
    for(int i = 0 ; i < 9 ; i++ ){
      cin >> in;
      sum -= in;
    }
    cout << sum << endl;
  }
}

すごろく

---

落ち着いて実装するだけ。

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(){
  int n, m, mas[1001];
  while( cin >> n >> m, n){
    for(int i = 1 ; i <= n ; i++ ){
      cin >> mas[i];
    }
    int ret = -1;
    for(int i = 1, now = 1, MLE ; i <= m ; i++ ){
      cin >> MLE;
      now = min( now + MLE, n);
      if( !~ret && now == n) ret = i;
      now = min( now + mas[now], n);
      if( !~ret && now == n) ret = i;
    }
    cout << ret << endl;
  }
}

パーティー

---

実装楽そうなわーしゃるふろいどを使った。
ただしこれだと実行速度がアレ。

#include<iostream>
#include<algorithm>

using namespace std;

#define INF ( 1 << 15 )

int main(){
  int n, m, mas[501][501];
  while( cin >> n >> m , n){
    fill_n( *mas, 501 * 501, INF);
    for(int i = 0, a, b ; i < m ; i++ ){
      cin >> a >> b;
      mas[a][b] = mas[b][a] = 1;
    }
    for(int i = 1 ; i <= n ; i++ ){
      for(int j = 1 ; j <= n ; j++ ){
        for(int k = 1 ; k <= n ; k++ ){
          mas[j][k] = min( mas[j][k], mas[j][i] + mas[i][k]);
        }
      }
    }
    int ret = 0;
    for(int i = 2 ; i <= n ; i++ ){
      if( !~(mas[1][i]-2) | !(mas[1][i]-2)) ret++;
    }
    cout << ret << endl;
  }
}

カード並べ

---

さっきからバグらせすぎなんだが(震え声) 眠いからかな？
bitで使ったカードを保存しながらsetに突っ込む。

#include<iostream>
#include<algorithm>
#include<string>
#include<set>

using namespace std;

#define INF ( 1 << 15 )

string array[10];
int n, k;
static set < string > ret;

void rec( string s, int bit, int cnt){
  if(cnt == k){
    ret.insert( s);
    return;
  }
  for(int i = 0 ; i < n ; i++ ){
    if((bit >> i) & 1) rec( s + array[i], bit&~(1<<i), cnt + 1);
  }
}
int main(){
  while(cin >> n >> k , n){
    for(int i = 0 ; i < n ; i++ ){
      cin >> array[i];
    }
    rec( "", (1 << n) - 1, 0);
    cout << ret.size() << endl;
    ret.clear();
  }
}

通勤経路

---

頑張って場合分けしてメモ化再帰。
多分以下の5つに場合分け出来る。
① スタート地点( 次どっちも行けて、その次どっちも曲がれる)
② 上上で来た( 次どっちも行けて、右に曲がった場合その次曲がれない)
③ 右右で来た( 次どっちも行けて、上に曲がった場合その次曲がれない)
④ 右上で来た( 次は上しか行けないけど、その次どっちも曲がれる)
⑤ 上右で来た( 次は右しか行けないけど、その次どっちも曲がれる)

#include<iostream>
#include<algorithm>

using namespace std;

const int MOD = 100000;
int w, h, dp[100][100][4];

int rec( int y, int x, int j){
  if( y >= h || x >= w) return 0;
  if( ~dp[y][x][j]) return dp[y][x][j];
  if( y == h - 1 && x == w - 1) return 1;

  int ret;
  if(!y && !x) ret = rec( y + 1, x, 0) + rec( y, x + 1, 1);
  else if( j == 0 ) ret = rec( y + 1, x, 0) + rec( y, x + 1, 3);
  else if( j == 1 ) ret = rec( y + 1, x, 2) + rec( y, x + 1, 1);
  else if( j == 2 ) ret = rec( y + 1, x, 0);
  else if( j == 3 ) ret = rec( y, x + 1, 1);

  return dp[y][x][j] = ret % MOD;
}
int main(){
  while( cin >> w >> h, w){
    fill_n( **dp, 100 * 100 * 4, -1);
    cout << rec( 0, 0, 0) << endl;
  }
}

方向音痴のトナカイ

---

眠いので前やったソース。もうちょっと早い解法があるのでまた今度やる。
普通にDFSやってるぽい(適当)

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
 
using namespace std;
 
typedef pair<int,int> Pt;
#define fr first
#define sc second
 
int mas[10][10],h,w,dx[]={0,1,-1,0},dy[]={1,0,0,-1};
Pt gl;
Pt Move(Pt p,int n){
  while(true){
    p.fr += dx[n] , p.sc += dy[n];
    if(p.fr >= 0 && p.fr < h && p.sc >= 0 && p.sc < w){
      if( mas[p.fr][p.sc] == 1 ) return p;
    }else return Pt(-1,-1);
  }
}
int solve(Pt p,int home){
  if( !home ){
    return ( p.fr == gl.fr || p.sc == gl.sc ? 1 : 0 );
  }
  int rec = 0;
  for(int i=0;i<4;i++){
    Pt s = Move(p,i);
    if(s.fr == -1) continue;
    mas[s.fr][s.sc] = -1;
    rec += solve(s,home-1);
    mas[s.fr][s.sc] = 1;
  }
  return rec;
}
int main(){
  while(cin >> w >> h && w){
    int home = 0;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cin >> mas[i][j];
        if( mas[i][j] == 1 ) home++;
        else if(mas[i][j] == 2 ) gl = Pt(i,j);
      }
    }
    cout << solve(gl,home) << endl;
  }
}