問題 http://uva.onlinejudge.org/external/110/11012.html概要 三次元の座標が与えられる。２点間のマンハッタン距離の最大値を求めよ。制約 テストケース 0 点の数 2 解法 人の解説を聞いてコードを見て書いた。まだ良くわかってない。 #include <bits/stdc++.h> using na</bits/stdc++.h>…

問題 http://uva.onlinejudge.org/external/115/11545.html概要 "S...****................***.D" とかいう感じの道を最短時間で進めという問題。 １マスを１時間で移動することが出来る。 夜は '*' の道を通ることは出来ない。あるマスにいるというのは、そ…

問題 http://uva.onlinejudge.org/external/112/11231.html概要 大きな市松模様のうち、８×８の市松模様はいくつあるか。解法 （実はまだよく分かってない） #include <bits/stdc++.h> using namespace std; int countChessBoard(int n, int m) { n -= 7, m -= 7; if(n < 1 </bits/stdc++.h>…

問題 http://uva.onlinejudge.org/external/111/11124.html概要 奇数段目かつ奇数番目のブロックのみの数字が書かれた積み石がある。最下段の数字以外はパスカルの三角形同様の方式で値が決まるので、全ての数字を特定し出力せよ。解法 積み石の一般の位置に…

問題 http://uva.onlinejudge.org/external/115/11553.html解法 Bobが最善の手を取ってきた前提でAliceの得点を最大化する。 #include <iostream> #include <algorithm> #include <limits> using namespace std; int main() { int grid[8][8]; int Tc; cin >> Tc; while(Tc--) { int N; ci</limits></algorithm></iostream>…

解法 重ねあわせた全体のカードの束から、２つに分ける位置を決めるように区間DPする。 元のカード束のうち２つの隣接する束を重ねるという動作を最も原子的なものとして、同様のアルゴリズムが最後まで展開されることを汲み取れれば解ける。反省 問題文を読…

解法を考えている途中

問題 http://uva.onlinejudge.org/external/108/10896.html概要 アルファベットのみがシーザー暗号化された暗号文と、平文の一単語が入力として与えられる。暗号鍵を、平文の一文字を 'a' としたときに暗号化された一文字とするとき、あり得る暗号鍵を全てア…

問題 http://uva.onlinejudge.org/external/109/10950.html概要 アルファベットの小文字1文字に対して数字コードが割り当てられる。暗号化した数字列が与えられるので、平文としてあり得る文字列を全てアルファベット順に列挙せよ。ただし候補が100個以上あ…

ベイジアンネットは各ノードが定量的な確率情報によって意味づけられた有向グラフである。 確率変数の集合がネットワークのノードを構成する。確率変数は離散でも連続でもよい。 X から Y へグラフが張るとき、XはYの親ノードと呼ばれる。 各ノード X_i はそ…

問題 http://uva.onlinejudge.org/external/9/979.html意訳 伝説の三角形 MGT が忌まわしき略奪者トライアングルマンによって平面世界に隠されてしまった。三角形は自由に回転、平行、反転がなされている可能性があり、加えて無慈悲にも多数の点の上に紛れて…

問題 http://uva.onlinejudge.org/external/9/983.html概要 N×N の正方行列が与えられる。全ての M×M の部分行列において、各値の和を出力せよ。またそれらの合計も出力せよ。合計は 64bit signed integer に収まるものとする。制約 N 解法 （普通の）二次元…

問題 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>

競技プログラミング 日常の勉強法 考え始めてから3日以上経ったものは答えを見て良い 初めて見てから一週間以上経ったものは毎日理解に努めないといけない 一ヶ月以上経ったものは理解できてないといけない（それが無理ということはあまりないはず） 一度理…

型名に typename をつける コンパイラが「型」か「staticなメンバ」かを判別できるようにするため

1項 C++は４つの基本的なサブセットでできている C ブロック ステートメント プリプロセッサ 組み込みのデータ型 配列 ポインタなど オブジェクト指向C++（クラス付きのC） ctor, dtor を持つクラス カプセル化 継承 ポリモーフィズム 仮想関数（動的結合） …

問題 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…

コンストラクタ explicit B(int x=0, bool b=true); のようなものもデフォルトコンストラクタとなる コピーコンストラクタは、オブジェクトを「同じ型の別のオブジェクト」で初期化するときに使われる Widget(const Widget& rhs); Widget w2(w1); Widget w3 …

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

問題概要 vector parent が与えられる。parent[i] とは i 番目のノードの親が parent[i] であることを示す。deletedCell で削除するノードが与えられたとき、残ったノードのうち葉のノードの数をカウントせよ。解法 子を参照する形の木を、与えられた vector…

問題 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} からそれぞれ任意個数分選び、乗算する。それぞれ素数同士なので、別の組み合わせによる値の重複はない。 …

概要 二分木が入力されるので Intersect または Union して出力せよ。解法以下がBNF。 := ( , ) | ε 一つの親ノードと２つの子ノードの３つのノードについての処理を考える。つまりカンマの位置を特定することが必要なのでその方法を考える。 先頭の'('を読…

概要 入力された文字列Sの、長さL分の部分文字列を任意回数ソートできる。ソートした際にはソートされた部分文字列以降にある文字列は全て削除される。このとき辞書順で最小の文字列は何を生成できるか。解法 部分文字列Lの区間を、右端から一文字ずつ左端に…

解法 ２×２の正方形のグリッドを取り出したとき、その中央の格子点を生命体の分割の数が変わるイベント点とする。するとグリッドのパターンは分割の数が 1 増加する２つと、1 減少する２つの４パターンのみに絞られる。（以下のコードでは check() 関数にそ…

問題 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 の位置関係に少し注意を払えばバグを生む要素は少ない。…