読者です 読者をやめる 読者になる 読者になる

日々精進

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

【AOJ 2015】Square Route

問題

Square Route | Aizu Online Judge

方針

  • 道と道の間隔が与えられるので, 正方形の区画がいくつあるか数える問題
  • すべてのパターンを試す方法では,  {O(N^2 M^2)}となり終わらない.
  • そこで, 辺の長さの全パターンを予め求め, その出現個数を元に計算する.(この場合は {O(N^2)}となる)
    • 長さが出現する場所, 順序はあまり関係がないため.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define m0(x) memset(x, 0, sizeof(x))

using namespace std;

int x[2000], y[2000];
int count_x[1500001], count_y[1500001];

signed main(){
  int n, m;
  vector<int> w, h;
  while(cin >> n >> m, n||m){
    rep(i, n) cin >> y[i];  
    rep(i, m) cin >> x[i];  
    m0(count_x);
    m0(count_y);
    rep(i, n){
      int sum = 0;
      REP(j, i, n){
        sum += y[j];
        count_y[sum]++; // 長さがsumの個数を数える
      }
    }
    
    rep(i, m){
      int sum = 0;
      REP(j, i, m){
        sum += x[j];
        count_x[sum]++;
      }
    }
    
    int ans = 0;
    rep(i, 1500001){
      ans += count_x[i] * count_y[i]; // 同じ長さの個数の積が答えになる.
    }
    
    cout << ans << endl;
  }
}

参考

Square Route 解説
こちらの図がとてもわかり易い.

【AOJ ALDS1_12】C: Graph Ⅱ - Single Source Shortest Path Ⅱ

問題

最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 隣接行列を用いたダイクストラ法はグラフG=(V, E)において {O(|V|^2)}となる.
  • 今回はノード数が {1 \leq n \leq 10000}であるので, 隣接リストを使った実装を行う.
  • 隣接リストでグラフを表現し, 二分ヒープ(priority_queue)を用いることで飛躍的に高速化することができる.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define mp make_pair
#define INF 1e9
#define MAX 10000

using namespace std;

typedef pair<int, int> pii;

int n;
// pair.first : 距離
// pair.second : 頂点
vector<pii> node[MAX];
bool root[MAX];
int d[MAX];

void dijkstra(){
  priority_queue<pii> pq;  
  rep(i, MAX){
    d[i] = INF;
    root[i] = false;
  }
  
  d[0] = 0;
  pq.push(mp(0, 0));

  while(!pq.empty()){
    pii p = pq.top(); pq.pop();
    int u = p.second;
    
    root[u] = true;
    
    if(d[u] < p.first * -1) continue;
    
    rep(i, node[u].size()){
      int v = node[u][i].first;
      if(root[v]) continue;
      if(d[v] > d[u] + node[u][i].second){
    d[v] = d[u] + node[u][i].second;
    pq.push(mp(d[v] * -1, v));
      }
    }
  }
}

signed main(){
  cin >> n;
  int u, k, v, c;
  rep(i, n){
    cin >> u >> k;
    rep(j, k){
      cin >> v >> c;
      node[u].pb(mp(v, c));
    }
  }

  dijkstra();
    
  rep(i, n){
    cout << i << " " << (d[i] == INF?-1:d[i]) << endl;
  }
}

【AOJ 1136】Polygonal Line Search

問題

Polygonal Line Search | Aizu Online Judge

方針

  • 0番目の入力セットと1〜n番目までのセットを比較して同じ形の折れ線であるか判定する.
  • 同じ折れ線であるかの判定は, 以下のいずれかを満たす.
    1. xy平面内で回転および平行移動によって(拡大縮小や裏返しをせずに)重なり合う
    2. 始点から終点まで の頂点が逆順に指定されている
  • 90度ごとにしか回転しない(1セットについて高々4パターン)ので, 4回転全部試してみる.
  • 比較する際に始点を合わせる(これ合わせなくても行けそうだなと思ったけど頭がなかった)
  • 入力形式ちゃんと読んでなくてバグらせて辛かった(n+1セット分入力があるのをすっかり見落としていた)

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef pair<int, int> pii;

vector<pii> in[50];
int m[50];

bool equal(vector<pii> v1, vector<pii> v2){
  int dx = (v1[0].first - v2[0].first);
  int dy = (v1[0].second - v2[0].second);
  rep(i, v1.size()){
    if(v1[i].first != v2[i].first+dx || v1[i].second != v2[i].second+dy) return false;
  }
  return true;
}

bool solve(int n){
  // 線分の数が異なる時は一致しない
  if(in[0].size() != in[n].size()) return false;  
  rep(i, 2){    // 順方向, 逆方向
    rep(j, 4){ // 4回転
      if(equal(in[0], in[n])) return true;         
      rep(k, m[n]){
        swap(in[n][k].first, in[n][k].second);
        in[n][k].first *= -1;
      }
    }
    reverse(ALL(in[n]));
  }
  return false;
}

