プログラミング備忘録

日頃のプログラミングの成果をここに書いていきます．

1. 温度センサの導入 『Raspberry PIで身の回りのいろいろを制御しよう 』

電子工作

はじめに

家の色々な特徴をデータに落とし込んでそれに制御できたらよくない？

と友達に声かけられたのがきっかけで，これからいろんなセンサを使った制御を行っていこうと思います。

さまざまなセンサのことを知れるいい機会ですし，あとはこれに乗っかってRaspberry PIの勉強もできたらいいなあと思っています。最初は温度センサを使った制御を行いたいと思います。とりあえず，今の現状としてはRaspberry PIに温度を取り込んだところまでです。

やるんだという意気込み？的な感じの薄い記事ですがここで終わっておきます。

1. 温度センサの導入 『Raspberry PIで身の回りのいろいろを制御しよう 』

電子工作

はじめに

家の色々な特徴をデータに落とし込んでそれに制御できたらよくない？

と友達に声かけられたのがきっかけで，これからいろんなセンサを使った制御を行っていこうと思います。

さまざまなセンサのことを知れるいい機会ですし，あとはこれに乗っかってRaspberry PIの勉強もできたらいいなあと思っています。最初は温度センサを使った制御を行いたいと思います。とりあえず，今の現状としてはRaspberry PIに温度を取り込んだところまでです。

やるんだという意気込み？的な感じの薄い記事ですがここで終わっておきます（記事書くのってすごくめんどくさいんですw）。

D - Checker 〜ABC086〜

競技プログラミング

問題

D - Checker

感想

これがコンテストに出てたら、時間以内に解けなかった気がする。というか、二次元累積和とかいろいろ省略するためにまとめてライブラリ作っておこうかな。

考え

まず、x, yの上限から、x, yについて全探索するのは得策ではないと考える。

そこでx, yに関してKの剰余を考えることで109→103まで落とし込むことができる。

(0, 0)〜(K - 1, K - 1)の正方形を考えて、(x, y)のKの剰余をそれぞれ(p, q)とすると、以下の関係が成り立っている。

  • x / K % 2 == y / K % 2ならば、(x, y)でのB or Wは(p, q)でのB or Wと同じ
  • 2での剰余が一致しないときはB or Wが反転する

これで、(x, y)のB or Wパターンを103まで落とし込むことができました。

最後はこの(0, 0)〜(K - 1, K - 1)の正方形に対して、二次元累積和を求めて最後に模様のパターンを103 * 103 * 2だけ全探索して最大値を求めればACとなります。

Accepted Program

#include <iostream>
using namespace std;
#define ll long long

int main () {
  int N, K;
  cin >> N >> K;
  static int white[1000][1000] = {};
  static int black[1000][1000] = {};
  ll x, y;
  char c;     
  for (ll i = 0; i < N; i++) {
    cin >> x >> y >> c;
    if ((x / K) % 2 == (y / K) % 2) {
      if (c == 'W') {
        white[y % K][x % K]++;  
      }         
      else {
        black[y % K][x % K]++;  
      }
    }
    else {
      if (c == 'W') {
        black[y % K][x % K]++;  
      }  
      else {
        white[y % K][x % K]++;  
      }
    }
  }

  // 二次元累積和だと.....?
  int sum_white[1000][1000] = {};
  int sum_black[1000][1000] = {};
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < K; j++) {
      if (i == 0) {
        if (i == 0 && j == 0) {
          sum_white[i][j] = white[i][j];
          sum_black[i][j] = black[i][j];  
        }  
        else {
          sum_white[i][j] = white[i][j] + sum_white[i][j - 1];  
          sum_black[i][j] = black[i][j] + sum_black[i][j - 1];  
        }
      }
      else {
        if (j == 0) {
          sum_white[i][j] = sum_white[i - 1][j] + white[i][j];
          sum_black[i][j] = black[i][j] + sum_black[i - 1][j];  
        }  
        else {
          sum_white[i][j] = sum_white[i - 1][j] + white[i][j] + sum_white[i][j - 1]
                          - sum_white[i - 1][j - 1];  
          sum_black[i][j] = sum_black[i - 1][j] + black[i][j] + sum_black[i][j - 1]
                          - sum_black[i - 1][j - 1];
        }
      }
    }  
  }
  ll ans = 0;
  for (ll i = 0; i < K; i++) {
    for (ll j = 0; j < K; j++) {
      ll sub = sum_white[i][j] + (sum_black[i][K - 1] - sum_black[i][j]);
      sub = sub + (sum_black[K - 1][j] - sum_black[i][j]);
      sub = sub + (sum_white[K - 1][K - 1] - sum_white[K - 1][j] - sum_white[i][K - 1]);
      sub = sub + sum_white[i][j];
      if (ans < sub) {
        ans = sub;  
      }  
    }  
  }
  for (ll i = 0; i < K; i++) {
    for (ll j = 0; j < K; j++) {
      ll sub = sum_black[i][j] + (sum_white[i][K - 1] - sum_white[i][j]);
      sub = sub + (sum_white[K - 1][j] - sum_white[i][j]);
      sub = sub + (sum_black[K - 1][K - 1] - sum_black[K - 1][j] - sum_black[i][K - 1]);
      sub = sub + sum_black[i][j];
      if (ans < sub) {
        ans = sub;  
      }  
    }  
  }
  cout << ans << endl;
}

