CODE THANKS FESTIVAL 2017(Parallel)

A - Time Penalty

最大値出力。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int ans = 0;
  FOR(i,0,8) {
    int in; cin >> in;
    ans = max(ans, in);
  }
  cout << ans << endl;
  return 0;
}

B - Concatenated Palindrome

sの最後の文字を含む最長の回文を求める。回文でない部分の文字数がTの文字数となる。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s; cin >> s;
  int len = s.length();
  int ans = len - 1;
  // 中心1つ
  FOR(i,0,len) {
    int r = i, l = i;
    while(r < len && l >= 0 && s[l] == s[r]) {
      l--;
      r++;
    }
    if(r == len) {
      ans = min(ans, l + 1);
    }
  }
 
  // 中心二つ
  FOR(i,0,len-1) {
    int r = i + 1, l = i;
    while(r < len && l >= 0 && s[l] == s[r]) {
      l--;
      r++;
    }
    if(r == len) {
      ans = min(ans, l + 1);
    }
  }
  cout << ans << endl;
  return 0;
}

C - Factory

次にi番目の機械を使うときにかかる時間とiをpriority_queueに保存。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<ll, int> P;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K; cin >> N >> K;
  ll a[N], b[N];
  FOR(i,0,N) cin >> a[i] >> b[i];
  priority_queue<P, vector<P>, greater<P> > Q;
  FOR(i,0,N) Q.push(P(a[i], i));
  ll ans = 0;
  FOR(i,0,K) {
    P p = Q.top(); Q.pop();
    ans += p.first;
    Q.push(P(p.first + b[p.second], p.second));
  }
  cout << ans << endl;
  return 0;
}

D - Bus Tour

証明はできないけどM - gcd(N, M)でできた。。。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
//最大公約数
int gcd(int a, int b) {
  while (a && b) {
    if (a >= b) a %= b;
    else b %= a;
  }
  return a + b;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M; cin >> N >> M;
  int g = gcd(N, M);
  cout << M - g << endl;
  return 0;
}

E - Coin Authentication

インタラクティブ問題

袋が最大50個で10回まで質問できる。つまり5個ずつ質問できる。この5個の袋について1,10,100,1000,10000枚秤に乗せることで、8,9,10,11,12を区別できる。

秤に乗せたコインの合計の重さがsumの時、

重さxのコインを1枚乗せている場合 (sum - x ) % 10 == 0となる。

次に10枚乗せたコインの重さを調べる場合sum = (sum - x) / 10として、1枚乗せている場合と同じ方法で重さを求める。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int sum;
bool f() {
  bool ret = 0;
  if((sum - 8) % 10 == 0) {
    sum -= 8;
    ret = 0;
  }
  else if((sum - 9) % 10 == 0) {
    sum -= 9;
    ret = 1;
  }
  else if((sum - 10) % 10 == 0) {
    sum -= 10;
    ret = 0;
  }
  else if((sum - 11) % 10 == 0) {
    sum -= 11;
    ret = 1;
  }
  else if((sum - 12) % 10 == 0) {
    sum -= 12;
    ret = 0;
  }
  return ret;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  int s = 0;
  vector<int> ans;
  while(s < N) {
    
    cout << "? ";
    FOR(i,0,s) cout << "0 ";
    cout << "1 ";
    s++;
    if(s < N) cout << "10 ";
    s++;
    if(s < N) cout << "100 ";
    s++;
    if(s < N) cout << "1000 ";
    s++;
    if(s < N) cout << "10000 ";
    s++;
    FOR(i,s,N) cout << "0 ";
    cout << endl;
 
    cin >> sum;
    while(sum) {
      if(f()) ans.push_back(1);
      else ans.push_back(0);
      sum /= 10;
    }
  }
  cout << "! ";
  FOR(i,0,ans.size()) printf("%d%c", ans[i], (i == ans.size() - 1 ? '\n' : ' '));
  return 0;
}