問題 http://uva.onlinejudge.org/external/114/11413.html概要解法 #include <bits/stdc++.h> using namespace std; #define LLINF (LONG_LONG_MAX/4) #define ALL(c) (c).begin(), (c).end() #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; int N, M; vector<ll> vessel; bool ev…</b;i++)></bits/stdc++.h>

問題 http://uva.onlinejudge.org/external/109/10976.html制約 入力は 10000 以下。解法 数学の問題。 定数 K が入力で定まるので、x か y を動かせばもう片方の変数が特定できる。 ポイントは入力から変数の制約（未知情報の制約）を見つけること。変数の…

問題 http://uva.onlinejudge.org/external/111/11105.html概要 4n+1で表される数を H-number と呼ぶ。H-number は 3 種類に分けられる。1と、H-primeと、H-composite である。1以外の H-number の積で表されない H-number を H-prime と呼び、それ以外の 1…

問題 http://uva.onlinejudge.org/external/4/435.html概要 党が連立したとき全体で過半数の投票数を獲得すると、その連合した党は選挙に勝つことが出来る。ここで各党に対して投票数でない新たな強さの指標 power index を考える。power index とは、あとひ…

問題 http://uva.onlinejudge.org/external/113/11371.html概要 入力の数字 N を並び替えた数字 a, b がある。a - b が 9 の倍数になり、かつ a - b が最大になるような a, b を求めよ。ただし、a, b はleading 0 となるような数字であってはならない。解法 …

問題 http://uva.onlinejudge.org/external/4/443.html概要 {2, 3, 5, 7} を素因数に持つ数字をのうち、N番目のものを言い当てよ。解法 {2, 3, 5, 7} からそれぞれ任意個数分選び、乗算する。それぞれ素数同士なので、別の組み合わせによる値の重複はない。 …

問題 http://uva.onlinejudge.org/external/2/296.html概要 0000 〜 9999 までの4桁の数字列に Hit And Blow をする。質問とそのときのHit数とBlow数が与えられるので、4桁の数字が一意に特定できるならば、その値を出力せよ。また複数候補がある場合は "ind…

問題 http://uva.onlinejudge.org/external/112/11258.html概要 数字列を 32bit signed integer に収まる範囲で任意の数に分割し、その和を求めよ。解法 メモ化再帰による区間DPの典型問題。l, r, i+1 の位置関係に少し注意を払えばバグを生む要素は少ない。…

問題 http://uva.onlinejudge.org/external/112/11287.html概要 Fermatの小定理：（または） であるが、pが素数でないときこの関係式が成り立つ p を 基数 a における pseudoprimes という。 p が 基数 a における pseudoprimes であるかどうか判定せよ。解…

問題 http://uva.onlinejudge.org/external/113/11350.html概要 走査の方向 'L' または 'R' が書かれるので、Stern-Brocot Tree を親ノードから辿れ。解法 左と右の数字の和を取って木を走査していく。二分探索木である。 図を見ながらコードで確認した方が…

問題 http://uva.onlinejudge.org/external/2/264.html概要 AOJ1007 JPEG Compression の劣化版解法 うまいやり方もあると思うけど、方向で場合分けをして四方向分作り、愚直にプログラムを書けば終わり。 #include <bits/stdc++.h> using namespace std; int main() { int </bits/stdc++.h>…

問題 http://uva.onlinejudge.org/external/2/297.html概要 画像が４分木を用いてモノクロで入力される。２種の画像を合わせたときに塗られたピクセルはいくつあるか解法 １次元配列の 4*深さ+i (1 深さに対応したピクセルの数を配列で持っておくと便利。４…

問題 http://uva.onlinejudge.org/external/114/11461.html ２つの正の整数a, b(a, bを含む)の間に含まれる２乗の数を答えよ。解法 整数の間をループで回して調べても良いが、もっとうまい方法がある。 a-1, b それぞれのルート取って切り捨てて差分を取れば…