D - Practical Skill Test

競技プログラミング

問題

D - Practical Skill Test

感想

D解けた（小並感）

考え

Dの剰余で整理することが大事です。Dの剰余について、各移動をしていき、ans[D]に移動した時に使った値を追加していく。

Accepted Program

#include <iostream>
#include <string.h>
#include <set>
#include <vector>
#include <map>
#include <math.h>

using namespace std;
// #define ll long long
typedef long long ll;

int main () {
  ll  H, W, D;
  cin >> H >> W >> D;
  ll A[H][W];
  map <ll, ll> x;
  map <ll, ll> y;
  for (ll i = 0; i < H; i++) {
    for (ll j = 0; j < W; j++) {
      cin >> A[i][j];
      x[A[i][j]] = i;
      y[A[i][j]] = j;  
    }  
  }  
  ll Q;
  cin >> Q;
  ll L[Q], R[Q];
  
  // ここでDの剰余を計算しておく
  set<ll> mod;
  for (ll i = 0; i < Q; i++) {
    cin >> L[i] >> R[i];
    mod.insert(L[i] % D);  
  }
  vector<vector<ll> > ans;
  ans.resize(D);
  for (auto d : mod) {
    // dについて記入していく
    ll start = (ll) d;
    // ans[start]
    ans[start].push_back(0);
    ll end = start;
    while (end <= H * W) {
      ll before = end;
      end = end + D;
      if (end > H * W) {
        break;  
      }
      ll before_i = x[before];
      ll before_j = y[before];
      ll end_i = x[end];
      ll end_j = y[end];
      ll sub = ans[start][ans[start].size() - 1];
      ans[start].push_back(sub + abs(end_i - before_i) + abs(end_j - before_j));
    } 
  }
  for (ll i = 0; i < Q; i++) {
    ll sub = L[i] % D;
    R[i] = (R[i] - sub)/D;
    L[i] = (L[i] -sub )/D;
    cout << ans[sub][R[i]] - 
            ans[sub][L[i]] << endl;    
  }
  
}

Marked Ancestor

競技プログラミング

問題

Marked Ancestor | Aizu Online Judge

感想

最初は、Disjoint Set（Union-Find木）を使う意味がわからなかった。 単純にクエリごとに親をたどっていきばいいのでは、と思っていました。（愚直解） しかし、愚直解では、根を調べた後にパスを短縮化することができないんですね。これが原因でTLEになります.....いやならないらしいw。

まあ愚直解だと勉強にならないので、ここではUnion-Find木を使って解いてみました。 計算量について、まだまだ考察が甘いなと反省した問題でした。楽しい。

考え

  • クエリの後ろから実行する。Mはここでは、Union-Find木でいうuniteに相当する。
  • 同じindexへのMは無視する（Aと変換した）
  • クエリの最初から実行する時は、クエリとそのindexを保存するとともに、Mであった場合にその親が自分自身であると設定することも忘れない（PPに対応する）

