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

問題

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

方針

• 隣接行列を用いたダイクストラ法はグラフG=(V, E)においてとなる.
• 今回はノード数がであるので, 隣接リストを使った実装を行う.
• 隣接リストでグラフを表現し, 二分ヒープ(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) 参加レポート

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

開演前

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

【LLR8リポート7】
名古屋公演1日目🐓Zepp Nagoyaでは2015年7月以来のライブです！今日は最高気温30℃らしいですが🌞こっちはもっともっと熱気で凄いライブにしましょうね🔥よろしくお願いいたします！
会場に着くとウェルカムボードが✨ただいまー！！🏃💨 by.スタッフ pic.twitter.com/W6LcSPB0y7

— aiko official (@aiko_dochibi) 2017年5月20日

LLR8zepp名古屋。全国で夏日に☀️今日から2日間よろしくお願いします♪(๑ᴖ◡ᴖ๑)♪ pic.twitter.com/5zBVVqJado

— 佐藤達哉 (@satotatsua) 2017年5月20日

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

開場

画像は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福井公演を思い出した.

コールアンドレスポンス

「男子」「女子」「そうでない人」「メガネ」「コンタクト」「裸眼」「小鉢」「お茶碗（不確か）」「どんぶり」「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人体制でしたね. 初めて見ました.
　連番していただいた方もとても良い方で, 非常に良いライブの思い出ができました. ありがとうございます.
　ただ, 階段上がってすぐに分煙されてない状態の喫煙所があるのはちょっとどうかと思いました. あれはいただけないですね.

関係者ツイートなど

名古屋ライブ1日目終わりましたー！
終わった後、素の顔しか出来ひんくらいに色々出ました笑
皆さん最後まで本当に本当にありがとうございました！！ pic.twitter.com/IBknpwsS4z

— aiko official (@aiko_dochibi) 2017年5月20日

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

Yu Sutoさん(@u_suto_)がシェアした投稿 - 2017 5月 21 6:19午後 PDT

名古屋2日間。会場も真夏日で興奮しました☀️打ち上げの鯛めしも激アツでかき氷🍧はキンキンでした💦最高の夜をありがとうございました😊 pic.twitter.com/AI9pMP1oIV

— 佐藤達哉 (@satotatsua) 2017年5月22日

aikoさん Live Tour
「Love Like Rock vol.8」
Zepp名古屋公演でした！！！
2日間の激アツライブ最高でした！！！
ありがとうございましたm(__)m pic.twitter.com/pZg7YvEICH

— 芳賀義彦 (@yoyoyotie) 2017年5月21日

【AOJ 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つ足りなくて小一時間悩むというミスをした. 元気なときにやらないとダメだね.

【AOJ 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";
}

【AOJ 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";
  }
}

【AOJ ALDS1_8】C: Binary search trees - Binary Search Tree III

問題

二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

• 二分探索木の削除を実装する問題
• 削除するノードを以下の3つの条件で場合分けし処理を行う.
  1. 子ノードを持たない
  2. 子ノードを1つだけ持つ
  3. 子ノードを2つ持つ
• 1, 2の場合は対象ノードを取り除くだけで良い.（取り除いてその子ノードを親ノードに繋げば良い）
• 3の場合は, 右部分木の最小ノードを削除したいノードに置き換える.

コード

#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++)

using namespace std;

struct Node{
  int data;
  Node *parent, *left, *right;
};

Node *root;

Node* findNode(int x){
  Node *r = root;
  while(r != NULL && r->data != x){
    if(x < r->data){
      r = r->left;
    }else{
      r = r->right;
    }    
  }
  return r;
}

Node* getMinNode(Node *u){
  while(u->left != NULL) u = u->left;
  return u;
}

Node* getSuccessor(Node *u){
  if(u->right != NULL) return getMinNode(u->right);
  Node *p = u->parent;
  while(p != NULL && p->right == u){
    u = p;
    p = p->parent;
  }
  return p;
}

void deleteNode(Node *u){
  Node *target;
  Node *child;

  // 削除対象ノードを決める
  // 子ノードが無い or 1個だけの場合, 削除対象ノードはuそのもの
  // 子が２つある場合, uの次接点となる.
  if(u->left == NULL || u->right == NULL){ // 子ノードがない or 1個
    target = u;
  }else{
    target = getSuccessor(u);
  }
  
  // 削除対象ノードの子ノードを求める
  if(target->left != NULL){
    child = target->left;
  }else{
    child = target->right;
  }

  // 子ノードがある場合, 子ノードの親ノードを削除対象ノードの親ノードにする
  if(child != NULL){
    child->parent = target->parent;
  }

  // 左 or 右のノードに子ノードを格納
  if(target->parent == NULL){
    root = child;    
  }else{
    if(target == target->parent->left){
      target->parent->left = child;
    }else{
      target->parent->right = child;
    }
  }
  
  // 削除対象が異なる場合はdataを入れ替え
  if(target != u) u->data = target->data;
  free(target);  
}

void insertNode(int x){
  Node *root_tmp = root;
  Node *elem;

  elem = (Node *)malloc(sizeof(Node));
  elem->data = x;
  elem->left = NULL;
  elem->right = NULL;
  
  Node *prev = NULL;

  while(root_tmp != NULL){
    prev = root_tmp;
    if(elem->data < root_tmp->data){
      root_tmp = root_tmp->left;
    }else{
      root_tmp = root_tmp->right;
    }
  }

  elem->parent = prev;

  if(elem->parent == NULL){
    root = elem;
  }else{
    if(elem->parent->data < elem->data){
      elem->parent->right = elem;
    }else{
      elem->parent->left = elem;
    }
  }
}

// 先行巡回
void preorder(Node *u){
  if(u == NULL) return; 
  cout << " " << u->data;
  preorder(u->left);
  preorder(u->right);
}

// 中間巡回
void inorder(Node *u){
  if(u == NULL) return; 
  inorder(u->left);
  cout << " " << u->data;
  inorder(u->right);
}

signed main(){
  int n;
  string command;
  int elem;

  cin >> n;
  rep(i, n){
    cin >> command;
    if(command == "insert"){
      cin >> elem;
      insertNode(elem);
    }else if(command == "find"){
      cin >> elem;
      if(findNode(elem)!=NULL) cout << "yes" << endl;
      else cout << "no" << endl;
    }else if(command == "delete"){
      cin >> elem;
      deleteNode(findNode(elem));
    }else{
      inorder(root);
      cout << "\n";
      preorder(root);
      cout << "\n";
    }
  }
}

参考

PDFです.
http://f-server.ics.kagoshima-u.ac.jp/~fuchida/algorithm/alg10-二分探索木.pdf