AtCoder Regular Contest 007

Submission #1049149

Source codeソースコード

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

int main() {
  string tmp;
  cin >> tmp;
  int n = tmp.length();
  vector<string> s(n);
  rep (i, n) {
    s[i] = tmp.substr(i, n-i) + tmp.substr(0, i);
  }
  deque<deque<bool> > pattern(n, deque<bool>(n));
  rep (i, n) {
    rep(j, n) {
      pattern[i][j] = (s[i][j] == 'o') ? true : false;
    }
  }

  int ans = 20;
  int m = (1 << n);
  FOR (i, 1, m) {
    int cnt = 0;
    deque<bool> possible(n, false);
    rep (j, n) {
      if ((i >> j) % 2 == 0) {
        continue;
      }
      cnt += 1;
      rep (k, n) {
        possible[k] |= pattern[j][k];
      }
    }
    bool flag = true;
    rep (j, n) {
      flag &= possible[j];
    }
    if (flag) {
      ans = min(ans, cnt);
    }
  }
  printf("%d\n", ans);

  return 0;
}

Submission

Task問題 C - 節約生活
User nameユーザ名 056 tspcx
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1673 Byte
File nameファイル名
Exec time実行時間 21 ms
Memory usageメモリ使用量 1052 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,00_sample_04.txt,00_sample_05.txt,01_rand_00.txt,01_rand_01.txt,01_rand_02.txt,01_rand_03.txt,01_rand_04.txt,01_rand_05.txt,01_rand_06.txt,01_rand_07.txt,01_rand_08.txt,01_rand_09.txt,01_rand_10.txt,01_rand_11.txt,01_rand_12.txt,01_rand_13.txt,01_rand_14.txt,01_rand_15.txt,01_rand_16.txt,01_rand_17.txt,01_rand_18.txt,01_rand_19.txt,02_maxrand_00.txt,02_maxrand_01.txt,02_maxrand_02.txt,02_maxrand_03.txt,02_maxrand_04.txt,02_maxrand_05.txt,02_maxrand_06.txt,02_maxrand_07.txt,02_maxrand_08.txt,02_maxrand_09.txt,02_maxrand_10.txt,02_maxrand_11.txt,02_maxrand_12.txt,02_maxrand_13.txt,02_maxrand_14.txt,02_maxrand_15.txt,02_maxrand_16.txt,02_maxrand_17.txt,02_maxrand_18.txt,02_maxrand_19.txt,03_max.txt,03_maxret.txt,03_min.txt,03_special_01.txt,03_special_02.txt,03_special_03.txt,03_special_04.txt,04_special_05.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01.txt AC 21 ms 1048 KB
00_sample_02.txt AC 18 ms 928 KB
00_sample_03.txt AC 20 ms 1052 KB
00_sample_04.txt AC 20 ms 1052 KB
00_sample_05.txt AC 18 ms 928 KB
01_rand_00.txt AC 20 ms 924 KB
01_rand_01.txt AC 20 ms 1044 KB
01_rand_02.txt AC 18 ms 1052 KB
01_rand_03.txt AC 19 ms 1048 KB
01_rand_04.txt AC 20 ms 924 KB
01_rand_05.txt AC 19 ms 940 KB
01_rand_06.txt AC 20 ms 916 KB
01_rand_07.txt AC 21 ms 920 KB
01_rand_08.txt AC 20 ms 928 KB
01_rand_09.txt AC 20 ms 912 KB
01_rand_10.txt AC 19 ms 916 KB
01_rand_11.txt AC 20 ms 1052 KB
01_rand_12.txt AC 19 ms 928 KB
01_rand_13.txt AC 20 ms 1048 KB
01_rand_14.txt AC 19 ms 952 KB
01_rand_15.txt AC 20 ms 920 KB
01_rand_16.txt AC 21 ms 924 KB
01_rand_17.txt AC 19 ms 972 KB
01_rand_18.txt AC 20 ms 916 KB
01_rand_19.txt AC 21 ms 920 KB
02_maxrand_00.txt AC 20 ms 1052 KB
02_maxrand_01.txt AC 20 ms 1052 KB
02_maxrand_02.txt AC 20 ms 1052 KB
02_maxrand_03.txt AC 21 ms 928 KB
02_maxrand_04.txt AC 21 ms 1048 KB
02_maxrand_05.txt AC 21 ms 1048 KB
02_maxrand_06.txt AC 19 ms 1044 KB
02_maxrand_07.txt AC 20 ms 1044 KB
02_maxrand_08.txt AC 21 ms 920 KB
02_maxrand_09.txt AC 20 ms 1052 KB
02_maxrand_10.txt AC 21 ms 920 KB
02_maxrand_11.txt AC 20 ms 928 KB
02_maxrand_12.txt AC 21 ms 1048 KB
02_maxrand_13.txt AC 21 ms 1052 KB
02_maxrand_14.txt AC 21 ms 1052 KB
02_maxrand_15.txt AC 20 ms 1052 KB
02_maxrand_16.txt AC 21 ms 1048 KB
02_maxrand_17.txt AC 21 ms 1048 KB
02_maxrand_18.txt AC 21 ms 1052 KB
02_maxrand_19.txt AC 21 ms 928 KB
03_max.txt AC 21 ms 1048 KB
03_maxret.txt AC 18 ms 1052 KB
03_min.txt AC 19 ms 1048 KB
03_special_01.txt AC 20 ms 1040 KB
03_special_02.txt AC 19 ms 1044 KB
03_special_03.txt AC 19 ms 928 KB
03_special_04.txt AC 21 ms 1040 KB
04_special_05.txt AC 20 ms 1036 KB