読者です 読者をやめる 読者になる 読者になる

AOJ1161 Verbal Arithmetic

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1161覆面算を解け。ただし、以下の条件を満たす。 異なる文字で同じ値が重複してはならない 複数桁ある数の時、先頭の数字は0であってはならない

AtCoder TTPC 2015 C - おおおかやま

問題 http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_cリンク先を読んで下さい

AOJ2426 Treasure Hunt

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426N個の宝の座標が与えられる。座標には重複も含む。 M個のクエリが与えられる。各クエリは長方形領域を示す。 クエリに対し、領域に含まれる宝の数を答えよ。 長方形領域は境界を含む。点…

AOJ2131 Pi is Three

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2131π-R 有理数Pの既約分数について考える。 分母を最小化して、同じ分母であれば、πにできるだけ近い値を求めよ。 R

AOJ2684 RLE Replacement

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2684ランレングス符号化された文字列A, B, Cが与えられる。 Aのうち、はじめてBが生じる場所をCに置換せよ。A, B, Cの各文字と数字のペアの数

AOJ2555 Everlasting Zero

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2555N個のスキルがあり、それぞれについて初めの経験値は0である。 あるコマンドを覚えるためには、指定された複数のスキルの経験値が条件を満たす必要がある。 条件は、スキルi >= 3, スキ…

AOJ2176 For the Peace

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2176N個の国がある。各々の国に対して、逆時系列順に新たに作ったミサイルの強さがM[i]個ずつ与えられる。 国力とは、持っているミサイルの強さの和で定義される。 ミサイルを破棄するには、…

AOJ2640 Prowler

AOJ

問題 N*Mのグリッドが与えられる。壁に右手を添えながらゴールに到達することが出来るか? 到達可能なとき、ゴールに到達するまでに踏んだマスの数を答えよ。 N, M

AOJ2224 Save your cats

AOJ

問題 N本の柱の座標が与えられ、柱と柱を繋ぐM個の壁が与えられる。 壁で囲まれた領域内に猫がいる。壁を壊して猫を助けたい。 壁を壊すコストは、壁の長さだけ掛かる。壁同士は交差しない。 すべての猫を助けるために壁を壊すコストを求めよ。

AtCoder Regular Contest 052 B - 円錐

ARC

問題 http://arc052.contest.atcoder.jp/tasks/arc052_b3次元空間上にN個の円錐が互いに重なり合わないように存在する。 それぞれの円錐はYZ平面に垂直に浮かんでいる。 M個の区間のクエリ(L[i], R[i])が与えられる。 各クエリに対して、2平面X = L[i], X = …

AtCoder Regular Contest 042 A - 掲示板

ARC

問題 http://arc042.contest.atcoder.jp/tasks/arc042_aN個の掲示板のスレッド1〜Nがある。はじめ、番号順に上から並んでいる。 あるスレッドに書き込みがおこると、そのスレッドが一番上位になる。 時系列順にM回の書き込まれたスレッド番号が入力される。 …

いかにして問題を解くか 第II部

対話 「慣れること」 どこから出発したら良いか どうすればよいか そうすれば何が出来るか 「もっとよく理解するように努めること」 どこから出発したら良いか どうすればよいか そうすれば何が出来るか 「よい考えを探すこと」 どこから出発したら良いか ど…

AOJ2566 Restore Calculation

AOJ

問題 3つのN桁の数A, B, Cがある。いくつかの数字は'?'となっている。 '?'には、数字の先頭であれば'1'から'9'が入り、先頭でなければ'0'から'9'が入る。 A + B = C が成立するパターン数を求めよ。(MOD 10^9+7)

AOJ1056 Ben Toh

AOJ

問題 初日、半額弁当は100%入手できる。2日目は50%の確率で入手できる。 3日目は、2日目で入手出来たのなら、25%の確率で入手できる。 2日目で入手できなかったなら、再び100%の確率で入手できるようになる。 以下このアルゴリズムをN日まで繰り返したと…

AOJ2534 Dictionary

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534アルファベットに対応させることのできる言語が発見されている。 単語が改行区切りで順に書かれている。辞書順が定義されている可能性のある言語かどうか判定せよ。

AOJ2178 Futon

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534N個の2*1マスの布団を広大なグリッド上に並べる。各々左上の座標と、縦と横のどちらの向きで配置するかの情報が与えられている。別の人の頭と足が隣り合わせになってしまう箇所が1つで…

AOJ2299 Tiles are Colorful

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2299以下のようなH*Wのグリッドがある。 ..A....... .......B.. .......... ..B....... ..A.CC.... ある空のマスから上下左右4方向に初めてぶつかったアルファベットに2つの同じ文字であれば…

AOJ2320 Infinity Maze

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2320以下の様なH*Wのグリッドが与えられる ####. ..... .#S#. ...#. #.##."NEWS"の何れかのアルファベットがおいてある場所を初期位置とする。 真っすぐ進み、壁にぶち当たったら90度回転す…

AOJ2241 Usaneko Matrix

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=22412人でN*Nのビンゴゲームを行う。マスの各値は互いに異なり、コールされる値もまた互いに異なる。 勝つ条件として、うさぎはU以上の列を揃える必要があり、ねこはV以上の列を揃える必要が…

