鎖中経路※コンテスト本番の入力が通るかどうかは未確認サンプルの図を見ると、最短経路は、両端の円の中心といくつかの円の交点を直線で結べば得られることがわかる。一方の円の中心からそれぞれの交点に到達するまでの最短経路を覚えておき、動的計画法。交…

鉄道乗り継ぎ各会社ごとに全点対間最短路を求め、運賃を計算する。この運賃を使って、出発地から目的地の最安運賃を求める。 #include <iostream> #include <vector> #include <queue> #include <utility> using namespace std; int main() { const int INF = 99999999; while ( true ) { int n</utility></queue></vector></iostream>…

偏りのあるサイコロ #include <iostream> #include <vector> #include <cstdlib> using namespace std; // サイコロDを回転したサイコロを返す vector<int> spin( vector<int> D, int dir ) { vector<int> R; int T[4][6] = { { 3, 0, 2, 5, 4, 1 }, { 4, 1, 0, 3, 5, 2 }, { 1, 5, 2, 0, 4, 3 }, { 2, </int></int></int></cstdlib></vector></iostream>…

繰り返す10進数 #include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; int next( int a, int L ) { vector<int> T(L); for ( int i=0; i</int></algorithm></set></vector></iostream>

ミレニアム #include <iostream> using namespace std; int main() { int n; cin >> n; for ( int i=0; i<n; i++ ) { int Y, M, D; cin>>Y>>M>>D; int ans = 0; while (Y<1000 ) { D++; if ( Y%3==0 && D>20 || Y%3!=0 && M%2==0 && D>19 || Y%3!=0 && M%2!=0 && D>20 ) { D = 1; M++; } if ( M>10 )</n;></iostream>…

Problem C ポロック予想動的計画法。和がnになる正四面体数の最小個数をAnとし、n以下の正四面体数の集合をT(n)とすると、 An = mint∈T(n)(An-t+1)。 奇数のみの場合も同様。 #include <iostream> using namespace std; int main() { const int N = 1000000; static in</iostream>…

Problem B 迷図と命ず幅優先探索。こういう入力の時は文字列のまま持っておくと楽らしい。 #include <iostream> #include <vector> #include <string> using namespace std; int main() { const int dirx[4] = { 1, 0, -1, 0 }; const int diry[4] = { 0, 1, 0, -1 }; while ( true ) {</string></vector></iostream>…

Problem A 角角画伯，かく悩みき問題とジャッジデータは↓ 国内予選問題 | ACM-ICPC: ACM International Collegiate Programming Contest Asia Regional Contest 2010 in Tokyo各タイルの位置を覚えておけば良い。 #include <iostream> #include <vector> #include <algorithm> using names</algorithm></vector></iostream>…

Problem E 最強の呪文動的計画法。各ノードiについてそれぞれの長さlの呪文で最強のものを覚えておく。そのような呪文をSi,lとすると、 Si,l = mins∈{t|yt=i}(Sxs,l-|labs|+labs) が成り立つ。と、 id:pes_magic が言っていた。最強の呪文が存在しない２つめ…

Problem D ぐらぐら問題文の通りに計算するだけ。だが、面倒くさい。 #include <iostream> #include <vector> #include <string> using namespace std; int main() { while ( true ) { // 入力 int w, h; cin >> w >> h; if ( w == 0 && h == 0 ) break; vector<string> elev( h ); for ( int i</string></string></vector></iostream>…