2017-04-11

【AOJ 2014】Surrounding Area

AOJ

問題

方針

白い杭から探索した場合には黒い杭, 黒い杭から探索した場合は白い杭に当たるまでひたすら探索
黒だけで塗りつぶされた場所と白だけで塗りつぶされた場所を数える.

コード

#include <iostream>
#include <utility>

using namespace std;

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

int w, h;
bool black[51][51];
bool white[51][51];
string field[51];

int dx[] = {1, 0, -1,  0};
int dy[] = {0, 1,  0, -1};

void solve(int x, int y, char c){
  
  if((c == 'B' && black[y][x]) || (c == 'W' && white[y][x])) return;

  if(c == 'W' && field[y][x]!='W') white[y][x] = true;
  else if(c == 'B' && field[y][x]!='B') black[y][x] = true;
  
  rep(i, 4){
    int nx = x + dx[i]; int ny = y + dy[i];    
    if(0 <= nx && nx < w && 0 <= ny && ny < h && field[ny][nx] == '.'){
      solve(nx, ny, c);
    }
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(cin >> w >> h, w || h){

    rep(i, h){
      cin >> field[i];
    }

    fill(black[0], black[50], false);
    fill(white[0], white[50], false);

    rep(i, h){
      rep(j, w){
    if(field[i][j] == 'W') {
      solve(j, i, 'W');
    }else if(field[i][j] == 'B'){
      solve(j, i, 'B');
    }
      }
    }
    
    int bl, wh;
    bl = wh = 0;

    rep(i, h){
      rep(j, w){
    if(black[i][j] && !white[i][j]) bl++;
    else if(!black[i][j] && white[i][j]) wh++;
      }
    }
  
    cout << bl << " " << wh << endl;
  }
  
}

ソースコードめちゃくちゃ汚い気がする…

2017-04-10

CLionでOpenCVを使えるようにした話

OpenCV プログラミング JetBrains

タイトルの通り, OpenCVをCLionで使えるように設定した.
CLionというのはJetBrains社が作っているC/C++のIDE. IntelliJ IDEAやPyCharm, Ruby Mineと同じ会社である.

www.jetbrains.com

設定環境

Windows7 Professional
OpenCV 3.2.0
MinGW(https://mingw-w64.org/doku.php/start)
CMake 3.8.0-rc4
CLion 2017.1

OpenCVのビルド

まずはじめにOpenCVのビルドを行う.

OpenCVのダウンロード

OpenCVをダウンロードしてくる.

sourceforge.net

任意の場所に展開し, CMakeでビルドする.

CMakeを使ってビルド

"Where is the source code"には先程展開したディレクトリの中のsourceディレクトリを, "Where to build the binaries"には出力先ディレクトリを書く. 今回はmingwとした. 選択が終わったあとはConfigureを押す.
f:id:bath_poo:20190324163752p:plain ここではMinGW Makefilesを選択する.　　 f:id:bath_poo:20170410174130p:plain
下記のように真っ赤な画面がでてくるので, Configureを押して白くなるのを待つ.
f:id:bath_poo:20190324163824p:plain 正常に終わると以下のようになる.
f:id:bath_poo:20190324163855p:plain そしてGenerateを押してビルドを行う.

makeを使ってビルド

コマンドプロンプトを開いてCMakeでビルドした先へ移動する.

$ mingw32-make

これが終わったら

$ mingw32-make install

とすることで完了する. このときにエラーがでてmingw23-makeが終わらず大変苦しむ. エラーで検索したら以下のstackoverflowを発見（これに頼るのはいけない気もするが…） stackoverflow.com こいつのとおりに直して無事にインストール完了した.

CLionの設定

CMakeList.txtに以下の内容を追記する.

find_package( OpenCV REQUIRED )
include_directories( ${OpenCV_INCLUDE_DIRS} )
target_link_libraries( "プロジェクト名" ${OpenCV_LIBS} )

そしてプロジェクトセッティング（今回のプロジェクト名はopencv_testとした）を開き, Executableをプロジェクト名にしてOKし実行.
f:id:bath_poo:20170410181046p:plain 今回使ったソースコードはおなじみ"lena"を表示するプログラム.

#include <opencv2/opencv.hpp>

int main() {
    cv::Mat image;

    image = cv::imread("lena.png", 1);
    if(!image.data){
        printf("No image data\n");
        return -1;
    }
    
    cvNamedWindow("Display Image", CV_WINDOW_AUTOSIZE);
    cv::imshow("Display Image", image);
    cvWaitKey(0);

    return 0;
}

以下のように画像が出力されたら成功. f:id:bath_poo:20170410181245p:plain

参考

inside-my-box.hatenablog.com

追記(2017/11/07)

先日ビルドしたらこのようなエラーが出た.

$ .... windres.exe: invalid option -- W

CmakeでGenerateするときに, ENABLE_PRECOMPILED_HEADERSのチェックを外すとうまくいくらしい.

2017-04-10

【AOJ 2013】Osaki

AOJ

問題

Osaki | Aizu Online Judge

方針

与えられた時刻はすべて秒に変換する.
pair<int, int>のfirstを時間, secondを出発するときは1, 到着したときは-1として保持
時刻順にソートする.
0～vec.size()まで調べ, 出発したときはカウンタを1, 到着したときは-1していきその最大値が答えになる.

コード

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
 
bool flag[90000];
 
typedef pair<int, int> P;
 
signed main(){ 
  int n;
  int h, m, s;
 
  while(scanf("%d", &n), n){
    fill(flag, flag+90000, false);
    vector<pair<int, int> > time;    
    rep(i, n){
      scanf("%d:%d:%d", &h, &m, &s);
      int start = h * 3600 + m * 60 + s;
      time.pb(P(start, 1));
      scanf("%d:%d:%d", &h, &m, &s);
      int end = h * 3600 + m * 60 + s;
      time.pb(P(end, -1));
    }
     
    sort(time.begin(), time.end());
 
    int cnt = 0;
    int _max = 0;
    rep(i, time.size()){
      if(time[i].second == 1){
        cnt++;
      }else{
        cnt--;
      }
      _max = max(cnt, _max);
    }
 
    cout << _max << endl;
  }
   
  return 0;
}

あとから調べてみたら「いもす法」というらしい（無知）

rep(i, time.size()){
  if(time[i].second == 1){
    cnt++;
  }else{
    cnt--;
  }
  _max = max(cnt, _max);
}

の部分は

rep(i, time.size()){
  cnt += time[i].second;
  _max = max(cnt, _max);
}

でいいというのは書き終わってから他のコードを見ることでわかった.

参考

https://imoz.jp/algorithms/imos_method.html

2017-04-09

【AOJ 1148】Analyzing Login/Logout Records

AOJ

問題

Analyzing Login/Logout Records | Aizu Online Judge

方針

PCの番号nと生徒の番号mをキーとしたmapを使って計算する.
ログには必ずログインとログアウトの記録が存在し, 時刻昇順で入力がされることからk番目をstart, k+1番目をend(ただしkは偶数)としてPC使用時間をboolの配列で管理した.
最後にしゃくとりで答えを求める.

ソース

#include <iostream>
#include <utility>
#include <map>
#include <vector>
 
using namespace std;
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
 
typedef pair<int, int> P;
 
signed main(){
  int N,M;
  int r, q;
  cin.tie(0);
  ios::sync_with_stdio(false);
   
  while(cin >> N >> M, N || M){
    cin >> r;
    int t, n, m, s;
    map<P, vector<P> > data;

    rep(i, r){
      cin >> t >> n >> m >> s;      
      data[P(n,m)].pb(P(t, s));
    }
    cin >> q;
    rep(i, q){
      int ts, te, qm;
      cin >> ts >> te >> qm;
      bool flag[1261]; 
      fill(flag, flag+1260, false);
       
      REP(j, 1, N+1){
        for(int k = 0 ; k < (int)data[P(j, qm)].size() ; k+=2){
          int start = max(data[P(j, qm)][k].first, ts);
          int end = min(data[P(j, qm)][k+1].first, te);
          REP(l, start, end+1){
            flag[l] = true;
          }
        }
      }
 
      int ans = 0;
      REP(j, ts, te){
        if(flag[j]){
          int start = j;
          while(flag[j]) j++;     
          ans+=(j-start-1);
        }
      }
 
      cout << ans << endl;
    }
  }
}

2017-04-06

【AOJ 1154】Monday-Saturday Prime Factors

AOJ

問題

Monday-Saturday Prime Factors | Aizu Online Judge

方針

月曜土曜数 a が月曜土曜数 b の月曜土曜約数であるための必要十分条件は, a が b の普通の意味の約数であること.
「エラトステネスの篩」の要領で月曜土曜素数を生成して試す.
出力のフォーマットミスに気づかず, プレゼンテーションエラーしまくった.

ソース

#include <iostream>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

bool prime[300001];

signed main(){
  int n;
  
  vector<int> nums;
  
  fill(prime, prime+300000, true);
  
  for(int i = 2 ; i <= sqrt(300000) ; i++){
    if((i%7 == 1 || i%7 == 6) && prime[i]){
      for(int j = i * 2 ; j <= 300000 ; j+=i){
        prime[j] = false;
      }
    }
  }
  
  for(int i = 2 ; i < 300000 ; i++){
    if(prime[i] && (i%7==1 || i%7 == 6)) {
      nums.push_back(i);
    }
  }

  while(cin >> n, n!=1){
    cout << n << ": ";
    vector<int> ans;
    for(int i = 0 ; i < (int)nums.size() && nums[i] <= n ; i++){
      if(n % nums[i] == 0){
        ans.push_back(nums[i]);
      }
    }

    for(int i = 0 ; i < (int)ans.size() - 1 ; i++){
      cout << ans[i] << " ";
    }
    cout << ans[(int)ans.size()-1] << endl;
  }
  
}

2017-04-06

【AOJ 1166】Amazing Maze

AOJ

問題

Amazing Mazes | Aizu Online Judge

方針

入力フォーマットが特殊な問題. （ここを理解するのに時間を取られる）
与えられた入力からフィールドを生成して, それに対してBFSする.
BFSはいいとしてフィールドの生成めちゃくちゃ手こずった. kyuridenamidaさんのコードをパク参考にさせてもらいました.

ソース

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int dx[] = {1, 0, -1,  0};
int dy[] = {0, 1,  0, -1};
int w, h;
int maze[200][200];
int d[200][200];

#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)
#define INF 1000000000

typedef pair<int ,int> P;

void init(int w, int h){
  rep(i, 200){
    rep(j, 200){
      maze[i][j] = 1;
    }
  }

  REP(i, 1, 2*h){
    REP(j, 1, 2*w){
      maze[i][j] = 0;
    }
  }
}

signed main(){

  cin.tie(0);
  ios::sync_with_stdio(false);
  
  while(cin >> w >> h, w || h){
    init(w, h);
    
    int in;
    rep(i, 2*h-1){
      if(i%2 == 0){ // 縦
        rep(j, w-1){
          cin >> in;
          rep(k, 3){
            maze[i+k][2*j+2] |= in;
          }
        }
      }else{ // 横
        rep(j, w){
          cin >> in;
          rep(k, 3){
            maze[i+1][j*2+k] |= in;
          }
        }
      }      
    }
    
    queue<P> que;
    que.push(P(1, 1));

    rep(i, 200){
      rep(j, 200){
        d[i][j] = INF;
      }
    }

    d[1][1] = 1; 
    int ans = 0;
    while(!que.empty()){
      P p = que.front(); que.pop();

      if(p.first == 2*h-1 && p.second == 2*w-1){
        ans = (d[p.first][p.second]+2)/2; 
        break;
      } 

      rep(i, 4){
        int nx = p.first + dx[i]; int ny = p.second + dy[i];

        if(maze[nx][ny] == 0 && d[nx][ny] == INF){
          que.push(P(nx, ny));
          d[nx][ny] = d[p.first][p.second] + 1;
        }
      }
    }
    cout << ans << endl;
  }
}

参考

kyuridenamida.hatenablog.com

思いついても上手いこと実装できなかったので, 練習の足りなさを感じる. がんばろう.

2017-04-02

【AOJ 2155】Infected Computer

AOJ

問題

Infected Computer | Aizu Online Judge

方針

与えられたデータをtで昇順ソートする.
あとはdとsの値を見てフラグにチェックをいれていき, カウントする.

コード

#include <iostream>
#include <algorithm>

using namespace std;

#define LOG_MAX 20000
#define N_MAX 20000
struct LOG {
  int s, t, d;

  bool operator < (const LOG& another) const {
    return t < another.t;
  }
};

LOG l[LOG_MAX+1];
int n, m;

signed main(){
  while(cin >> n >> m, n||m){
    bool infected[N_MAX+1];

    for(int i = 0 ; i < m ; i++){
      cin >> l[i].t >> l[i].s >> l[i].d;
    }

    sort(l, l+m);

    for(int i = 0 ; i <= n ; i++) infected[i] = false;
    infected[1] = true;

    for(int i = 0 ; i < m ; i++) infected[l[i].d] |= infected[l[i].s];
    
    int ans = 0;
    for(int i = 1 ; i <= n ; i++) if(infected[i]) ans++;

    cout << ans << endl;
  }
}

日々精進

aikoと旅行とプログラミング