解法：場合分けして点数計算O(1)

とにかくinputが分厚い

デバッグが大変　おわり

結構な時間これに費やしたのでもうやりたくない一問

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>

#define i64 long long
#define ui64 unsigned long long
using namespace std;

int c_points[5][14];
int h_points[10];

struct card{
  int num;
  int mark;
  card(char n_,char m_):num(),mark(){
    switch(m_){
      case 'S': mark = 0; break;
      case 'H': mark = 2; break;
      case 'D': mark = 3; break;
      case 'C': mark = 1; break;
    }
    if(('0'<=n_)&&(n_<='9'))num=n_-'0';
    else{
      switch(n_){
        case 'T': num = 10; break;
        case 'J': num = 11; break;
        case 'Q': num = 12; break;
        case 'K': num = 13; break;
        case 'A': num = 1; break;
      }
    }
  }
  bool operator< (const card& a){
    return num==a.num?mark<a.mark:num<a.num;
  }
};

bool straight(vector<card>& hand){
  for(int i=0;i<4;i++){
    if((hand[i+1].num-hand[i].num==1)||\
        ((!i)&&(hand[4].num==13&&hand[i].num==1)));
    else return false;
  }
  return true;
}

bool flush(vector<card>& hand){
  for(int i=0;i<4;i++){
    if(hand[i].mark!=hand[i+1].mark)return false;
  }
  return true;
}

bool no_pair(vector<card>& hand){
  for(int i=0;i<4;i++){
    if(hand[i].num==hand[i+1].num)return false;
  }
  return true;
}

bool one_pair(vector<card>& hand){
  int p;
  for(int i=0;i<=4;i++){
    if(i==4)return false;
    if(hand[i].num==hand[i+1].num){
      p=i;break;
    }
  }
  for(int i=p+1;i<4;i++){
    if(hand[i].num==hand[i+1].num)return false;
  }
  return true;
}

bool two_pair(vector<card>& hand){
  int p;
  for(int i=0;i<=2;i++){
    if(i==2)return false;
    if(hand[i].num==hand[i+1].num){
      p=i;break;
    }
  }
  if(p==0){
    return hand[2].num==hand[3].num?hand[3].num!=hand[4].num:hand[3].num==hand[4].num;
  }
  if(p==1){
    return hand[3].num==hand[4].num;
  }
}

bool three_card(vector<card>& hand){
  if(hand[0].num==hand[2].num&&hand[0].num!=hand[3].num)return true;
  if(hand[0].num!=hand[1].num&&hand[1].num==hand[3].num&&hand[3].num!=hand[4].num)return true;
  if(hand[0].num!=hand[1].num&&hand[1].num!=hand[2].num&&hand[2].num==hand[4].num)return true;
  return false;
}

bool fullhouse(vector<card>& hand){
  int p;
  if(hand[1].num!=hand[2].num){
    if(hand[0].num!=hand[1].num)return false;
    for(int i=2;i<4;i++){
      if(hand[i].num!=hand[i+1].num)return false;
    }
    return true;
  }else{
    if(hand[3].num!=hand[4].num)return false;
    for(int i=0;i<2;i++){
      if(hand[i].num!=hand[i+1].num)return false;
    }
    return true;
  }
}

bool straight_flush(vector<card>& hand){
  return straight(hand)&&flush(hand);
}

bool four_card(vector<card>& hand){
  return hand[0].num==hand[3].num||hand[1].num==hand[4].num;
}

bool royal_straight_flush(vector<card>& hand){
  if(straight_flush(hand)){
    if(hand[0].num==1&&hand[4].num==13)return true;
  }
  return false;
}


i64 solve(vector<card>& hand){
  sort(hand.begin(),hand.end());
  i64 res=0LL;
  
  for(int i=0;i<5;i++){
    int m_=hand[i].mark;
    int n_=hand[i].num;
    res+=(i64)c_points[m_][n_-1];
  }
  if(royal_straight_flush(hand)){
    res*=(i64)h_points[8];
    return res;
  }
  if(straight_flush(hand)){
    res*=(i64)h_points[7];
    return res;
  }
  if(four_card(hand)){
    res*=(i64)h_points[6];
    return res;
  }
  if(straight(hand)){
    res*=(i64)h_points[3];
    return res;
  }
  if(flush(hand)){
    res*=(i64)h_points[4];
    return res;
  }
  if(fullhouse(hand)){
    res*=(i64)h_points[5];
    return res;
  }
  if(one_pair(hand)){
    res*=(i64)h_points[0];
    return res;
  }
  if(two_pair(hand)){
    res*=(i64)h_points[1];
    return res;
  }
  if(three_card(hand)){
    res*=(i64)h_points[2];
    return res;
  }
  if(no_pair(hand)){
    return (i64)0;
  }
  
  return -1;
}

int main(){
  int n;
  bool flag = false;
  while(1){
    if(!flag){
      cin >> n;
      if(cin.eof())return 0; 
      flag=true;
    }
    fill(&c_points[0][0],&c_points[4][13],0);
    fill(&h_points[0],&h_points[9],0);
    for(int i=0;i<4;i++){
      for(int k=0;k<13;k++){
        cin >> c_points[i][k];
      }
    }
    for(int i=0;i<9;i++){
      cin >> h_points[i];
    }
    char a[3];
    vector<card> hands;
    for(int i=0;i<n;i++){
      for(int k=0;k<5;k++){
        cin >> a;
        hands.push_back(card(a[0],a[1]));
      }
      cout << solve(hands) << endl;
      hands.clear();
    }
    if(flag){
      cin >> n;
      if(cin.eof())return 0; 
      else cout << endl;
    }
  }
  return 0;
}

