日々精進

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

プログラミング

【AOJ ALDS1_7】A: Tree - Rooted Trees

問題 Rooted Trees | Aizu Online Judge 方針 根付き木を実装する. Nodeという構造体を定義しておき, ノード番号(id), 親ノード(parent), 子ノード(child), 深さ(depth)というメンバを定義する. 入力にそって親子関係を構築していく. すべて終わったあと, ro…

【AOJ 1167】Pollock's conjecture

問題 Pollock's conjecture | Aizu Online Judge 方針 動的計画法を使う. nを表現するのに必要な正四面体の数の最小値 としたとき, はとして求めることができる. 1から順番にもとめておき, 入力したnを添え字にしてテーブルを出力する. コード #include<iostream> #inc</iostream>…

【AOJ 1346】Miscalculation

問題 Miscalculation | Aizu Online Judge 方針 ルール1は通常の優先順位(乗算→加算)で演算する. ルール2は左から順番に計算する. ルール1とルール2の結果が等しく, 入力した数字とも等しければU ルール1が入力した数字と等しければM, ルール2と等しければ…

【AOJ 2340】Carpenters' Language

問題 Carpenters' Language | Aizu Online Judge 方針 文法を見てみると, 実は挿入位置は関係なくてかっこの個数だけで判定できることが分かる. 左括弧, 右括弧それぞれの個数を保持しておき, 同じの時はYes, そうでないときはNoを出力する. コード #include<iostream></iostream>…

【AOJ 1249】Make a Sequence

問題 Make a Sequence | Aizu Online Judge 方針 置くたびにm個以上つながっているかを調べる. 縦横斜めの3方向を探索するので, dx, dy, dzという配列を用意しておき3重ループする. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) f</bits/stdc++.h>…

【AOJ 2165】 Strange String Manipulation

問題 Strange String Manipulation | Aizu Online Judge 方針 S,A,Cを総当りして, エントロピーが一番低くなる場合を探す. 誤差を考えて, epsを足さないと死んでしまう. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a</bits/stdc++.h>…

【AOJ 1368】Quality of Check Digits