AOJ1512 Smartphone Game

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1512パズドラを1回だけシミュレートせよ。ただし、移動可能回数は高々N回までである。 0 グリッドは5*5

AtCoder CodeFormula2014 予選A C - 決勝進出者

問題 http://code-formula-2014-quala.contest.atcoder.jp/tasks/code_formula_2014_qualA_cN回の予選があり、開かれる順序の早い順に、それぞれの順位がK位まで与えられる。ここからK人を選抜したい。選抜の方法は以下である。 1. 予選の順位が高いほうが優…

AOJ1190 Anchored Balloon

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1190&lang=jpZ=0の平面上にN個の整数座標が与えられる。各々に杭を打ち、それぞれ異なる長さのロープで一つのバルーンに繋ぐ。 上空に飛ばしたとき、バルーンの上昇する最大の高さを求めよ。…

AOJ1031 Simple GUI Application

AOJ

問題 指定された記法のXMLを解析してGUIオブジェクトの配置状況を読み取り、クリックした領域と子オブジェクトの数を答えよ。解説 地道にやる。sscanfを使って、','区切りの数値を読み取ったり、タグを正規表現で読み取るのが賢いらしい。 自分はまだ荒削り…

AOJ2363 Unequal Dice

AOJ

問題 多面体サイコロがあり、幾つかの面は数字が書かれていない場合もある。 サイコロを振ったとき、数字が書かれていない面が表になった場合、数字の面になるまでサイコロを振る。 多面体サイコロは、数字が書かれている面に対して、その数字とその面の出る…

AOJ2333 My friends are small

AOJ

問題 重さのみのナップザック問題が与えられる。 任意の順番で品物を詰めることができるが、まだ品物が入る場合は出来る限り詰めなければならない。 N個の品物を容量Wのナップザックに入れる組み合わせの数を答えよ。

SRM Div2 555 〜 599, 600 〜 解説記事

SRM

SRM Div2 の解説記事です。まだまだ抜けが有ります。https://github.com/motxx/SRM-Div2

SRM635 Div2Hard LonglongestPathTree

SRM

#include <bits/stdc++.h> using namespace std; // rep #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) struct Edge { int to, cost; }; // typedef typedef vector<Edge> Edges; typedef long long ll; int N; Edges G[2010]; bool notuse[2010]; typedef ll Weight; typedef pair<Weight, int> R…</weight,></b;i++)></bits/stdc++.h>

SRM635 Div2Med QuadraticLaw

SRM

問題文 本来の授業時間 d が与えられる。授業の開始を t 遅らせるとき、更に t^2 の時間だけ授業時間が少なくなる。授業時間をできるだけ少なくするための t を求めよ。解説 入力が10^18なので普通に線形探索は不可。二分探索しても良いが、整数型で探索範囲…

LiveArchive 4994 Overlapping Scenes

解法 入力の文字列を next_permutation() して、順に重ねあわせていく。2つの文字列に対して重ね合わせをして、末尾文字列から一致した部分を引いたものを返す関数 concat() を用意した。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i</bits/stdc++.h>

yukicoder no.3 ビットすごろく

問題文 http://ch.nicovideo.jp/programing/blomaga/ar583624解答 __builtin_popcount() + 幅優先探索 する。最短経路問題である。 #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int const INF = 1<<29; bool vis[10001] = {}; queue<pair<int, int> > q;</pair<int,></bits/stdc++.h>…

yukicoder no.30 たこやき工場

問題文 http://yukicoder.me/problems/a14e51c14f78a730解法 DFS + メモ化再帰(=貰うDP)コメントアウトはBFSでやろうとしてる。最短路をメモしないのでTLEする。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i</bits/stdc++.h>

yukicoder no.27

問題文 http://ch.nicovideo.jp/programing/blomaga/ar625916解説 まず A, B, C を [1,30] の範囲でそれぞれ全探索し、値を固定する。 dp[i] := A, B, C を用いて整数 i を作るための最小数 として DP すると、V0, V1, V2, V3 のそれぞれについての必要な最…

JAG夏合宿2014 3日目 H - Points and Lines

問題文 http://jag2014autumn.contest.atcoder.jp/tasks/icpc2014autumn_h感想 問題文には左優先で計算すると書いてあるが、自分は初めは、順序は任意に決定されるかつ幾何的制約を満たすものが最終的な解になるのでは、と思ってしまった。以下の参考問題の…

JAG夏合宿2014 3日目 A - North North West

#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a; i<(int)b; i++) #define rep(i,n) REP(i,0,n) int main() { string str; while(cin >> str) { if(str == "#") break; vector<int> order; rep(i, str.size()) { if(str[i] == 'n') { order.push_</int></bits/stdc++.h>…

AtCoder BeginnerContest 014 D

解答 根付き木において、頂点 a, b 間を辿る最短パスはの最も近い共通祖先の頂点である。よって LCA を用いて、頂点 a までの深さ + 頂点 b までの深さ - 2*共通祖先の頂点 + 1 が答えとなる。 まだ自力でLCAを書くことが出来ないので蟻本そのままのコードを…