2017-07-19

AOJ2501

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2501

解法：商と余のマンハッタン距離を求める　

計算量：O(N)

サンプルを見ればなんとなく分かるだろうか。

図が丁寧に書かれているのが分かりやすい。

但し入力の数字をそれぞれ-1しないと余りがw=4の時の出力が合わない。（それを注視したケースもある）

#include <iostream>
#include <cmath>
using namespace std;

int main(){
  int n,a,b,c,d,p,q,res=10000;
  cin >> n >> a >> b >> c >> d;
  a--;b--;c--;d--;
  for(int w=1;w<=n;w++){
    p = abs(a/w-b/w) + abs(a%w-b%w);
    q = abs(c/w-d/w) + abs(c%w-d%w);
    //cout << p <<" " << q << endl;;
    res = min(res,p+q);
  }
  cout << res << endl;
}

2017-07-17

AOJ2101

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2101

解法：線形に調べるだけ

コーナーケースがN=1の場合というのは恐れ入った。流石UT

N=1をどう弾いてやるかと思ったが結局最後の出力で無理やりdeficientにする方法で落ち着いた。

#include <cstdio>
  
#define i64 long long
using namespace std;
int main(){
  i64 r,n;
  while(scanf("%lld",&n),n){
    r=0LL;
    for(i64 i=1LL;i*i<n;i++){
      if(!(n%i)){
        r+=i;if(i>1)r+=n/i;
      }
    }
    // printf("%d %d\n",n,r);
    if(r>n){
      puts("abundant number");
    }
    else if(r==n&&n!=1){
      puts("perfect number");
    }
    else{
      puts("deficient number");
    }
  }
}

2017-07-15

AOJ2440

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2440

解法：やるだけ O(nm)

制約がゆるいのでソートの必要もない

ソートすると二分探索できるのでクエリが早く終わるはず

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
  int n,m;
  vector<string> u(257);
  string t;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> u[i];
  }
  cin >> m;
  bool open=false;//opened : true //closed : false
  for(int i=0;i<m;i++){
    cin >> t;
    if(find(u.begin(),u.end(),t)!=u.end()){
      if(open){
        cout << "Closed by " << t << endl;
        open = false;
      }else{
        cout << "Opened by " << t << endl;
        open = true;
      }
    }else{
      cout << "Unknown " << t << endl;
    }
  }
}

2017-07-15

ICPCにっき

結果：3完

A:5分でささっと書いてAC。プリンターの動作が怪しくB、Cをメンバーが見れず。

B:文字列の分割が見えた時点でメンバーにパス。1回WAを見て交代。

C:Bをコーディングしてもらっている間にO( (dw)^2 )の雑なコードで大丈夫と見えていたので交代即実装。如何せんdw<=100

B:Cの小バグを埋めている間にBの方のデバッグが終わったのですぐにデバッグを行ったがemacs保存ミスという痛恨のアホをやらかし2回目のWA。3回目でAC。

C:交代後バグを取り切ってAC。D行けるかもと希望を持った（ここまで1時間台）

D:最初問題を誤読しており無向グラフの隣接行列か何かと勘違いしていた。

すぐに勘違いを修正したはいいが今度はろくな解法が思いつかない。

Fに逃亡。

Eはとっつきにくそうだった。

その後3人でDとFを読んでいたがどちらも有効な解法が出ず、Gを実装してもらったがバグで無限ループ。終了

はんせい

DがbitDPに見えたが場合分けしてもmax(min(n,m))=22を見て断念した。

が、実はそれが正解だったらしい。

そして、全探索を枝狩りする方向に走ったがいい方法が見当たらなかった。

が、これでも通していたチームがいた。

けつろん：精進が足りなかった

max(min(n,m))=22で通るのか…（16くらいが限界だと思っていた）

2017-07-13

AOJ1188

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188

Hierarchical Democracy

ICPC2013のC問題

解法：やるだけ

括弧が閉じるたびに下階層から表を集めて上に持っていく作業をする

sstreamが案外便利かもしれない気がしてきた

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

int parseint(string s){
  stringstream ss(s);
  int r;
  ss >> r;
  return r;
}

int sumdiv2(vector<int> &a){
  int r=0;
  sort(a.begin(),a.end());
  for(int i=0;i<a.size()/2+1;i++){
    r+=a[i]/2+1;
  }
  return r;
}

int sum2(vector<int> &a){
  int r=0;
  sort(a.begin(),a.end());
  for(int i=0;i<a.size()/2+1;i++){
    r+=a[i];
  }
  return r;
}

int main(){
  int n;
  int stack;
  cin >> n;
  string s;

  vector<vector<int> > votes;
  while(n--){
    votes.clear();
    stack = 0;
    int max = 0;
    cin >> s;
    while(s[max]=='[')max++;
    votes.resize(max+3);
    for(int i=0;i<s.size();i++){
      if(s[i]=='[')stack++;
      else if(s[i]==']'){
        stack--;
        if(!votes[stack+2].empty()){
          if(stack+2==max){
            votes[stack+1].push_back(sumdiv2(votes[stack+2]));
          }else{
            votes[stack+1].push_back(sum2(votes[stack+2]));
          }
          votes[stack+2].clear();
        }
      }else{
        int r = parseint(s.substr(i));
        votes[stack].push_back(r);
        while(r/10){r/=10;i++;}
      }
    }
    cout << votes[1][0] << endl;
  }
}

そーすにっき

なんかいろいろのせておくばしょ

AOJ2218

AOJ2501

AOJ2101

AOJ2440

ICPCにっき

AOJ1188