TheProduct動的計画法。最後が numbers[i] である k 個の数字の積が取りうるのは、最後が numbers[i-maxDist]〜numbers[i-1] である k-1 個の数字の積に numbers[i] を乗じた値。各マスでは正負それぞれ絶対値が最小・最大であるものだけ記憶しておけばよい…

Div 1の250と同じ。

クラス定義とか入力例をコピペするのが面倒になってきたので、プラグインを導入した。定番らしいCodeProcessor+TZTester+FileEdit。テンプレートはこんな感じ。 #include <iostream> #include <string> #include <vector> using namespace std; class $CLASSNAME$ { public: $RC$ $METH</vector></string></iostream>…

ToolsBox #include <sstream> #include <vector> #include <set> using namespace std; class ToolsBox { public: int countTools( vector<string> need ) { set<string> tool; for ( int i=0; i<(int)need.size(); i++ ) { stringstream s( need[i] ); string t; while ( s >> t ) tool.insert( t </string></string></set></vector></sstream>…

PlanarGraphShop動的計画法。c 個のグラフで n コインとなるなら、c+1 個のグラフの組み合わせで n+1, c+8, c+9, c+27, ……コインを作れる。 グラフが平面グラフとなる条件はWikipediaより、 Gが平面的グラフならば、|E(G)|≦3|V(G)|-6。ただし、|V(G)|≧3。X=2…

MazeMaker１日勘違いしてて、参加し損ねた。ぐぬぬ。 #include <vector> #include <string> using namespace std; class MazeMaker { public: int longestPath( vector<string> maze, int startRow, int startCol, vector<int> moveRow, vector<int> moveCol ); }; int MazeMaker::longestPath(</int></int></string></string></vector>…

Packets1x1と2x2の隙間をカウントしながら大きい順に置いていく。 #include <iostream> using namespace std; int main() { while ( true ) { int p[7]; for ( int i=1; i<=6; i++ ) cin >> p[i]; int num = 0; int s1 = 0; int s2 = 0; // 6 num += p[6]; // 5 num +=</iostream>…

TheTournamentDivOne勝ち点 w と引き分け点 d を合計が points になるように各チームに振り分けると考える。ただし、d は異なる２チームに同時に与えなければならない。各チームの引き分け数は、合計が偶数であり、引き分け数最大のチームの引き分け数が他の…

TheSoccerDivTwoチームをチーム0が順位で勝てないチーム、そのチームが負ければチーム0が勝てるチーム、そのチームが引き分ければチーム0が勝てるチーム、勝敗に関係無くチーム0が勝てるチームに分けて、g1, g2, g3, g4とする。なるべくg2が負けて、g3が引き…

TheBasketballDivTwo #include <vector> #include <string> #include <algorithm> using namespace std; class TheBasketballDivTwo { int n; vector<string> t; int play( int p ); public: int find( vector<string> table ); }; int TheBasketballDivTwo::find( vector<string> table ) { n = (int)table.size</string></string></string></algorithm></string></vector>…

TheTournamentDivTwo #include <vector> #include <numeric> using namespace std; class TheTournamentDivTwo { public: int find( vector<int> points ) { int sum = accumulate( points.begin(), points.end(), 0 ); return sum%2==0 ? sum/2 : -1; } };</int></numeric></vector>

Numbers That Count #include <iostream> #include <string> using namespace std; string invent( string w ); int main() { string w; while ( cin >> w && w != "-1" ) { string seq[16] = { w }; for ( int i=1; i<=15; i++ ) seq[i] = invent( seq[i-1] ); int j, k; for </string></iostream>…

Jury Compromise動的計画法の使い方がわかってきた。 D(J)-P(J) の取り得る値が高々±20nなので、m人の候補を組み合わせて D(J)-P(J)=i となりうるかどうかを表の i 番目のセルに持つ。複数ある場合は D(J)+P(J) が最大となるようにすることで、最適な組み合…

TheBasketballDivOneチーム数 n≦5 なので試合結果 3n(n-1)/2 は最大59049通り。全パターン試す。 #include <iostream> #include <set> #include <vector> using namespace std; class TheBasketballDivOne { public: int find( int n, int m ); }; int TheBasketballDivOne::find( i</vector></set></iostream>…

Dividing与えられたビー玉を組み合わせて合計の半分の価値にできるか、ということと等価。 ビー玉の価値の合計が高々120000ということに着目して動的計画法で解く。価値m以下のビー玉を組み合わせて価値iを作れるかどうかを表に持つ。そのまま実装すると制限…