問題 http://uva.onlinejudge.org/external/108/10858.html意訳 生物名が複数種与えられる。与えられた関係から食物連鎖に関わるグループを部類分けできるので、そのときの食物連鎖のグループの最大サイズを出力せよ。ただしAがBを捕食する関係にあるとき、…

問題文 http://uva.onlinejudge.org/external/106/10664.html解法 取る取らないのO(2^20)のDFSで解けばよい。 ちょうど半分に分けられるかどうかを判定するが、ここで入力の重さを安易に整数除算して切り捨てによるミスを犯さないようにする。ただサンプル1…

http://uva.onlinejudge.org/external/106/10633.html問題概要 ２桁以上の整数Nと、Nの下一桁を取り除いた整数Mが与えられる。N-M の値があなたに伝えられるので、もとのNの候補を昇順ソートして全て示せ。解法 #include <bits/stdc++.h> using namespace std; typedef unsi</bits/stdc++.h>…

問題文 http://uva.onlinejudge.org/external/4/440.html問題概要 1からNまでの数列それぞれにランダムに対応させた地域のネットを遮断していく。方法は公平性を極めたいので、遮断の順序にランダム性を導入する。ランダム性は、数列を循環させた上ではじめ…

問題文 http://uva.onlinejudge.org/external/4/400.html問題概要 ls コマンドで出力されるような表を実装せよ。ファイル名がある部分だけ、全ての項目を最も長いファイル名 + 2 まで空白で埋める。'-' は丁度60文字である。解法 行と列のサイズ設定が一番詰…

問題文 http://uva.onlinejudge.org/external/5/542.html問題概要 サッカーのトーナメント戦がある。a国がb国に勝つ確率が隣接行列で与えられるので、出場する16カ国それぞれについての優勝確率を算出せよ。解法 1試合で a国が勝つパターンと b国が勝つパタ…

問題文 http://uva.onlinejudge.org/external/104/10466.html概要 一つの恒星の周りを惑星が周り、その惑星を別の惑星が衛星のように周わることが繰り返し続く惑星系がある。この惑星系で、それぞれの惑星は二次元上の円を成して周わる。N個の惑星が存在する…

問題文 http://uva.onlinejudge.org/external/115/11559.html概要 ポイントは以下 You are free to choose from a number of weekends this autumn, and have to find a suitable hotel to stay at, preferably as cheap as possible. > コストを最小にする…

問題文 http://uva.onlinejudge.org/external/106/10678.html概要 距離 D の２本の柱に長さ L ロープが繋がっている。 一頭の牛がこのロープに付けられたリングと繋がって放牧されていとき、牛が動ける面積を求めよ。解法 牛の動ける領域は楕円の面積分の領…

問題文 http://uva.onlinejudge.org/external/104/10489.html概要 深さに対して分岐するノード数が決まっている木がある。全部で B 個の木があるので、全てのノードを N 人に等配分し、そのときの余りを出力せよ。解法 英文の意味が取れればやるだけ。深さと…

問題文 http://uva.onlinejudge.org/external/104/10493.html概要 葉ノード数がちょうど M で構成される N 分木は存在するか。 そのような N 分木のノード数が一意に定まるなら、"N M 全体のノード数" を出力。 複数存在するなら "Multiple" 存在しないなら …

問題 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1872解法 解き方は何でもいいけど、文字列でやるか bitset でやるかとか、文字列でないなら1の数え上げは __builtin_popcount(unsigned long) とかそ…

問題 http://uva.onlinejudge.org/external/109/10938.html概要 ノードとノードの接続関係を表した木の情報が与えられる。あるノード２点にノミがいて、それらは相手のノミに向かって最短で移動しようとする。最後に一つのノードに終着する場合と、お互い隣…

問題 http://uva.onlinejudge.org/external/3/350.html解法 入力が Z, I, M, L の順で 4つあたえられるので、Lを変換する際の循環の長さを出力するだけ。 自分はサンプルの L = 4 という数字をなぜか次のケースに関係する値かと勘違いして小一時間詰まってい…