活動日記 day 39

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

活動日記 day38

活動内容 :
輪講
コンテスト (Div1 : チーム戦, Div2 : 個人戦)

コンテスト :
Div1 : Virtual Arena: Room 3472
Div2 : Virtual Arena: Room 3473

コメント：
輪講ではDPについて学びました。
これを機に区間DPをマスターしましょう。

活動日記 day 37

活動内容 :
輪講
コンテスト (Div1 : チーム戦, Div2 : 個人戦)
新歓
コンテスト :
Div1 : Virtual Arena: Room 3420
Div2 : Virtual Arena: Room 3421

コメント：
第一回あり本輪読会を行いました。
コンテストはDiv1とDiv2に分かれて行いました。
新歓もありました。

活動日記 day 36

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

活動日記 day 35

活動内容 :
部活動紹介
コンテスト (チーム戦)
コンテスト : Virtual Arena: Room 3408

A - Water Rate

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int A = 0, B = 0;
int C = 0, D = 0;
int P = 0;
 
int main(void){
    cin >> A;
    cin >> B;
    cin >> C;
    cin >> D;
    cin >> P;
 
    int x = A * P;
    int y = (P <= C) ? B : B + D*(P-C);
 
    cout << min(x,y) << endl;
}

B - Christmas Party

#include <iostream>
#include <vector>
 
using namespace std;
 
int N = 0;
int M = 0;
 
int main(void){
    cin >> N;
    cin >> M;
 
    vector<int> A(M, 0);
    vector<int> P(N, 0);
 
    int target = 0;
    int count  = 0;
    int x = 0;
    int z = 0;
 
    for(int i=0; i<M; ++i){
        cin >> A[i];
    }
 
    for(int i=0; i<M; ++i){
        target = A[i];
 
        count = 0;
        for(int j=0; j<N; ++j){
            cin >> x;
 
            if(x == target){
                P[j] += 1;
                count++;
            }
        }
 
        P[target - 1] += (N - count);
    }
 
    for(int i=0; i<N; ++i){
        cout << P[i] << endl;
    }
}

C - Weather Forecaster

#include<iostream>
 
using namespace std;
 
int main(){
    //scanf("%d",&n);
    int h,w;
    cin>>h>>w;
    char cloud[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>cloud[i][j];
        }
    }
    for(int i = 0; i < h; i++){
        int j=0;
            while(cloud[i][j] != 'c'&&j<w){
                cout << -1;
                j++;
                                if(j<w){
                    cout<<" ";
                }
            }
            int count = 0;
            while(j<w){
                if(cloud[i][j] == 'c'){
                    //int count = 0;
                    count=0;
                    cout<<count;
                }
                else{
                    count++;
                    cout<<count;
                }
                j++;
                if(j<w){
                    cout<<" ";
                }
            }
            cout << endl;
    }
    //input finish
    return 0;
}

D - Silk Road

#include <iostream>
#include <algorithm>
#include <climits>
 
using namespace std;
 
int N = 0, M = 0;
int D[1000] = {0};
int C[1000] = {0};
 
int memo[1001][1001];
 
long dp(int i, int j){
 
    if(memo[i][j] != -1){
        return memo[i][j];
    }
 
    if(j > M){
        return memo[i][j] = INT_MAX;
    }
    if(i == N){
        return memo[i][j] = 0;
    }
 
    long x = dp(i, j+1);
    long y = dp(i+1, j+1);
 
    if(x == INT_MAX && y == INT_MAX){
        return memo[i][j] = INT_MAX;
    }else if(x == INT_MAX){
        return memo[i][j] = C[j] * D[i] + y;
    }else if(y == INT_MAX){
        return memo[i][j] = x;
    }else{
        return memo[i][j] = min(x, C[j] * D[i] + y);
    }
 
}
 
int main(void){
 
    fill(memo[0],memo[1000], -1);
 
    cin >> N >> M;
    for(int i=0; i<N; ++i){
        cin >> D[i];
    }
    for(int j=0; j<M; ++j){
        cin >> C[j];
    }
    cout << dp(0, 0) << endl;
}

E - 3-Primes Problem

#include <iostream>
#include <climits>
#include <vector>
 
using namespace std;
int main()
{
    int prime[1000];
    for(int i=0;i<1000;i++){
        prime[i]=1;
    }
    prime[0] = 0;// 1 is not prime
    for (int i = 0; i < 1000; i++)
    {
        if (prime[i] == 1)
        {
            //cout<<"hogehoge"<<endl;
            for (int j = (i + 1); (i + 1) * j <= 1000; j++)
            {
                prime[(i + 1) * j - 1] = 0;
            }
        }
    }
    int count = 0;
    for(int i = 0; i < 1000; i++){
        if(prime[i] == 1){
            count++;
        }
    }
    int number[count], n = 0;
    for(int i = 0; i < 1000; i++){
        if(prime[i] == 1){
            number[n] = i + 1;
            n++;
        }
    }
    int t=0;
    cin>>t;
    vector<int> a(t, 0);
    for(int i=0;i<t;i++){
        cin>>a[i];
    }
    for(int i=0;i<t;i++){
        for(int j = 0; j < count; j++){
            for(int k = 0; k < count; k++){
                for(int l = 0; l < count; l++){
                    if(a[i] == number[j] + number[k] + number[l]){
                        cout << number[j] << " " << number[k] << " " << number[l] << endl;
                        goto LABEL;
                    }
                }
            }
        }
        LABEL:
        continue;
    }
    return 0;
}