AtCoder BeginnerContest 014 C

解説 いもす法。 まず一次元で状態が変わる点をイベントとしてみて、カウンタ +1, -1 の増減を設定する。O(N) 累積和を取り、実際の状態の遷移状況を求める。O(N) よって全体で O(N) #include <bits/stdc++.h> using namespace std; #define MAX (1000000) int imos[MAX+10]</bits/stdc++.h>…

AtCoder BeginnerContest 014 B

解説 状態を2進数値化して考えて、指定の位置にビットが立っているかどうかで N 個の ON / OFF を調べる手技。 X と (1 論理積が 0 でないなら、i 番目にビットが立っている。 #include <bits/stdc++.h> using namespace std; int main() { int N, X; cin >> N >> X; int s</bits/stdc++.h>…

AtCoder BeginnerContest 014 A

解説 足りない分は b - (a を b で割った余り) である。 数が余らない時は 0 を出力するのに気をつける。 #include <bits/stdc++.h> using namespace std; int main() { int a, b; cin >> a >> b; cout << ((a%b) ? b-a%b : 0) << endl; return 0; }</bits/stdc++.h>

yukicoder no.25

問題文 http://ch.nicovideo.jp/programing/blomaga/ar620922解説(と考えた過程) 有限小数で表せるということは、分子を整数、分母を 10^n で表せるということである。 分母が 10^n すなわち (2^n) * (5^n) で表せるためには、M が 2 または 5 の素因数の…

LiveArchive4403 ASCII Diamondi

解説 描画する文字の位置に対応する文字を探してやれば、描画する長方形の範囲の計算量 40000 × テストケース 125 で解ける。 #include <bits/stdc++.h> using namespace std; #define SIZE_N (2*N-1) char change(int x, int y, int N) { int ax = N, ay = N; x %= SIZE_N;</bits/stdc++.h>…

UVa299 Train Swapping

UVa

解法 バブルソートの交換回数(反転数)を求める。 バブルソートして求めるか、あるいはBITするかマージソートするかすればよい。 以下は BIT のコード。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; class BIT { private: vector<int> bit; int size; public: BIT(int </b;i++)></bits/stdc++.h>…

AOJ2301 Sleeping Time

AOJ

解答 K = 30 までで O(2^K) なので、多少枝刈りすれば通るだろうと思っていたが TLE がなかなか取れなかった。決め手は solve() 関数内の 2行目の枝刈り。条件式を満たすとき今の確率を P倍 と (1-P)倍 に分割する必要がなくなる。コメントアウトしてある条…

UVa12295 Optimal Symmetric Paths

UVa

解説 解法が右往左往した問題。 左上半分と右下半分のコストの和を1つのコストとみなして、ダイクストラする。ある状態における最小のコストが更新できなくても等しいのであれば場合の数をカウントする必要がある。その場合にダイクストラの処理を打ち切ら…

UVa10189 Minesweeper

UVa

解説 爆弾の周りの8方向のカウンタを加算する。実装方法にもよるが、加算する場所が別の爆弾と被らないようにする。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int const dx[8] = {-1,0,1,0,-1,1,1,-1}; int const dy[8] = {0,-1,0,1,-1,-1,1,1};</vector></algorithm></iostream>…

UVa10035 Primary Arithmetic

UVa

解説 二項加算の繰上げ回数を調べる。加算処理は string よりも vector にするとやりやすいことが多いと思う。 #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; int main() { string a, b; while(cin >> a >> b) { if(a == "0" && b == "0") </vector></string></algorithm></iostream>…

UVa10300 Ecological Premium

UVa

解説 平均取って価値を掛けて総和取れみたいなことを言っているが、つまり入力の3つの要素の真ん中を無視して足しあわせろということ。 #include <iostream> using namespace std; int main() { int Tc; cin >> Tc; while(Tc--) { int N; cin >> N; int sum = 0; whil</iostream>…

TypicalDP Contest D - サイコロ

問題文 サイコロを N 回振ったとき、出た目の積が D の倍数となる確率を求めよ。 1≤N≤100 1≤D≤10^18解説 https://github.com/osak/Contest/tree/master/AtCoder/TypicalDP を見てから自分で書いてみた。サイコロによってできる積の素因数の種類は 2, 3, 5 に…

Typical DP Contest B - ゲーム

両者が最大化しながらメモ化再帰 互いに同じアルゴリズムで選択を繰り返している

UVa12316 Sewing Buttons with Grandma

UVa

解法 nHr +DP を多倍長整数で実装。 nHr は高校数学によると順列の割り算 or 組合わせから導くことが出来る。

UVa494 Kindergarten Counting Game

UVa

解法 記号を空白に変換して stringstream が吐いた数をカウントする。 #include <bits/stdc++.h> using namespace std; int main() { string s; while(getline(cin, s)) { for(int i=0; i<s.size(); i++) { if(!isalpha(s[i])) { s[i] = ' '; } } stringstream ss(s); int cnt = 0; while(ss >> s) cnt ++; cout << cnt << endl; } return 0; }</s.size();></bits/stdc++.h>