【AOJ 2102】Rummy
問題
方針
- 数字と記号のペアが与えられるので, 全通り試してセットであるか試す.
- セットである条件は
- 3枚とも同じ色であること
- 番号がすべて同じか連番になっていること（ただし, 8, 9, 1のような連番は認められない）
- これが3枚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++) #define mp make_pair using namespace std; typedef pair<int, string> pis; int n; pair<int, string> v[9]; int num[9]; string mark[9]; bool check_num(pis a, pis b, pis c){ if(a.first > b.first) swap(a, b); if(a.first > c.first) swap(a, c); if(b.first > c.first) swap(b, c); return (a.first + 1 == b.first && b.first + 1 == c.first) || (a.first == b.first && b.first == c.first); } bool check_mark(pis a, pis b, pis c){ return a.second == b.second && b.second == c.second; } bool check(){ bool ret = true; rep(i, 3){ ret &= (check_num(v[i*3], v[i*3+1], v[i*3+2]) && check_mark(v[i*3], v[i*3+1], v[i*3+2])); } return ret; } signed main(){ bool flag; cin >> n; while(n--){ flag = false; rep(i, 9) cin >> num[i]; rep(i, 9){ cin >> mark[i]; v[i] = mp(num[i], mark[i]); } do{ if(check()){ cout << 1 << endl; flag = true; break; } }while(next_permutation(v, v+9)); if(!flag) cout << 0 << endl; } }
【AOJ ALDS1_13】B: Heuristic Search - 8 Puzzle
問題
| アルゴリズムとデータ構造 | Aizu Online Judge
方針
- DFSをして正しい並びになったかを判定し, その時のターン数を返す.
- 探索した盤面はフラグを立てておき, 同じ状態を２回以上探索しないようにする.
- mapって比較の"<“が定義されてないと使えないのを初めて知った.
コード
#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; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; struct Puzzle{ int field[9]; int space; int turn; bool operator < (const Puzzle& a) const{ rep(i, 9){ if(a.field[i] == field[i]) continue; return field[i] > a.field[i]; } return false; } }; bool check(Puzzle p){ rep(i, 9){ if(p.field[i] != i+1) return false; } return true; } int solve(Puzzle in){ queue<Puzzle> q; map<Puzzle, bool> mp; q.push(in); mp[in] = true; // bfs while(!q.empty()){ Puzzle p = q.front(); q.pop(); if(check(p)) return p.turn; int x = p.space % 3; int y = p.space / 3; rep(i, 4){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx < 0 || 2 < nx || ny < 0 || 2 < ny) continue; Puzzle tmp = p; swap(tmp.field[p.space], tmp.field[3 * ny + nx]); tmp.space = 3 * ny + nx; if(mp[tmp] == false){ mp[tmp] = true; tmp.turn++; q.push(tmp); } } } return -1; } signed main(){ Puzzle in; rep(i, 9){ cin >> in.field[i]; if(in.field[i] == 0){ in.field[i] = 9; in.space = i; } } in.turn = 0; cout << solve(in) << endl; }
【ICPC World Final 2017】E : Need for Speed
問題
- ある区間の距離と移動速度がそれぞれ
として与えられる.
は実際の速度s+c(cは定数)として表示されている.
- 実際にかかった時間tが与えられるので, cが何であるかを求めよ.
方針
コード
#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 eps 1e-14 using namespace std; signed main(){ int n; double t; double d[1001], s[1001]; double _min = 1500.0, _max = -1200; scanf("%d %lf", &n, &t); rep(i, n){ scanf("%lf %lf", &d[i], &s[i]); _min = min(s[i], _min); } double right = _min; double left = -1001000; double c; double prev = 0.0; rep(i, 100){ c = (left + right)/2.0; double sum = 0.0; rep(i, n) sum += (d[i] / (s[i] - c)); if(fabs(sum - t) < eps){ break; }else if(sum > t){ right = c; }else{ left = c; } prev = sum; } printf("%.9f\n", -c); } ``
【AOJ 2015】Square Route
問題
Square Route | 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 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)において
となる.
- 今回はノード数が
であるので, 隣接リストを使った実装を行う.
- 隣接リストでグラフを表現し, 二分ヒープ(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番目までのセットを比較して同じ形の折れ線であるか判定する.
- 同じ折れ線であるかの判定は, 以下のいずれかを満たす.
- xy平面内で回転および平行移動によって(拡大縮小や裏返しをせずに)重なり合う
- 始点から終点まで の頂点が逆順に指定されている
- 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】
— aiko official (@aiko_dochibi) 2017年5月20日
名古屋公演1日目🐓Zepp Nagoyaでは2015年7月以来のライブです！今日は最高気温30℃らしいですが🌞こっちはもっともっと熱気で凄いライブにしましょうね🔥よろしくお願いいたします！
会場に着くとウェルカムボードが✨ただいまー！！🏃💨 by.スタッフ pic.twitter.com/W6LcSPB0y7
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階指定席って実はめちゃくちゃいい席なのでは？
セットリスト
- 彼の落書き
- 染まる夢
- 赤いランプ
- キスが巡る
まさかキスが巡るが聞けるなんて. ツイてるなあなどと考えていた. - なんて一日
ライブBDで見てめちゃくちゃ気に入った曲. 結構昔の曲連続したなーと思いつつ、アルバム引っさげじゃないライブの良さだよねと思っていた. - プラマイ
- 線香花火
- 微熱
こういうバラードで目を閉じて聞くという贅沢なことをしていた. たまに聞くのに集中するのもいいよね. - それだけ
- 密かなさよならの仕方
シモネタのあとに歌ったのってこれでしたっけ（記憶が曖昧） - 桜の時
- 蝶々結び
- 小鳥公園
- もっと
- Loveletter
このあたりからの盛り上がりはすごかった. やはりLoveletterは盛り上がる. - be master of life
- あたしの向こう
アンコール
- 4月の雨
- 赤い靴
赤い靴にコールなんてあったっけと思ったが, 最後の「ばいばーい」だった. - ボーイフレンド
ダブルアンコール
- 愛の病
愛の病は早いほうが良いよね. - ジェット
このアンコール, LLP19福井公演を思い出した.
コールアンドレスポンス
「男子」「女子」「そうでない人」「メガネ」「コンタクト」「裸眼」「小鉢」「お茶碗（不確か）」「どんぶり」「PA席」「サイドスタッフ」「照明」「警備のお兄さん」といった感じでした. あとなんか吠えるパートも有りました. それに加えて年齢別（10代, 20代, …) ももちろん有りましたよ.
ライブ中の会話
- 大阪公演で歯が欠けたらしく, 名古屋に来る前に歯医者によったとのこと
- 嵐のニノも歯が弱いって話をしていた.
- マウスピースしてる人を聞いてましたね. レーシックぐらいいた.
- ヤスケンの歯は全部差し歯
- こばち姉さん
- aikoが巨乳でPower of Love歌ってたらそれは違うみたいな話を母親からされた.
- バーが小鉢を刺激するね
- マネージャーとご飯食べ行ったら隣の席にいた女の人が男の人に愚痴ってた. （どうも同じ会社の違う部署というつながりらしく, 上司や部下に対する愚痴を言っていたそう）
- 上司のほうは21:30に酔いつぶれる.
- 女の人はDragon Ashを聞いて育ったので打たれ強いという持論を展開していた.
- それに対して男の人が「ZIGGY世代では？」というツッコミ. どっちも同じではないかという議論がZepp Nagoyaでなされた. なんだこれは
- めっちゃエゴサしてる（アーティストとかめっちゃエゴサしてるからね）
- 8歳の女の子に対してシモネタのオンパレード
- お母様の主張がすごく激しかった.
- ギターの設楽さんは白湯を飲みまくってるらしい. （お酒とかも飲まないそうです）
まとめ
自身初のRock参加となりました. 開場どんなもんかなと思いましたが, 2階席からでもaikoをしっかり見ることができ良い会場だなと思いました. 500円はらってドリンクと交換するとか柵があるとか, ライブハウスそのものが初めてだったので少し戸惑いながらも楽しむことができました.
Rockの魅力は何と言っても近さ. 1階席の人たちは本当にaiko近くて羨ましい反面, 自分は1階席で落ち着いて見れるのだろうかとも思いました. 2階席でゆっくり見るのが自分にはあってるのかもしれない.
あと今回バンドメンバー初回のときの演奏がみんなかっこよかったですねー. 佐野さん本当に手が2本なのかってぐらい激しいドラムでした. 格好良かった！あと今回はキーボードが2人体制でしたね. 初めて見ました.
連番していただいた方もとても良い方で, 非常に良いライブの思い出ができました. ありがとうございます.
ただ, 階段上がってすぐに分煙されてない状態の喫煙所があるのはちょっとどうかと思いました. あれはいただけないですね.
関係者ツイートなど
名古屋ライブ1日目終わりましたー！
— aiko official (@aiko_dochibi) 2017年5月20日
終わった後、素の顔しか出来ひんくらいに色々出ました笑
皆さん最後まで本当に本当にありがとうございました！！ pic.twitter.com/IBknpwsS4z
名古屋2日間。会場も真夏日で興奮しました☀️打ち上げの鯛めしも激アツでかき氷🍧はキンキンでした💦最高の夜をありがとうございました😊 pic.twitter.com/AI9pMP1oIV
— 佐藤達哉 (@satotatsua) 2017年5月22日
aikoさん Live Tour
— 芳賀義彦 (@yoyoyotie) 2017年5月21日
「Love Like Rock vol.8」
Zepp名古屋公演でした！！！
2日間の激アツライブ最高でした！！！
ありがとうございましたm(__)m pic.twitter.com/pZg7YvEICH