活動日記 day 34

活動内容 :
コンテスト ( 個人戦 )
コンテスト : AtCoder Virtual Contest

A - 25個の文字列
N-1を5で割った商と余りを１文字目と２文字目のインデックスに指定すれば解くことができます。
（全列挙したものをソートしても解くことは可能です。）

#include <iostream>
using namespace std;
 
int main() {	
	string S;
	int N;	
	cin >> S >> N;
	
	cout << S[(N - 1) / 5] << S[(N - 1) % 5] << endl;
	
	return 0;
}

B - 双子とスイカ割り
1行ずつシミュレートしましょう。

#include <iostream>
using namespace std;
 
int main() {	
	int N, A, B;
	cin >> N >> A >> B;
	
	int sum = 0;
	
	for(int i = 0; i < N; i++){
		string s;
		int d;		
		cin >> s >> d;
		
		if(d < A) d = A;
		else if(d > B) d = B;
		
		if(s == "West") sum += d;
		else sum -= d;
 
	}
	
	if(sum == 0) cout << 0 << endl;
	else if(sum > 0) cout << "West " << sum << endl;
	else cout << "East " << -sum << endl;
 
	return 0;
}

C - 双子と○×ゲーム
未定

D - 25個の整数
未定

E - ウサギとカメ
未定

活動日記 day 33

活動内容 :
コンテスト (チーム戦)
コンテスト : Virtual Arena: Room 3394

A - Selection of Participants of an Experiment

全探索で解けます。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int a[1001]={0};
 
int main() {
  int n;
  while(scanf("%d",&n),n!=0){
    for(int i=0;i<n;++i){
      scanf("%d ",&a[i]);
    }
    int minimum = INT_MAX;
    for(int i=0;i<n;++i){
      for(int j=i+1;j<n;++j){
        if(abs(a[i] - a[j]) < minimum)minimum = abs(a[i] - a[j]);
      }
    }
    printf("%d\n",minimum);
  }
 
  return 0;
}

B - Look for the Winner!
入力を捨てるのを忘れないようにしましょう。

#include <iostream>
#include <stdio.h>
using namespace std;
 
int main()
{
    while (true)
    {
    LABEL:
        int array[30] = {0};
        int n;
        int top = 0;
        int topalpha = 0;
        int next = 0;
        int nextalpha = 0;
        int amari = 0;
        cin >> n;
        if (n == 0)
        {
            return 0;
        }
        char temp;
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            temp = temp - 65;
            array[temp]++;
 
            //top sagashi
            for (int j = 0; j < 30; j++)
            {
                if (top < array[j])
                {
                    top = array[j];
                    topalpha = j;
                }
            }
 
            //2nd sagashi
            for (int j = 0; j < 30; j++)
            {
                if (next < array[j] && j != topalpha)
                {
                    next = array[j];
                    nextalpha = j;
                }
            }
            amari = n - i - 1;
            char hoge;

            if (top <= next + amari)
            {
                //mada wakaran
                continue;
            }
            else
            {
                //win top or tie
                if (top == next)
                {
                    cout << "TIE" << endl;

                    for (int j = 0; j < amari; j++)
                    {
                        cin >> hoge;
                    }
                    goto LABEL;
                }
                else
                {
                    printf("%c ", 65 + topalpha);
                    printf("%d\n", i + 1);
                    for (int j = 0; j < amari; j++)
                    {
                        cin >> hoge;
                    }
                    goto LABEL;
                }
            }
        }
        printf("TIE\n");
    }
    return 0;
}

E - Arithmetical CAPTCHA
全探索です。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int n[5];
char op[] = {'+','-','='};
 
bool check(deque<char> &ops) {
  bool found = false;
  rep(i,3) if( ops[i] == '=' ) { found = true; break; }
  if( !found ) return false;
  set<int> S;
  int v = n[0];
  rep(i,3) {
    if( ops[i] == '+' ) {
      v += n[i+1];
    } else if( ops[i] == '-' ) {
      v -= n[i+1];
    } else {
      S.insert(v);
      v = n[i+1];
    }
  }
  S.insert(v);
  return S.size() == 1;
}
 
bool dfs(int cur,deque<char> &deq) {
  if( cur >= 3 ) {
    return check(deq);
  }
  rep(i,3) {
    deq.push_back(op[i]);
    if( dfs(cur+1,deq) ) return true;
    deq.pop_back();
  }
  return false;
}
 
void compute() {
  deque<char> deq;
  assert( dfs(0,deq) );
  cout << n[0] << " ";
  rep(i,3) {
    cout << deq[i] << " " << n[i+1];
    if( i != 2 ) cout << " ";
  } puts("");
}
 
int main() {
  int T,CNT=1;
  cin >> T;
  while( T-- ) {
    cout << "Case #" << CNT++ << ": ";
    rep(i,4) cin >> n[i];
    compute();
  }
  return 0;
}

コメント：
蟻本を読んでSG定理を復習しようと思います。