模擬国内予選 2012
模擬国内予選2012がありました。3問解いて42位でした。本番は4問解けるように頑張りたいと思います。最初の20分くらい繋がらなくて問題文が見られないというアクシデントがありました。
問題B,Cはもう少し早く解けないとまずいなあ、と思いますが3問とも一発ACだったのは良かったと思います。本番もWAを出さないようにがんばります。
| Rank | Solved | Time | A | B | C | D | E | F | G |
| 42 | 3 | 4:11(15106) | 0:41 | 1:22 | 2:17 | - | - | - | - |
問題Aは簡単でした。適当にfor文を回して解きました。
問題Bはソートするだけ。
問題Cは構文解析 or 文字列置換です。文字列置換で解きました。
問題Dは線分の距離を求めてダイクストラ or ワーシャルフロイドです。
問題E以降は問題文をきちんと読んでいないのでノーコメントです。
問題A,B,Cまではきちんと練習していれば必ず解くことのできるいい問題セットだったと思います。問題Bの類似問題にはAOJ 1043や模擬国内予選2010 問題BのAOJ 2198があります。問題Cの類似問題には国内予選2008年問題CのAOJ 1155があります。
コードはあとで載せます。
開始0:00
コンテスト開始直後問題文が見られない状況が20分ちょっと続く...
iwi氏が問題文を公開、すかさず印刷(0:21)
問題A AC(0:41)
問題Aは簡単そうだけどちょっと面倒?
とか言いながらコードを書き始める。途中手が数分止まったりしたけど適当にコードかいて一発AC
問題 B AC(1:22)
問題Bはソートするだけだから簡単そう、とりあえずコードを書く。パラメータが多くて思ったよりコードを書くのに時間がかかってしまった。
問題 C AC(2:17)
問題Cを読む。「これは私の苦手な構文解析…、いやでもそんなに難しくないから頑張って構文解析しよう」とコードを書き始める。コードを書きながら、何を血迷ったか論理学の教科書を引っ張り出し真理値表を探し始めたが数分たって問題文に真理値表が書いてあることに気づく。コードを書いている途中で「ん？これ国内予選2008年の問題Cとほとんど同じだからあのときの文字列置換で解いたときのコード見ながらやればバグなしでコード書けそう」と思い途中で問題を解く方針を変える。かなり無駄に時間を浪費しつつデバッグしつつコードを書き終え一発AC!!
問題 Dを読む
問題Dを読み、幾何問題だけど線分間の距離求めて最短経路を求めるだけの簡単そうな問題に見えたので幾何のライブラリを見ながらつらつらとコードを書く。残り時間がなくなってきてコードを書き終える前にコンテスト終了時間に...。
と思いきやコンテスト時間が20分延長されたので続きのコードを書く。コードを書き終えたがsample inputが合わない。どこかがバグっているようなのでデバッグを続けたが20分でバグを潰せるはずもなくコンテスト終了、残念。
ソースコード
問題 A(AOJ:2399)#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ // n := 人数 int n; while( cin >> n , n ){ // s[i][j] := i が j さんの個人情報を知っているかどうか. int s[101][101] = {0}; for(int i=0 ; i < n ; i++ ){ int m; cin >> m; for(int j=0 ; j < m ; j++ ){ int p; cin >> p; p--; // i さんは p さんの個人情報を知っている. s[i][p] = 1; } } // k := 個人情報が漏洩した人数. int k; cin >> k; // L := 個人情報が漏洩した人の番号を保持する配列. vector<int> L(k); for(int i=0 ; i < k ; i++ ){ cin >> L[i]; L[i]--; } // ans := 個人情報を漏らした可能性のある人の番号を保持する配列. vector<int> ans; for(int y=0 ; y < n ; y++ ){ bool flag = true; // foo := y さんが知っている人の番号を保持する配列 vector<int> foo; for(int x=0 ; x < n ; x++ ){ if( s[y][x] ) foo.push_back( x ); } for(int i=0 ; i < L.size() ; i++ ){ // y さんは L[i] さんの情報を漏らした可能性がなければ flag を false にしておく. if( count(foo.begin(), foo.end(), L[i] ) == 0 ){ flag = false; } } // y さん が個人情報を漏らした可能性のある人なら ans に追加. if( flag ) ans.push_back( y ); } // 個人情報を漏らした可能性のある人物が一人だけならその番号を出力, そうでなければ -1 を出力. if( ans.size() == 1 ){ cout << (ans[0]+1) << endl; }else{ cout << -1 << endl; } } }
問題 B (AOJ:2400)
#include <iostream> #include <algorithm> #include <vector> #include <map> using namespace std; typedef pair<int,int> P; struct Score{ // problem[i] := 問題 i を解いたかどうか vector<bool> problem; // WA[i] := 問題 i のペナルティの数 vector<int> WA; // submit[i] := i 番目の提出して正解した時刻 vector<int> submit; }; int main(){ int t, p, r; while( cin >> t >> p >> r, t || p || r ){ // data[i] := チーム i のスコア vector<Score> data(t); // 初期化 vector<bool> problem_; vector<int> WA_; for(int i=0 ; i < p ; i++ ){ problem_.push_back( false ); WA_.push_back( 0 ); } for(int i=0 ; i < t ; i++ ){ data[i].problem = problem_; data[i].WA = WA_; } // 入力 for(int i=0 ; i < r ; i++ ){ int ID, pID, time; string message; cin >> ID >> pID >> time >> message; ID--; pID--; if( message == "CORRECT" ){ data[ID].problem[pID] = true; data[ID].submit.push_back( time ); }else{ data[ID].WA[pID]++; } } // ( -solved , (time, ID) ) を保持する配列 vector< pair<int,P> > ans; // 点数計算 for(int i=0 ; i < t ; i++ ){ // 解いた問題数 (ソートするときに解いた問題数が多い順になるように -1 をかけておく ) int solved = -data[i].submit.size(); // time の計算 (正解した問題の提出時刻の総和) int time=0; for(int j=0 ; j < data[i].submit.size() ; j++ ){ time += data[i].submit[j]; } // WA(ペナルティ) の加算 for(int j=0 ; j < p ; j++ ){ if( data[i].problem[j] ){ time += data[i].WA[j] * 1200; } } P pp(time,i); ans.push_back( pair<int,P> ( solved , pp ) ); } sort( ans.begin() , ans.end() ); for(int i=0 ; i < ans.size() ; i++ ){ int ID = (ans[i].second.second + 1); int solved = -ans[i].first; // 解いた問題数に -1 をかけて元に戻すのを忘れない. int time = ans[i].second.first; cout << ID << " " << solved << " " << time << endl; } } }
問題 C (AOJ:2401)
コンテスト中に書いた文字列置換で解くコードは構文解析より計算量が大きくなるので注意が必要です。
#include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; const int INF = 1e+8; // 変数 'a' - 'k' を value に置き換え void change(string& s, char x, char value){ for(int i=0 ; i < s.size() ; i++ ){ if( s[i] == x ) s[i] = value; } } // 式から "--" の除去 void minus_erase(string& s){ for(int i=1 ; i < s.size() ; i++ ){ if( s[i-1] == '-' && s[i] == '-' ){ s.erase( i-1 , 2 ); i = 0; } } } // 論理否定の計算 ("-F" => "T", "-T" => "F" の 文字列置換) void minus_calc(string& s){ for(int i=1 ; i < s.size() ; i++ ){ if( s[i-1] == '-' && s[i] == 'F' ){ s.replace( i-1 , 2 , "T" ); i = 0; }else if( s[i-1] == '-' && s[i] == 'T' ){ s.replace( i-1 , 2 , "F" ); i = 0; } } } // 論理和, 論理積, 論理包含の計算 (文字列置換) void calc(string& s){ string ex[12] = { "(F+F)", "(F+T)", "(T+F)", "(T+T)", "(F*F)", "(F*T)", "(T*F)", "(T*T)", "(F>F)", "(F>T)", "(T>F)", "(T>T)" }; string result[12] = { "F", "T", "T", "T", "F", "F", "F", "T", "T", "T", "F", "T" }; for(int i=0 ; i+4 < s.size() ; i++ ){ for(int j=0 ; j < 12 ; j++ ){ if( s.substr(i,5) == ex[j] ){ s.replace( i , 5 , result[j] ); i = -1; break; } } } } int main(){ string ex; while( cin >> ex ){ if( ex == "#" ) break; // "->" を ">" に置き換えておく string s; for(int i=0 ; i < ex.size() ; i++ ){ if( i+1 < ex.size() && ex[i] == '-' && ex[i+1] == '>' ){ s.push_back( '>' ); i++; }else{ s.push_back( ex[i] ); } } // '=' の左側を ex1, 右側を ex2 とする string ex1, ex2; bool flag = false; for(int i=0 ; i < s.size() ; i++ ){ if( s[i] == '=' ){ flag = true; }else if( flag ){ ex2.push_back( s[i] ); }else{ ex1.push_back( s[i] ); } } // 登場する変数('a' - 'k')をチェック int f[256] = {0}; for(int i= 0 ; i < s.size() ; i++ ){ f[ s[i] ] = 1; } vector<char> vc; for(char c = 'a' ; c <= 'k' ; c++ ){ if( f[c] ){ vc.push_back( c ); } } // N := 登場する変数の種類. int N = vc.size(); // 変数の置き換えを 2^N 通り試し すべての式の評価で右辺と左辺が等しいか調べる. bool ans = true; for(int bits = 0 ; bits < (1<<N) ; bits++ ){ string ex1_ = ex1; string ex2_ = ex2; // 変数を "T" or "F" に置き換えておく for(int i=0 ; i < N ; i++ ){ // i 番目の文字を'T' か 'F'にしておく if( bits & (1<<i) ){ change( ex1_ , vc[i] , 'T' ); change( ex2_ , vc[i] , 'T' ); }else{ change( ex1_ , vc[i] , 'F' ); change( ex2_ , vc[i] , 'F' ); } } // "--" の除去 minus_erase( ex1_ ); minus_erase( ex2_ ); // 式 ex1 が "T" か "F" になるまで文字列置換を繰り返す. bool minus_flag = true; while( ex1_.size() > 1 ){ minus_calc( ex1_ ); calc( ex1_ ); } // 式 ex2 が "T" か "F" になるまで文字列置換を繰り返す. while( ex2_.size() > 1 ){ minus_calc( ex2_ ); calc( ex2_ ); } // 式 ex1 と 式 ex2 が等しいかどうか if( ex1_ != ex2_ ){ ans = false; break; } } // 出力 if( ans ){ cout << "YES" << endl; }else{ cout << "NO" << endl; } } }
問題 D (AOJ:2402)
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <complex> using namespace std; // XY座標 #define X real() #define Y imag() const double EPS = 1e-6; const double INF = 1e+12; const double PI = acos(-1.0); typedef complex<double> P; // 内積(dot product) a・b = |a||b|cosθ double dot(P a, P b){ return real( conj(a) * b ); } // 外積(cross product) |a×b| = |a||b|sinθ double cross(P a, P b){ return imag( conj(a) * b ); } // 度からラジアンに変換する. double to_rad(double deg){ return deg * PI / 180.0; } // 原点を軸に点 p を a ラジアンだけ回転した点を返す. P rot(P p, double a){ double x = p.X * cos(a) - p.Y * sin(a); double y = p.X * sin(a) + p.Y * cos(a); return P(x,y); } // 点 a を軸に点 b を angle ラジアンだけ回転した点を返す. P rot2(P a, P b, double angle){ P p = b - a; return rot( p , angle ) + a; } // CCW : 反時計回り (Counter Clock Wise) // CW : 時計回り (Clock Wise) enum {CCW=1, CW=-1, ON=0}; // * 3点がどちら回りであるか返す, 3点が1直線に乗っているときは ON を返す int ccw(const P &a, P b, P c) { b-=a, c-=a; if( cross(b,c) > EPS ) return CCW; // CCW : 反時計回り if( cross(b,c) < -EPS ) return CW; // CW : 時計回り if(dot(b, c) < -EPS ) return +2; // c--a--b on line if(dot(b, b) + EPS < dot(c, c) ) return -2; // a--b--c on line ??? return ON; } // 線分クラス struct Segment{ P a, b; Segment(P a_, P b_){ a = a_; b = b_; } // 点 p と線分の距離を返す. double distance(P p){ if( dot(b-a,p-a) < EPS ) return abs(p-a); if( dot(a-b,p-b) < EPS ) return abs(p-b); return abs( cross(b-a,p-a) ) / abs(b-a) ; } // 線分 s と交差しているかどうかを返す. bool is_intersection(const Segment& s){ return ( ccw(a, b, s.a) * ccw(a, b, s.b) <= 0 && ccw(s.a, s.b, a) * ccw(s.a, s.b, b) <= 0 ); } // 点 p が線分上にあるかどうか bool contain(P p) { return (abs(a-p) + abs(p-b) < abs(a-b) + EPS); } // 線分と線分の距離 double distance(Segment s) { if( is_intersection(s) ) return 0.0; return min( min(distance(s.a), distance(s.b)), min(s.distance(a), s.distance(b)) ); } // デバッグ出力 void print(){ printf("line(%f,%f,%f,%f);\n", a.X ,a.Y, b.X, b.Y ); } }; int main(){ // n := 星の数, m := スタート, l := ゴール int n, m, l; while( scanf("%d %d %d", &n, &m, &l) , n || m || l ){ m--; l--; // v[i] := i 番目の星 (5つの線分) vector< vector<Segment> > v; for(int i=0 ; i < n ; i++ ){ int x, y, a, r; scanf("%d %d %d %d", &x, &y, &a, &r ); double angle = to_rad( a + 90 ); P p1( x + r*cos(angle) , y + r*sin(angle) ); P p2 = rot2( P(x,y) , p1 , to_rad(72) ); P p3 = rot2( P(x,y) , p2 , to_rad(72) ); P p4 = rot2( P(x,y) , p3 , to_rad(72) ); P p5 = rot2( P(x,y) , p4 , to_rad(72) ); // vs := 5 つの線分 vector<Segment> vs; vs.push_back( Segment(p1,p3) ); vs.push_back( Segment(p3,p5) ); vs.push_back( Segment(p5,p2) ); vs.push_back( Segment(p2,p4) ); vs.push_back( Segment(p4,p1) ); v.push_back( vs ); } // 初期化 double G[101][101]; for(int i=0 ; i < 101 ; i++ ){ for(int j=0 ; j < 101 ; j++ ){ G[i][j] = (i == j)? 0 : INF; } } // 任意 i 番目と j 番目の星の距離の計算 (線分の距離の計算) for(int i=0 ; i < v.size() ; i++ ){ for(int j=i+1 ; j < v.size() ; j++ ){ double d = INF; for(int k1 = 0 ; k1 < v[i].size() ; k1++ ){ for(int k2 = 0 ; k2 < v[j].size() ; k2++ ){ Segment s1 = v[i][k1]; Segment s2 = v[j][k2]; d = min( d , s1.distance(s2) ); } } G[i][j] = G[j][i] = d; } } // ワーシャルフロイド法で最短経路を求める for(int k=0 ; k < n ; k++ ){ for(int i=0 ; i < n ; i++ ){ for(int j=0 ; j < n ; j++ ){ G[i][j] = min( G[i][j] , G[i][k] + G[k][j] ); } } } // 答えの出力 printf("%.8f\n", G[m][l] ); } }
