解法：線形に調べるだけ

コーナーケースが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;
  }
}

そーすにっき

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

AOJ2101

AOJ2440

ICPCにっき

AOJ1188