問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_11_D最近Scalaを学び始めた。詳しいことは後で。 import scala.io.StdIn._ object Main { case class Rotation(run: Dice => Dice){ def apply(d: Dice): Dice = run(d) def compose(…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A 書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で紹介されいるが、セグ木を使って効率よく解けると書いてあったので実装。 x座標を座標圧縮すると平面走…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0294 解説 http://web-ext.u-aizu.ac.jp/pc-concours/2014/download/pastexam/editorial2013_final.pdf私は書籍「最新コンパイラ構成技法」のLengauer-Tarjanの擬似コードを参考にしました…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2201金属棒の候補となる直線は ２円の共通内・外接線 ２円の内一方の半径にmを足したものと他方の円の共通内・外接線 両方の半径にmを足したものの共通内・外接線 の３通り。これを全列挙…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010前に通したコードを書き直したので。 #include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; typedef double Real; Real EPS = 1e-8; int sgn(Real a, Real b=0){return</cstdio></cmath></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1131&lang=jp 解き直し。 y/x+1/z=(yz+x)/xz だから、これを使って探索。枝刈りはしなくても通る。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int p,q,a,n; int rec(int x,int y,i</algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156 g[現在の方向][Y][X]:=最短距離 でダイクストラ。 #include<iostream> #include<vector> #include<algorithm> #include<queue> #define rep(i,n) for(int i=0;i<(n);i++) #define INF (1<<29) #define Cost first.first #d</queue></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122 dfsした。 #include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; vector<pair<int,int> >sp; int dx[12]={-1,0,1,2,2,2,1,0,-1,-2,-2,-2}; int dy[12]={-2,-2,-2,-1,0,1,2,2,2,1,0,-1}; int n</pair<int,int></cmath></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116典型問題。↓を参考にした。 http://algorithms.blog55.fc2.com/blog-entry-133.html #include<iostream> #include<vector> #include<stack> #include<algorithm> using namespace std; typedef pair<int,int> pii; char G[501][501];</int,int></algorithm></stack></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2118数字が書いてあるグリッドが与えられる。 この数字の中から、4近傍に隣接しているもの同士をとらないように選んだとき選んだ数字の和を最大化せよ。 前の一行を覚えておくdp。 #include<iostream></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2488 区間dp。monge性を使わなくても通ってしまった。 dp[i][j]:=i~j番目までの点で木を作るときの最小コスト #include<vector> #include<iostream> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cctype> </cctype></string></queue></set></map></algorithm></iostream></vector>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A Range Minimum Queryを平方分割で解いた。 #include<iostream> #include<algorithm> #include<vector> #include<climits> #define max_n 100000 using namespace std; typedef long long ll; const ll B=1000; ll a[max_n</climits></vector></algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0264 問題文の通りに実装する。 x+y=z (mod p) x-y=x+p-y (mod p) x*y=z (mod p) x/y=x*mod_inv(y,p) (mod p) #include<iostream> #include<vector> #include<algorithm> #include<string> #include<sstream> #include<cstdlib> using namespace st</cstdlib></sstream></string></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070 dp[使った数字][和]:=場合の数 #include<iostream> #include<vector> #include<algorithm> #include<cassert> #define all(c) (c).begin(),(c).end() using namespace std; int count(int bits){ bits = (bits & 0x55555555)</cassert></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0190 双方向bfsで解いた。 #include<iostream> #include<vector> #include<algorithm> #include<map> #include<queue> using namespace std; map<vector<int>,int>mp,used; struct State{ vector<int>v; int t; State(vector<int>v,int t):v(v),t(t){} }; v</int></int></vector<int></queue></map></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1215文字列といくつかの文字が与えられる。 文字をすべて含む、文字列の部分列の中で最小の長さのものの個数と、そのような部分列のなかで最初に現れるものを出力せよ。 尺取り法のような…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318無向グラフが与えられるので、車にのってsからtに行くときの最短経路を求めよ。ただし車には燃料の容量がある。車は燃料1で距離10進むことができる。次の町に着いたときに燃料がちょう…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1325二つの整数(m,n)の組をGinkgo numberと呼ぶ。 · = をGinkgo numberの掛け算とする。 また、 · = であるとき、はの約数である。さらに、あるGinkgo numberが, , , , , , , 以外に約数を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=132014個以下の文字列が与えられる。これらの文字列を全てつなぎ合わせたときの文字列の長さの最小値を求めよ。 ビットDPした。 dp[ 最後に使った文字 ][ 今まで使った文字の集合 ]:=長さ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1257連続する素数の和でnを作る場合の数を求めよ。 素数の数が1000くらいしかなかったので尺取り法した。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void){ bool prim[10</algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2151 拡張ダイクストラした。 d[ ノード番号 ][ ノードについた時の残金 ] := 襲われた人数優先順位付きキューは、 P3( 襲われた人数 , P( 残金 , ノード番号 ) ) としている。 #include <iostream> </iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1140&lang=jp 幅優先探索でスタート位置と汚れについて全点対間最短距離を求めておいて、パスを全部試す。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> #define INF 100000000 #define </queue></string></algorithm></vector></iostream>…

問題文 http://poj.org/problem?id=3692 最大クリーク問題。 二部グラフになっているので補グラフの最大独立集合を求める。 最大クリーク=補グラフの最大独立集合 が成り立つ。また二部グラフなら、 最大独立集合=頂点数-最大マッチング が成り立つ。 #inclu…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 Monge DP。 週刊spaghetti_sourceさんにわかりやすい説明があったので参考にしながら解いた。 http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915dp[ 左端 ][ 右端 ] := その…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1262無限にエネルギーのある車でレースをする。距離0の地点からスタートし、途中n個のチェックポイントがある。チェックポイントではタイヤの交換ができる。タイヤの交換にはb秒かかる。タ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1266 星と望遠鏡が与えられる。すべての望遠鏡を使って見える星の数を数えよ。 aとbをそれぞれ望遠鏡の方向ベクトルと星の位置ベクトルとすると、 cosθ=a•b/|a||b| θ=acos(a•b/|a||b|) で…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188&lang=jp 構文解析した。 数字は全部n/2+1して、括弧ではソートして小さい方から過半数とる。 #include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int now; string s; int num</algorithm></string></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580 座標圧縮した。 #include<iostream> #include<vector> #include<algorithm> #include<map> #define all(c) (c).begin(),(c).end() #define f first #define s second using namespace std; typedef long long ll; struct</map></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1175&lang=jp ビットDPで解いた。 dp[ 残っている円盤 ] := その状態がありえるかどうかcheckは円盤同士が重なっているかを判定する関数。 i countは立っているビットの数を数える関数。 #…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 ビットDPで解いた。 dp[ すでに置いたケーキ ][ ケーキの番号 ] := 横幅countは立っているビットの数を数える関数。 #include<iostream> #include<vector> #include<string> #include<cstdio> #include<cmath> #include<algorithm> #include<climits></climits></algorithm></cmath></cstdio></string></vector></iostream>…