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