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

Bridge

グラフ構造において強連結を求めて処理することは多いけど、 蟻本に載っているタイプのScc*1だと後の処理が結構使い辛い気がしてた。 単にSccするだけならば別に良いんだけど、辺に対して操作をする時、 その辺は強連結をするための辺なのか強連結成分同士を…

codeforces Round #176

1/22(木) TPC練習会 A問題 Problem - A - Codeforcesめっちゃ汚い #include<iostream> #include<string> using namespace std; int main() { string in[4]; for(int i=0;i<4;i++){ cin >> in[i]; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ int cnt = 0, cnt2 = 0; if(in[</string></iostream>…

SRM 626 div2

250 class SumOfPower { public: int findSum( vector <int> array ) { vi v(array); int sum = 0; for(int i=1;i<=v.size();i++){ for(int k=0;k<v.size();k++){ if(k+i > v.size())continue; for(int j=k;j</v.size();k++){></int>

AOJ 2200 Mr. Rito Post Office

問題文 日本語なので省略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200 解法 動的計画法 dp[i][j] : i番目まで集配するとき、船をjに泊めていた場合にかかる最小のコスト 陸と海の距離に関してはWarshall-Floydで求めた。 ただ、Dijkstra…

AOJ 0562 Shopping in JOI Kingdom

概要 日本語の問題なので省略させていただきます。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0562最近AOJがWAのデータとか見せてくれるのでありがたいですね。 解法 まず各ショッピングモールのある町からダイクストラ法を用いてすべての町…

AOJ 0537 Bingo

概要 日本語の問題なので省略させていただきます。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537 解法 動的計画法です。dp[i][j]i:マスの番号(左上から順に振ったとき)j:i番目までの値の合計というDPテーブルでソースコードのように回すだ…

AOJ 0540 Amidakuji

概要 日本語の問題なので省略させていただきます。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0540 解法 各横棒の両端に対して上にたどっていった時にたどり着く番号と下にたどっていった時の得点を先に求めておきます。そうすることでもしi…

AOJ 0531 Paint Color

概要 日本語の問題なので省略させて頂きます。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531 解法 幅 w (1 ≤ w ≤ 1000000 となる整数) と高さ h (1 ≤ h ≤ 1000000 となる整数)とあるので当然普通にやったら要素数が足りません。座標圧縮 …

AOJ 0568 Pasta

概要 日本語問題なので省略させていただきます。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568 解法 動的計画法dp[i][j][k] i日目のパスタがj。i+1日目のパスタがkのときのパターン数その日のパスタがtの場合にはdp[i][t][1〜3]のみを更新…

poj 1661 Help Jimmy

3ヶ月くらいぶりに更新なのでは・・・(困惑) スペランカー? 概要 ジミーさんが地面まで降りたいので初期位置(y,x) 落ちることのできる最大の高さ 途中に浮かぶ謎の板の情報が与えられたとき、ジミーさんが地面にたどり着くまでの最短の時間を求める。注意し…

aoj 0574 Nails

概要 日本語の問題なので省略させていただきます。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0574 解法 各点にたいして配列を準備するh[5000][5000]しかし5000*5000とか余裕で配列足りないのでh[12512502]と一つでくくる(このへんの大きさ…