AOJ0562 JOI 国の買い物事情

解法

---

Dijkstraしてそれぞれの街のショッピングモールまでの最短距離を求めて、
なんといえばいいか、その…
例えば「A街」と「B街」がありました。
「A街」からショッピングモールまでの最短ルートが10でした。
「B街」から(ry の最短ルートは15でした。
これでA街とB街までの道の長さが10だったら、困るじゃん。
で多分これを計算で求める。
ルート = A + ( B - A ) + ( A~B - ( B - A ) ) / 2
なんか図を書いてみたらこうなった。
あとは切り上げ。
nで割るとしたら ( もとの数 + n - 1 ) / n で良い感じに切り上げできる。

ソース

---

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef pair < int , int > Pi;
#define fr first
#define sc second
#define INF ( 1 << 30 )
struct edge{
  int to, cost;
};
vector < edge > info[3001];
int main() {
  int N, M, K;
 
  cin >> N >> M >> K;
  for(int i = 0 ; i < M ; i++ ){
    int a, b, c;
    cin >> a >> b >> c;
    info[a].push_back((edge){ b, c});
    info[b].push_back((edge){ a, c});
  }
 
  int used[3001];
  fill_n( used, 3001, INF);
  priority_queue< Pi , vector< Pi >,greater< Pi > > que;
  for(int i = 0 ; i < K ; i++ ){
    int a;
    cin >> a;
 
    que.push(Pi( 0, a));
    used[a] = 0;
 
    while(!que.empty()){
      Pi p = que.top();
      que.pop();
      for(int j = 0 ; j < info[p.sc].size() ; j++ ){
        edge e = info[p.sc][j];
        if( used[e.to] > p.fr + e.cost ){
          used[e.to] = p.fr + e.cost;
          que.push( Pi( used[e.to], e.to));
        }
      }
    }
  }
 
 
  int ret = 0;
  for(int i = 1 ; i <= N ; i++ ){
    for(int j = 0 ; j < info[i].size() ; j++ ){
      if( used[i] <= used[info[i][j].to]){
        const int java = used[info[i][j].to] - used[i];
        ret = max( ret, used[i] + java + (info[i][j].cost - java + 1) / 2);
      }
    }
  }
  cout << ret << endl;
}

AOJ2219 THE BYDOLM@STER

解法

---

個数無限のナップザック×3。
名前は見た感じ不要。入力がめんどくさかった。

ソース

---

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
 
int main() {
  int N, M, cost[300], exp[300][3], dp[301];
  while(cin >> N >> M){
    for(int i = 0 ; i < N ; i++ ){
      string s;
      getline(cin, s), getline(cin, s);
      cin >> cost[i] >> exp[i][0] >> exp[i][1] >> exp[i][2];
    }
    int ret = 0;
    for(int i = 0 ; i < 3 ; i++ ){
      fill_n( dp, 301, 0);
      for(int j = 0 ; j < N ; j++ ){
        for(int k = 0 ; k <= M ; k++ ){
          if(k - cost[j] >= 0 ){
            dp[k] = max( dp[k], dp[k-cost[j]] + exp[j][i]);
            ret = max( ret, dp[k]);
          }
        }
      }
    }
    cout << ret << endl;
  }
}

AOJ0283 勉強会

解法

---

2分探索使ってほげると良い。
multisetとかmapとか色々使ったけどやっぱりvectorが実行時間が短かった。

ソース

---

#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
using namespace std;
 
#define INF ( 1 << 30 )
typedef pair < int , int > Pi;
 
int main()
{
  int N, Q;
  int stmp[1000000], comp[1000000], a;
  char buff[1024];
  scanf( "%d %d", &N, &Q);
  for(int i = 0 ; i < N ; i++ ){
    scanf( "%d", &stmp[i]);
    comp[i] = stmp[i];
  }
  sort( comp, comp + N);
 
  vector< int > sym;
  while(Q--){
    scanf("%s %d", buff, &a);
    if(*buff == 'A'){ //ADD
 
      sym.push_back(stmp[a - 1]);
      sort( sym.begin(), sym.end());
 
    } else if(*buff == 'R'){ //REMOVE
 
      sym.erase( lower_bound( sym.begin(), sym.end(), stmp[a - 1]));
 
    } else { //CHECK
 
      int left = 0, right = INF;
      while(left != right){
        int center = ( left + right ) / 2;
        int pre = 0, BAN = 0;
        for(int i = 0 ; i < sym.size() ; i++ ){
          int p = distance( comp,lower_bound( comp, comp + N, sym[i] - center));
          BAN += max( p - pre, 0);
          pre = distance( comp, upper_bound( comp, comp + N, sym[i]));
        }
        BAN += max( N - pre, 0);
        if(BAN <= a) right = center;
        else left = center + 1;
      }
      if( left != INF) printf("%d\n", left);
      else puts("NA");
 
    }
  }
  return false;
}

AOJ0041: Expression

問題概要

---

10パズル

解法

---

括弧とか括弧とかが面倒なので面倒くさいけど場合分けで書いた。
((a.b).(c.d))
(((a.b).c).d)
((a.(b.c)).d)
多分この3通りだと思う。

ソース

---

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<sstream>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++ )
int d[4];
bool flg = false;
string s = "+-*";
int calc( int a, int op, int b){
  if( op == 0) return a + b;
  if( op == 1) return a - b;
  return a * b;
}
bool solve(int a, int b, int c){
  flg++;
  if(calc( calc( calc( d[0], a, d[1]), b, d[2]), c, d[3]) == 10){
    return printf("(((%d %c %d) %c %d) %c %d)\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  if(calc( calc( d[0], a, d[1]), b, calc( d[2], c, d[3])) == 10){
    return printf("((%d %c %d) %c (%d %c %d))\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  if(calc( calc( d[0], a, calc( d[1], b, d[2])), c, d[3]) == 10){
    return printf("((%d %c (%d %c %d)) %c %d)\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  return flg = false;
}
 
bool judge(){
  rep(i,3) rep(j,3) rep(k,3) if(solve( i, j, k)) return true;
}
int main(){
  while(flg = true){
    rep(i,4) cin >> d[i];
    if(!d[0] && !d[1] && !d[2] && !d[3]) break;
    sort(d, d + 4);
    do if(judge()) break; while(next_permutation(d,d+4));
    if(!flg) puts("0");
  }
}

AOJ0070 Combination of Number Sequences

解法

---

書いていて気持ちが良くなるメモ化再帰。
書いていて気持ちが良い(再掲)

ソース

---

#include<iostream>
#include<algorithm>
using namespace std;
int dp[10][1<<10][331], n; //nの制約は自明だけど sはどれくら(ry ← 331か
int rec( int now, int used,int sum){
  if( sum < 0 ) return 0;
  if( now == n ) return sum == 0;
  if(~dp[now][used][sum]) return dp[now][used][sum];
  int ret = 0;
  for(int i = 0 ; i < 10 ; i++ ){
    if((used >> i) & 1)
      ret += rec( now + 1, used&~(1 << i), sum - i * (now + 1));
  }
  return dp[now][used][sum] = ret;
}
int main(){
  int s;
  while(cin >> n >> s){
    fill_n( **dp, 10 * (1 << 10) * 331, -1);
    cout << rec( 0, (1 << 10) - 1, s) << endl;
  }
}