問題 Quality of Check Digits | Aizu Online Judge 方針 4桁の数字(abcd)をループで作る. eを求め, それをチェック関数に投げる. abcdの各桁を0-9の数字で置き換え, 0になったら-1を返す. また, 連続する2桁を交換し(ただし, それぞれが違う文字のときのみ…

【AOJ 1367】Rearranging a Sequence

問題 Rearranging a Sequence | Aizu Online Judge 方針 与えられたM個の値を逆順に出力する. 出力したかどうかを管理しておき, 1回も出力していない場合に限って出力を行う. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int</bits/stdc++.h>…

【AOJ 2619】Thread Tree

問題 Thread Tree | Aizu Online Judge 方針 木を作って順に辿って出力する. 英語つらいなって思ったけどそんなに難しくなかった.(これは方針ではない) コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n </bits/stdc++.h>…

AtCoder Beginner Contest #60

問題はこちら. abc060.contest.atcoder.jp 問題A:Shiritori 文字列A, B, Cが3つ与えられた時, それらがしりとりになっているか判定せよ. #include <iostream> using namespace std; signed main(){ string a, b, c; cin >> a >> b >> c; if(a[a.size()-1] == b[0] && </iostream>…

【AOJ 2565】Broken Audio Signal

問題 Broken Audio Signal | Aizu Online Judge 方針 区間を狭めていって, その区間によって結果を出力する. xが偶数番目のときに上界, 奇数番目のときに下界を決めることができる. xが連続した時はnone, 上界がないなど様々な場合分けがあってとてもつらい.…

【AOJ 2727】M and A

問題 M and A | Aizu Online Judge 方針 SとTの部分文字列を交互に繋げてSを作ることができるか調べる. Sの部分文字列は自明にSに含まれているので, Tの部分文字列を考える. Tの先頭から順に探索し, 部分文字列であるかを試す. (Sの偶数番目と奇数番目をと…

【AOJ 1232】Calling Extraterrestrial Intelligence Again

問題 Calling Extraterrestrial Intelligence Again | Aizu Online Judge 方針 とを満たすp, qを求める. (p, qは素数) エラトステネスの篩を使って素数を生成する. それらを使ってpとqの組を試す. qを求めるループの条件式は, という不等式から, とした. コ…

【AOJ 1241】Lagrange's Four-Square Theorem

問題 Lagrange's Four-Square Theorem | Aizu Online Judge 方針 全部探索する. コード #include <iostream> using namespace std; signed main(){ int n; while(cin >> n, n){ int cnt = 0; for(int i = 1 ; i * i <= n ; i++){ if(i*i == n) cnt++; for(int j = i ; </iostream>…

【AOJ 2300】Calendar Colors

問題 Calender Colors | Aizu Online Judge 方針 N個のLABカラーが与えられる. そこからM個取り出し, 要素それぞれの差の二乗の和を求める. その和の最大値が答え. であることから全探索しても良さそう. M個取り出すときにbitを使うと便利っぽい. コード #in…

【AOJ ALDS1_6】A: Counting Sort

問題 Counting Sort | Aizu Online Judge 方針 計数ソート(バケットソート)をしよう. アルゴリズムは問題をそのまま実装. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; </bits/stdc++.h>…

【AOJ 1285】Grey Area

問題 Grey Area | Aizu Online Judge 方針 ヒストグラムを印刷するために必要なインク量を求めようという問題. vを入力する際に, 区画の最大値(imax), 頻度の最大値(hmax)を求める. hist[i] := の頻度としたとき, を計算する. 最後に0.01を足す(線とかを引く…

AtCoder Beginner Contest #59

問題A:Three-letter acronym 3つ文字列が与えられるので, それぞれの1文字目を大文字にしてつなげ表示する. 文字コードでやった. #include <iostream> #include <cstring> using namespace std; int main(){ string s1, s2, s3; cin >> s1 >> s2 >> s3; cout << (char)('A'+s1[</cstring></iostream>…

【AOJ 1257】And Then There Was One

問題 And Then There Was One | Aizu Online Judge 方針 Josephus problemという有名な問題らしい. (ただし, ) という漸化式を解くことでで求まる. コード #include <iostream> using namespace std; int f(int n, int k){ if(n == 1) return 0; return (f(n-1, k)+k)%</iostream>…

【AOJ 2242】Era Name

問題 Era Name | Aizu Online Judge 方針 EraBasedYearとWesternYearが入力し, それらをs(start), e(end)という変数に代入. queryが ]にはいってるとき, が答え. 当てはまらない時はUnknownとなる. コード #include <iostream> #include <vector> #include <algorithm> using namespace st</algorithm></vector></iostream>…

【ALDS1_10】B: Dynamic Programming - Matrix Chain Multiplication

問題 連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 行列が5個与えられた時, 計算の順序は 1. 2. 3. など様々な順序がある. すべてのパターンを試すアルゴリズムでは, となってしまうため, これよりも計算効率の良いアルゴリズムを考える…

【AOJ 1610】Bamboo Blossoms

問題 Bamboo Blossoms | Aizu Online Judge 方針 エラトステネスの篩的に消していく. Nが0になったときのiが答え. コード #include <iostream> #include <cmath> using namespace std; #define MAX 7368791 int main(){ int m, n; bool flag[MAX]; while(cin >> m >> n, m||n)</cmath></iostream>…

【AOJ 2700】Airport Codes

問題 Airport Codes | Aizu Online Judge 方針 1文字目と母音の直後の文字を順に連結した文字列を作る. k文字未満ならその文字列, k文字以上なら取り出した文字列の先頭からk文字分をコードとする. kを1から50まですべて試す(試しても間に合う制約なので) コ…

【AOJ 2706】Let's Solve Geometric Problems

問題 Let's Solve Geometric Problems | Aizu Online Judge 方針 b進数k桁の値は以下のように表すことができる. 上の式を変換すると,となることがわかる. 上記の式の形に変換したときのbが答え. コード #include <iostream> #include <cmath> #include <utility> #include <vector> #include <algorithm> u</algorithm></vector></utility></cmath></iostream>…

【AOJ ALDS1_7】B: Tree - Binary Trees

問題 Binary Trees | Aizu Online Judge 方針 二分木を作ろう. コード #include <iostream> using namespace std; struct Node{ int parent, left, right; }; int n; Node T[30]; int D[30], H[30]; void depth(int u, int d){ if(u == -1) return; D[u] = d; depth(T[</iostream>…

【AOJ 2331】A Way to Invite Friends

問題 A Way to Invite Friends | Aizu Online Judge 方針1 配列の[a, b]を++していく. 配列fをf[i]:=i人誘う時行くことができる友達の数とする. i-1(自分を抜いた数)誘うときに, i - 1 <= f[i]となればi-1人誘えるということになる. 方針2 aのときにf[a]を…

【AOJ 1193】Chain Disappearance Puzzle

問題 連鎖消滅パズル | Aizu Online Judge 方針 横に3つ以上連鎖している箇所は消すことができる. 消えた部分には, 上にある石が空きを埋めるように落ちてくる. すべての石を落とした後に消滅の条件をみたすようなものがあればまた繰り返す. 上の通りにシミ…

【AOJ ALDS1_5】D: Recursion / Divide and Conquer - The Number of Inversions

問題 反転数 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 反転数を求める問題. バブルソートの要領で探すとになってTLEするので効率よく探す必要がある. タイトルの通り, 分割統治法(マージソート)を活用することででカウントすることができる. …

【AOJ 2253】Brave Force Story

問題 Brave Force Story | Aizu Online Judge 方針 BFSをする. その際にそこにたどり着ける距離を保存し, 最後にたどり着けたマスの数を数える. 普通に探索するとインデックスが負になって悲しくなるので, 適当に座標をずらす. コード #include <algorithm> #include <iostream> #</iostream></algorithm>…

【AOJ ALDS1_5】B: Recursion/Divide and Conquer - Merge Sort

問題 Merge Sort | Aizu Online Judge 方針 マージソートをします. INFを適当においたせいで無事に死んだ コード #include <iostream> #include <cstdio> 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 MAX</cstdio></iostream>…