signed main(){
  int n;

  int x, y;

  
  while(cin >> n, n){
    
    // 入力
    rep(i, n+1){
      cin >> m[i];
      in[i].clear();
      rep(j, m[i]){
        cin >> x >> y;
        in[i].pb(mp(x, y)); 
      }
    }

    REP(i, 1, n+1){
      if(solve(i)) cout << i << endl;
    }
    cout << "+++++" << endl;
  }
  
}

aiko Live Tour Love Like Rock Vol.8 Zepp Nagoya(5/20) 参加レポート

f:id:bath_poo:20170521005135j:plain 2017/5/20にZepp Nagoyaで行われたaiko LIVE Tour Love Like Rock Vol.8(通称LLR)に参加してきました. 全開のLLP19も書いたので, これからは書いていこうと思います. 以下ネタバレなので注意.

開演前

写真撮ってない. つらいね.

  • この日はめちゃくちゃ暑くて, 最高気温の予報が30℃. 5月だっていうのに暑すぎだろとか思ったけど, 5月ってそんなもんでしたっけ.
  • 連番する方と合流し, 物販列に並ぶ. Zeppの裏側(という表現が正しいかは分からないが)まで列が続いていて, 結局1時間ぐらいかかったような気がする. f:id:bath_poo:20170521092233j:plain この写真だと左側が名駅側です.
  • 今回あまり欲しいと思うグッズがなかったので, トートバッグとタオルを購入. グッズ名が案の定めちゃくちゃ長かった.
    • 犬も入るよ、猫も入るよ、でもラクダは入らないよ。おバッグ
    • スペシャの夏フェス特番とかで首に巻いてる人を見たらめっちゃ嬉しいから巻いてねタオル
  • グッズはこちらから↓ aiko.com

開場

f:id:bath_poo:20170520221416p:plain 画像はhttp://hall.zepp.co.jp/nagoya/floor.htmlより引用しました.

  • 今回は2階スタンディングという後ろの後ろの席でした(一般なのでそれはそう)
  • しかしそこはライブハウス, 一番うしろの席だと言うのによく見えました. 2階指定席って実はめちゃくちゃいい席なのでは?

セットリスト

  1. 彼の落書き
  2. 染まる夢
  3. 赤いランプ
  4. キスが巡る
    まさかキスが巡るが聞けるなんて. ツイてるなあなどと考えていた.
  5. なんて一日
    ライブBDで見てめちゃくちゃ気に入った曲. 結構昔の曲連続したなーと思いつつ、アルバム引っさげじゃないライブの良さだよねと思っていた.
  6. プラマイ
  7. 線香花火
  8. 微熱
    こういうバラードで目を閉じて聞くという贅沢なことをしていた. たまに聞くのに集中するのもいいよね.
  9. それだけ
  10. 密かなさよならの仕方
    シモネタのあとに歌ったのってこれでしたっけ(記憶が曖昧)
  11. 桜の時
  12. 蝶々結び
  13. 小鳥公園
  14. もっと
  15. Loveletter
    このあたりからの盛り上がりはすごかった. やはりLoveletterは盛り上がる.
  16. be master of life
  17. あたしの向こう
アンコール
  1. 4月の雨
  2. 赤い靴
    赤い靴にコールなんてあったっけと思ったが, 最後の「ばいばーい」だった.
  3. ボーイフレンド
ダブルアンコール
  1. 愛の病
    愛の病は早いほうが良いよね.
  2. ジェット
    このアンコール, LLP19福井公演を思い出した.

f:id:bath_poo:20170521091602j:plain

コールアンドレスポンス

「男子」「女子」「そうでない人」「メガネ」「コンタクト」「裸眼」「小鉢」「お茶碗(不確か)」「どんぶり」「PA席」「サイドスタッフ」「照明」「警備のお兄さん」といった感じでした. あとなんか吠えるパートも有りました. それに加えて年齢別(10代, 20代, …) ももちろん有りましたよ.

ライブ中の会話

  • 大阪公演で歯が欠けたらしく, 名古屋に来る前に歯医者によったとのこと
    • 嵐のニノも歯が弱いって話をしていた.
    • マウスピースしてる人を聞いてましたね. レーシックぐらいいた.
  • ヤスケンの歯は全部差し歯
  • こばち姉さん
    • aikoが巨乳でPower of Love歌ってたらそれは違うみたいな話を母親からされた.
    • バーが小鉢を刺激するね
  • マネージャーとご飯食べ行ったら隣の席にいた女の人が男の人に愚痴ってた. (どうも同じ会社の違う部署というつながりらしく, 上司や部下に対する愚痴を言っていたそう)
    • 上司のほうは21:30に酔いつぶれる.
    • 女の人はDragon Ashを聞いて育ったので打たれ強いという持論を展開していた.
      • それに対して男の人が「ZIGGY世代では?」というツッコミ. どっちも同じではないかという議論がZepp Nagoyaでなされた. なんだこれは
  • めっちゃエゴサしてる(アーティストとかめっちゃエゴサしてるからね)
    • 「#aikoスケスケ小鉢」と書いてツイートしたらaikoが見てくれるかもしれないぞ!
    • 普段はInstagramで「#シーズー」というタグを見まくってるらしい.
  • 8歳の女の子に対してシモネタのオンパレード
    • お母様の主張がすごく激しかった.
  • ギターの設楽さんは白湯を飲みまくってるらしい. (お酒とかも飲まないそうです)

