情報オリンピック 2009本選 解答 公式のページはJOI 2008-2009 本選 問題・データ 前回Q1~Q3を解いたときの記事は『Volume 5 / 0538->0540（2009年11月28日）』 Problem 0540 : Amidakuji / 4: あみだくじ むずかしかった。解説見ても解くのに手間取った。 …

ACM/ICPC国内予選突破の手引き”Step by step”の難易度：☆☆☆ ４つ目から終わりまで。 下から2番目の”Non-Stop Travel”はAOJで見つからなかった上に問題文が英語なので、見なかったことにした。 ともあれ、これで”Step by step”は終わり。がんばった！ あとはJ…

ACM/ICPC国内予選突破の手引き”Step by step”の難易度：☆☆☆ スタート。 Problem 2008 : Dragon Fantasy 難易度 : ☆☆☆ 種類 : 探索 解説見てやっとできた。 (double) したがって、==の場合に対応するために if( dist( c[i].x-d.x, c[i].y-d.y ) < new_t + 1e-…

ACM/ICPC国内予選突破の手引き”Step by step”の難易度：☆☆終わり。 Problem 1131 : Unit Fraction Partition 難易度 : ☆☆ 種類 : 探索 分母の組み合わせを試していく。 でも、はじめさっぱりだった。解説を見てから実装。 #include <iostream> using namespace std; in</iostream>…

Problem 1130 : Red and Black 難易度 : ☆☆ 種類 : 再帰 深さ優先探索。 #include <iostream> using namespace std; #define MAX 20 bool map[MAX+2][MAX+2]; int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 }; int w, h; int count( int x, int y ) { int cnt =</iostream>…

（『ACM/ICPC国内予選突破の手引き』をやってみる（１）に引き続きACM/ICPC国内予選突破の手引きの”Step by step”。 これで”Step by step”の難易度：☆がすべて終了。 Problem 1119 : Exploring Caves 難易度 : ☆ 種類 : シミュレーション 入力ごとに座標移動…

解説がしっかりあって、難易度別、ジャンル別に体系付けられているACM/ICPC国内予選突破の手引きの問題を解いてみようと思います。まずは”Step by step”から。 Problem 1129 : Hanafuda Shuffle 難易度 : ☆ 種類 : シミュレーション ベクターでカードの番号…

情報オリンピック 2006予選 解答 Problem 0500 : Card Game 問題通りに実装するだけ。 #include <iostream> using namespace std; int main(void) { int n, point_a, point_b, a, b; while( cin >> n, n!=0 ){ point_a = point_b = 0; for( int i=0; i<n; i++ ){ cin >> a >> b; if( a </n;></iostream>…

情報オリンピック 2007予選 解答 Problem 0525 : Osenbei 公式の解説のまんま。 #include <iostream> #include <vector> using namespace std; // 数え上げ int countUp( vector< vector<int> > src ) { int i, j, cnt, result = 0; for( j=0; j</int></vector></iostream>

情報オリンピック 2009本選 解答 難しい……。データが大きくなるとダメダメ。 Problem 0538 : IOIOI / IOIOI BM法でやると時間切れになる。愚直にカウントして解いた。 #include <iostream> using namespace std; int main(void) { int n, m, cnt, result, i, j; char c</iostream>…

情報オリンピック 2006予選 解答 Problem 0515 : School Road / 通学経路 高1で習った数学Aにあるような、碁盤目状に繋がっている点間の最短経路の数を求める問題。 深さ優先で解くと時間切れでアウト。 (x,y)までの最短経路の数 = (x-1,y)までの最短経路 + …

情報オリンピック 2006予選 解答 Problem 0510 : Score / 得点 足して、大きいほうを表示するだけ。 #include <iostream> using namespace std; int main(void) { int s, t, i, input; s = t = 0; for( i=0; i<4; i++ ){ cin >> input; s += input; } for( i=0; i<4; i</iostream>…

情報オリンピック 2007予選 解答 Problem 0526 : Boat Travel / 船旅 最短経路問題。 新しい運行情報がある度に、そこを経由する経路を更新する。 #include <iostream> #include <vector> using namespace std; vector< vector<int> > p; void refresh( int n, int a, int b ){ int </int></vector></iostream>…

情報オリンピック 2007予選 解答 Problem 0524 : Searching Constellation / 星座探し 星座のある点を基準点とおいて、基準点-その他の点間の距離を保存。（dis_m[0..m-1]） 与えられた星のおのおのの座標（pos_n[0..n-1]）について、↑の距離を足したところ…

情報オリンピック 2007予選 解答 Problem 0521 : Change / おつり 大きい硬貨から引いていく。 #include <iostream> using namespace std; int main(void) { int n, i, cnt; int table[6] = { 500, 100, 50, 10, 5, 1 }; while( cin >> n, n!=0 ){ n = 1000 - n; cnt =</iostream>…

情報オリンピック 2008予選 解答 Problem 0536 : Shuffle / シャッフル 安直に配列を使ってシミュレーションしようとすると、配列が確保できなくなってRuntime Errorが出る。カードの数10^9とかだもの。 で、情報オリンピックのサイトの解説見ても実装の仕方…

情報オリンピック 2008予選 解答 Problem 0532 : Time Card / タイムカード #include <iostream> using namespace std; int main(void) { int h1, h2, m1, m2, s1, s2, t; for( int i=0; i<3; i++ ){ cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2; t = (h2*60*60+m2*60+s2</iostream>…

Problem 0148 : Candy and Class Flag #include <iostream> #include <iomanip> using namespace std; int main(void) { int n; while( cin >> n ){ cout << "3C"; cout.width(2); cout.fill('0'); if( n%39 ) cout << n%39 << endl; else cout << 39 << endl; } return 0; } Pr</iomanip></iostream>…

Problem 0181 : Persistence パソコン甲子園2008予選 問題09 こだわり #include <iostream> #include <vector> #include <limits.h> using namespace std; int m, n; vector<int> bw; vector< vector<int> > bsw; int calc() { int new_val; int i, j, k; for( i=1; i<=n; i++ ) bsw[1][i] = bw[i];</int></int></limits.h></vector></iostream>…

パソコン甲子園2008本選 解答 Problem 0191 : Baby Tree a（1...m）回目に肥料i（0...n-1）を投入したときの最大成長率を記録していって、最終的にm回目で成長率が最大のものを出力する。 #include <iostream> #include <iomanip> #include <vector> #include <limits.h> using namespace std; str</limits.h></vector></iomanip></iostream>…

Problem 0144 : Packet Transportation 有向グラフの最短経路を求める問題。 ワーシャル-フロイド法で解いた。 #include <iostream> #include <vector> using namespace std; #define MAX 9999 int n; vector< vector<int> > rtr; void Floyd(){ int i, j, k, l; for( i=1; i<=n; i+</int></vector></iostream>…

Problem 0139 : Snakes 頭→尻尾＆全身の長さ→中身の順で判定。 #include <iostream> #include <string> using namespace std; void checkA( string str ){ int length = str.size(); if( str[length-1] != '~' || length == 4 ){ cout << "NA" << endl; return; } int i, cnt =</string></iostream>…

パソコン甲子園2006本選 解答 Problem 0136 : Frequency Distribution of Height これまでSuccess:100%だったから、Submitするとき無駄に緊張した。 僕が失敗すると100％じゃなくってしまうわけで……。 #include <iostream> using namespace std; int main(void) { int </iostream>…

パソコン甲子園2006本選 解答 Problem 0133 : Rotation of a Pattern #include <iostream> using namespace std; int main(void) { char patt[8][8], tmp[8][8]; int i, j; for( i=0; i<8; i++ ){ for( j=0; j<9; j++ ){ patt[i][j] = cin.get(); } } cout << "90" << </iostream>…

パソコン甲子園2007本選 解答 Problem 0169 : Blackjack ブラックジャックの点数計算。 1の枚数を数えといて、1にするか11にするかはあとで計算。 #include <iostream> using namespace std; int main(void) { int point, card, one_flag, i; char ch; while( cin.get(</iostream>…

パソコン甲子園2007本選 解答 Problem 0166 : Area of Polygon（未） "Wrong Answer" 円に内接する多角形の面積比較。 多角形は三角形の集合だから、(三角形の面積)=0.5*r*r*sin(v)を足しこめば多角形の面積が出るはず…。 #include <iostream> #include <cmath> #define PI 3.</cmath></iostream>…

パソコン甲子園2007本選 解答 Problem 0158 : Collatz's Problem #include <iostream> using namespace std; int collatz( int num ) { if( num == 1 ) return 0; if( num%2 == 0 ) return 1+collatz(num/2); else return 1+collatz(num*3+1); } int main(void) { int </iostream>…

2008年本選 解答 Problem 0183 : Black-and-White #include <iostream> using namespace std; int main(void) { char board[3][3], ch, center; int i, j; while( cin.get(ch) ){ if( ch == '0' ) break; else cin.putback(ch); for( i=0; i<3; i++ ){ for( j=0; j<3; </iostream>…

パソコン甲子園2008予選 解答 Problem 0173 : Haunted House #include <iostream> #include <string> using namespace std; int main(void) { int am, pm; string className; for( int i=0; i<9; i++ ){ cin >> className >> am >> pm; cout << className << " " << am+pm << "</string></iostream>…

Problem 0035 : Is it Convex? パス。 Problem 0036 : A Figure on Surface 長くなっちゃった。 #include <iostream> using namespace std; int main(void) { int pat[7][4][4] = { {{0,0,0,0}, {0,1,1,0}, {0,1,1,0}, {0,0,0,0}}, {{0,1,0,0}, {0,1,0,0}, {0,1,0,0}, </iostream>…