Accepted Program

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define ll long long 

int m[100001];
int P[100001];
int PP[100001];

// initialize
void init (ll n) {
  // P[i] means the parent of 'i'.
  for (ll i = 0; i <= n; i++) {
    P[i] = i;  
    PP[i] = i;  
    m[i] = 0;
  }    
  m[1] = 1;
}
// check the root of 'x'
int root (ll x) {
  if (P[x] == x) {
    return x;  
  }  
  else {
    // cut the path length
    return (P[x] = root (P[x]));  
  }
}
// unite both root of 'x' and 'y'
void unite (ll x, ll y) {
  P[root(x)] = root(y);    
}

int main () {
  ll n, q;
  while (cin >> n >> q && n != 0 && q != 0) {
    init(n);
    long long ans = 0;
    ll sub;
    char subsub;
    for (ll i = 2; i <= n; i++) {
      cin >> sub;
      P[i] = sub;  
      PP[i] = sub;  
    }
    vector<char> ss;
    vector<ll> s;
    for (ll i = 0; i < q; i++) {
      cin >> subsub >> sub;
      ss.push_back(subsub);
      s.push_back(sub);
      if (subsub == 'M') {
        if (m[sub] == 1) {
          ss[i] = 'A';
        }
        else {
          m[sub] = 1; 
          P[sub] = sub;  
        }
      }    
    }
    for (ll i = 0; i < q; i++) {
      subsub = ss[q - 1 - i];
      sub    = s[q - 1 - i];
      if (subsub == 'M') {
        m[sub] = 0;
        P[sub] = PP[sub];
        unite(sub, P[sub]);    
      }    
      if (subsub == 'Q') {
        ans = ans + root(sub);
      }
    }
    cout << ans << endl;
  }
}

Set - Disjoint Set: Union Find Tree

競技プログラミング

問題

Disjoint Set: Union Find Tree | Aizu Online Judge

感想と雑多なこと

かなり更新遅くなりました... いろいろと重なっていて忙しかったり、AtCoderのD問題が解けなくて記事にできなかったりと、ここ一週間くらい自分の思うように実装できなかったですね。

現状、C問題は普通に解けるのですが、D問題が全く解けない状態です。おそらく知識が足りないのだと思います。どこかで蟻本に手を出そうかなあと思っていたのですが、その時期が近づいているなという感覚です。

今回選んだ問題は、単純に自分が知らなかった&実装経験が少ない、グラフ構造（木）に関する問題です。

考え

P[i]をiの親要素であると定義し、あとは木での知識を用いれば良い。

Accepted Program

#include <iostream>
using namespace std;

int P[10001];

// initialize
void init (int n) {
  // P[i] means the parent of 'i'.
  for (int i = 0; i <= n; i++) {
    P[i] = i;  
  }    
}
// check the root of 'x'
int root (int x) {
  if (P[x] == x) {
    return x;  
  }  
  else {
    return root (P[x]);  
  }
}
// unite both root of 'x' and 'y'
void unite (int x, int y) {
  P[root(x)] = root(y);    
}
int sames (int x, int y) {
  if (root(x) == root(y)) {
    return 1;  
  }  
  else {
    return 0;  
  }
}

int main () {
  int n, m;
  cin >> n >> m;
  init(n);
  for (int i = 0; i < m; i++) {
    int c, x, y;
    cin >> c >> x >> y;
    if (c == 1) {
      cout << sames(x, y) << endl;  
    }       
    else {
      unite(x, y);  
    }
  }
}

〜九州大学プログラミングコンテスト2018〜 C - Ito Campus

競技プログラミング

問題

C - Ito Campus

感想

はじめてBPS（幅優先探索）を実装してみた。 割とTLEになる条件が厳しかったので厳格に実装する必要があるんだなあと思いました。 BPSの中で、四方へ進む際に一回一回その方向でいいのか考える必要がない（つまり、その四方へ進む方向が最短経路となっている）ということはすごいと思いました（コードでいうとdp[pi + vi[i]][qi + vj[i]] = dp[pi][qi] + 1;に対応しています）。