Counterfeit Dollar12枚のコインそれぞれが軽い・重いと仮定し、矛盾がないか調べる。 #include <iostream> #include <string> using namespace std; int main() { int n; cin >> n; string info[] = { "down", "even", "up" }; for ( int i=0; i<n; i++ ) { string weight[3][3]; for ( int j=0; j<9; j++ ) cin >> weight[0][j]; for ( char c=</n;></string></iostream>…

Faulty Odometer 要は、012356789の9文字を使った9進数を読み込むだけ。 #include <iostream> #include <string> using namespace std; int main() { int map[] = { 0, 1, 2, 3, 0, 4, 5, 6, 7, 8 }; string s; while ( cin >> s && s[0] != '0' ) { int mile = 0; for ( int i</string></iostream>…

Joseph とりあえず書いてみたプログラムだとTLEになるけどkの幅が小さいので、↓のプログラムで全ての場合を計算し、 #include <iostream> #include <vector> using namespace std; int main() { for ( int k=1; k<14; k++ ) //int k; //while ( cin >> k && k > 0 ) { int m; f</vector></iostream>…

Sticks Time Limit Exceedを回避することができず、諦めてカンニング。ShortCoding本に載っていた。著者のサイトにも250Bまでは。書き方は違うけど、やっていることは同じだよなと首を捻ったが、バグで一部枝刈りが働いていなかった。 枝刈り 長い順に試して…

STAMPS 可能な切手の組み合わせをバックトラックで生成する。 コードが長くなってくるとバグが増える……。 #include <iostream> #include <algorithm> #include <vector> using namespace std; vector<int> stamp, custom; vector<int> number; // number of each stamps int type; // number of diff</int></int></vector></algorithm></iostream>…

今現在、私はイエローに最も近い日本人だそうだ。先輩に教えてもらった。 黄色になりたい。

Maya Calendar 月名をコピペするときにスペースが入ったせいで、Presentation Errorが出て悩んだ。 #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { // month names of Haab string hmonth[19] = { "pop", "no", "zip", "zotz", "tzec", "</algorithm></string></iostream>…

DNA Sorting #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; bool cmp( string a, string b ); int sortedness( string s ); int main() { int n, m; cin >> n >> m; vector<string> dna(m); for ( int i=0; i<m; i++ ) cin >> dna[i]; sort( dna.begin(), dna.end(</m;></string></string></algorithm></vector></iostream>…

Biorhythms #include <iostream> using namespace std; int main() { for ( int c=1; ; c++ ) { int p, e, i, d; cin >> p >> e >> i >> d; if ( p == -1 ) break; for ( int j=1; j<=21252; j++ ) { if ( ( j + d - p ) % 23 == 0 && ( j + d - e ) % 28 == 0 && ( j </iostream>…

I Think I Need a Houseboat #include <iostream> #define _USE_MATH_DEFINES #include <math.h> using namespace std; int main() { int n; cin >> n; for ( int i=1; i<=n; i++ ) { double x, y; cin >> x >> y; double r = sqrt( x*x + y*y ); double area = M_PI/2 * r*r; </math.h></iostream>…

Financial Management #include <stdio.h> int main() { double sum = 0; for ( int i=0; i<12; i++ ) { double m; scanf( "%lf", &m ); sum += m; } printf( "$%.2f\n", sum / 12 ); return 0; }</stdio.h>

Hangover #include <iostream> using namespace std; int main() { double l; while ( cin>>l, l>0 ) { double d = 0; int n; for ( n=1; ; n++ ) { d += 1. / (n+1); if ( d > l ) break; } cout << n << " card(s)" << endl; } return 0; }</iostream>

487-3279 #include <iostream> #include <string> #include <map> using namespace std; string normalize( string num ); int main() { int n; cin >> n; map<string,int> count; for ( int i=0; i<n; i++ ) { string num; cin >> num; string stand = normalize( num ); count[stand] += 1; } bool dup = false; for ( ma…</n;></string,int></map></string></iostream>

Java('A`)ﾜｶﾝﾈ Exponentiation import java.util.Scanner; import java.math.BigDecimal; class Main { public static void main( String[] args ) { Scanner s = new Scanner( System.in ); while ( s.hasNext() ) { String R = s.next(); int n = s.nextIn…

A+B Problem #include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << a+b << endl; return 0; }</iostream>