まとめ

 自身初のRock参加となりました. 開場どんなもんかなと思いましたが, 2階席からでもaikoをしっかり見ることができ良い会場だなと思いました. 500円はらってドリンクと交換するとか柵があるとか, ライブハウスそのものが初めてだったので少し戸惑いながらも楽しむことができました.  Rockの魅力は何と言っても近さ. 1階席の人たちは本当にaiko近くて羨ましい反面, 自分は1階席で落ち着いて見れるのだろうかとも思いました. 2階席でゆっくり見るのが自分にはあってるのかもしれない.
 あと今回バンドメンバー初回のときの演奏がみんなかっこよかったですねー. 佐野さん本当に手が2本なのかってぐらい激しいドラムでした. 格好良かった!あと今回はキーボードが2人体制でしたね. 初めて見ました.
 連番していただいた方もとても良い方で, 非常に良いライブの思い出ができました. ありがとうございます.
 ただ, 階段上がってすぐに分煙されてない状態の喫煙所があるのはちょっとどうかと思いました. あれはいただけないですね.

関係者ツイートなど

LLR8名古屋二日間お疲れ様でした。帰京してリハーサルに勤しみます

Yu Sutoさん(@u_suto_)がシェアした投稿 -

【ALDS1_9】C: Heaps - Priority Queue

問題

優先度付きキュー | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 優先度付きキューを実装する問題
  • (体がしんどいので元気になったらしっかり書きます許して)

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define MAX 2000000
#define INF (1<<30)
#define left(i) (i * 2);
#define right(i) (i * 2 + 1)

using namespace std;

int h;
int A[MAX+2];

void maxHeapify(int i){
  int r = right(i);
  int l = left(i);
  int _max = i;
  
  if(l <= h && A[l] > A[_max]) _max =l;
  if(r <= h && A[r] > A[_max]) _max = r;

  if(_max != i){
    swap(A[i], A[_max]);
    maxHeapify(_max);
  }
}

int extract(){
  if(h < 1) return -INF;
  int maxv = A[1];
  A[1] = A[h];
  h--;
  maxHeapify(1);
  return maxv;
}

void insert(int x){
  h++;
  A[h] = -INF;
  if(x < A[h]) return;
  
  A[h] = x;
  int i = h;
  while(i > 1 && A[i/2] < A[i]){
    swap(A[i/2], A[i]);
    i /= 2;
  }
  
}

signed main(){
  string command;
  int n;
  h = 0;
  while(true){
    cin >> command;    
    if(command == "end") break;
    if(command == "insert"){
      cin >> n;
      insert(n);
    }else{
      cout << extract() << endl;;
    }
    
  }
}

風邪ひきながらといたので, 定数の0が1つ足りなくて小一時間悩むというミスをした. 元気なときにやらないとダメだね.

【ALDS1_9】B: Heaps - Maximum Heap

問題

ヒープの構築 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 最大ヒープを作る問題
  • 節点のキーが子のキーよりも大きいという条件を満たすものを最大ヒープという.
  • ボトムアップに関数を適用することで最大ヒープに変換する.

コード

#include <iostream>

using namespace std;

#define H_MAX 500000
#define left(i) (i * 2)
#define right(i) (i * 2 + 1)

int h, A[H_MAX+1];

void maxHeapify(int i){
  int r = right(i);
  int l = left(i);
  int _max = i;
  
  if(l <= h && A[l] > A[_max]) _max =l;
  if(r <= h && A[r] > A[_max]) _max = r;

  if(_max != i){
    swap(A[i], A[_max]);
    maxHeapify(_max);
  }
}

int main(){
  cin >> h;
  for(int i = 1 ; i <= h ; i++){
    cin >> A[i];
  }

  for(int i = h/2 ; i >= 1 ; i--){
    maxHeapify(i);
  }

  for(int i = 1 ; i <= h ; i++){
    cout << " " << A[i];
  }

  cout << "\n";
}

【ALDS1_9】A: Heaps - Complete Binary Tree

問題

ヒープ 完全二分木 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 完全二分木とは, すべての葉が同じ深さであり内部節点の次数が2であるような二分木である.
  • 節点番号がiであるとき, 親はi/2, 左の子ノードは2i, 右の子ノードは2i+1で求めることができる.

コード

#include<iostream>

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

using namespace std;

signed main(){
  int h;
  int A[251];
  cin >> h;
  for(int i = 1 ; i <= h ; i++){
    cin >> A[i];
  }

  for(int i = 1 ; i <= h ; i++){
    cout << "node " << i << ": key = " << A[i] << ", ";
    if(i/2 >= 1) cout << "parent key = " << A[i/2] <<  ", ";
    if(2 * i <= h) cout << "left key = " << A[2 * i] << ", ";
    if(2 * i + 1 <= h) cout << "right key = " << A[2 * i + 1] << ", ";
    cout << "\n";
  }
}