考え

以下の2回に分けて、BPSを使います。

  1. イノシシのいる位置からStartして、新しい#の範囲を作っていく
  2. SからBPSしてGまでたどっていく

Accepted Program

可読性がない...

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long

ll abs (ll x, ll y) {
  if (x - y) {
    return x - y;  
  }  
  return y - x;
}

int main () {
  ll h, w, x;
  cin >> h >> w >> x;
  char s[h][w];
  ll dp[h][w];
  ll xa[h][w];
  vector<int> ii;
  vector<int> jj;
  int si = 0;
  int sj = 0;
  for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      s[i][j] = -1;
      dp[i][j] = -1;
      xa[i][j] = -1;
      cin >> s[i][j];
      if (s[i][j] == '@') {
        ii.push_back(i);
        jj.push_back(j);
        xa[i][j] = x;  
      }  
      if (s[i][j] == 'S') {
        si = i;
        sj = j;  
      }
    }  
  }
  ll vi[4] = {0, 0, 1, -1};
  ll vj[4] = {1, -1, 0, 0};
  for (ll i = 0; i < ii.size(); i++) {
    queue<ll> li;
    queue<ll> lj;
    li.push(ii[i]);
    lj.push(jj[i]);
    while (!li.empty()) {
      ll xi, xj;
      xi = li.front();
      xj = lj.front();
      li.pop();
      lj.pop();
      
      for (int a = 0; a < 4; a++) {
          
        if (xi + vi[a] > 0 && xi + vi[a] < h && xj + vj[a] > 0 && xj + vj[a] < w) {
          if (s[xi + vi[a]][xj + vj[a]] == '@') {
            // 何もしない.  
          }
          if (s[xi + vi[a]][xj + vj[a]] == '#') {
            // 同上  
          }
          if (s[xi + vi[a]][xj + vj[a]] == '.'
            ||s[xi + vi[a]][xj + vj[a]] == 'G'
            ||s[xi + vi[a]][xj + vj[a]] == 'S')
          {
            ll sub = xa[xi][xj] - 1;
            if (xa[xi + vi[a]][xj + vj[a]] < 0) {
              xa[xi + vi[a]][xj + vj[a]] = xa[xi][xj] - 1;
              if (sub > 0) {
                li.push(xi + vi[a]);
                lj.push(xj + vj[a]);
              }
            }
          }
        }    
      }  
    }
  }
  // まさかのここも探索だったとは.....

  
  ll gi, gj;
  gi = 0;
  gj = 0;
  bool ok = false;
  for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      if (xa[i][j] >= 0) {
        if (s[i][j] == 'G') {
          cout << -1 << endl;
          return 0;   
        }
        s[i][j] = '#';
      }
      if (s[i][j] == 'G') {
        gi = i;
        gj = j;  
      }
    } 
  }
  // 幅優先探索で求める。
  dp[si][sj] = 0;
  queue<ll> P;
  queue<ll> Q;
  P.push(si);
  Q.push(sj);
  
  while (!P.empty()) {
    ll pi = P.front();
    ll qi = Q.front();

    if (pi == gi && qi == gj) {
      cout << dp[pi][qi] << endl;
      return 0;  
    }
    for (int i = 0; i < 4; i++) {
      if (pi + vi[i] > 0 && pi + vi[i] < h && qi + vj[i] > 0 && qi + vj[i] < w) {
        if (s[pi + vi[i]][qi + vj[i]] != '#' && s[pi + vi[i]][qi+vj[i]] != '@') {
          if (dp[pi + vi[i]][qi + vj[i]] < 0) {        
            P.push(pi + vi[i]);
            Q.push(qi + vj[i]);    
            dp[pi + vi[i]][qi + vj[i]] = dp[pi][qi] + 1;
          }
        }  
      }       
    }
    P.pop();
    Q.pop();
  }
  cout << dp[gi][gj] << endl;
  /*for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      cout << dp[i][j] << " " ;  
    }  
    cout << endl;
  }
  */
}