Codeforces Beta Round #18 (Div. 2)
参戦しました。
Div.2 Onlyに出るということは、まぁそういうことです。
・・・(ノд<。)゜。ｸｽﾝ
で、とりあえず結果から。
Ａ ： WA*1 → Accepted
Ｃ ： Accepted
Ｂ ： PE*2 → TLE*3 → Accepted
Ｄ ： WA
で、3問正解、最終順位は32位、レーティングは 1491 => 1577 となりました。
やたー！
青に復帰だよ〜！
あ、ちなみにＡの後ＢやらずにＣにとりかかったのは、そのとき正解者数を見たらＣの方が多かったのでＢを開いたけどすぐにＣにとりかかったからです。
経緯
ちなみにCodeforcesに出るのはこれが初めてではありません。
既に何回も出てますし、SRMなんかにも参戦してます。
普段はこういうことを書くのが面倒なのであまり需要がないかなと思って書かないんですが、
ということで、書くことにしました。
そこそこ需要があるなら今後もCodeforces、SRMともに書いていこうかと思ったり思わなかったり・・・ ←
Ａ．Triangle
ということで自分が解けた問題の分かる範囲で解説します。
問題の本文はCodeforcesを参照願います。
問題
Ａの問題は簡単に説明すると
平面上の3つの点(x1,y1),(x2,y2),(x3,y3)が与えられる。
このとき直角三角形であれば"RIGHT"と、x1,y1,x2,y2,x3,y3のうち1だけ動かしたときに直角三角形になるのであれば"ALMOST"と、それ以外の場合は"NEITHER"と出力せよ。
ということです。
解法
垂直かどうかが判定出来ればそれを用いて直角三角形かどうかを調べ、直角三角形でなければx1,y1,x2,y2,x3,y3を1だけ動かした状態の点を作り同様に垂直かの判定を行い、どれにも引っかからなければそれ以外と判断出来ますね。
ではどうやって垂直かどうかを判定するか。
垂直かどうかの判定には内積を使いましょう。
3つのうちの1つを基準にし、残りの2つの点への方向ベクトルを求めます。
次に、この2つのベクトルの内積をとります。
この内積の結果が0であればその2つのベクトルは垂直であることがわかります。
これでなんとか書けそうですね。
注意点
問題には3点で描ける三角形の大きさは0でないと明示されてます。
つまり、与えられた3点のうち2つ以上が同じ点ということはありません。
しかし、1移動させたときに同じ点になってしまうことがあります。
よって内積が0になったからといって垂直であるとは限らない点に注意です！
私がWAを出したのはこのことを考えてなかったからです。。。orz
解答例
書きなおすのが面倒なので実際のコンテスト中に投げたソースを載せておきます。
#include <cstdlib> #include <cmath> #include <map> #include <utility> #include <set> #include <sstream> #include <iostream> #include <iterator> #include <string> #include <vector> #include <list> #include <algorithm> #include <functional> #include <stack> #include <queue> using namespace std; #define mp make_pair #define pb push_back #define sz(x) ((x).size()) #define For(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) For(i,0,(n)) #define all(v) (v).begin(),(v).end() struct Coord { int x; int y; bool nz( void ) { if( x && y ) return true; return false; } int operator*( const Coord & c ) { return x * c.x + y * c.y; } Coord operator-( const Coord & c ) { Coord tmp; tmp.x = x - c.x; tmp.y = y - c.y; return tmp; } }; int main( void ) { Coord c[3]; rep( i, 3 ) cin >> c[i].x >> c[i].y; { Coord c1, c2; c1 = c[1] - c[0]; c2 = c[2] - c[0]; if( !( c1 * c2 ) ) { cout << "RIGHT"; return 0; } c1 = c[0] - c[1]; c2 = c[2] - c[1]; if( !( c1 * c2 ) ) { cout << "RIGHT"; return 0; } c1 = c[0] - c[2]; c2 = c[1] - c[2]; if( !( c1 * c2 ) ) { cout << "RIGHT"; return 0; } } rep( i, 3 ) { rep( j, 12 ) { Coord tmp[3]; Coord c1, c2; rep( k, 3 ) tmp[k] = c[k]; switch( j ) { case 0: tmp[0].x--; break; case 1: tmp[0].x++; break; case 2: tmp[1].x--; break; case 3: tmp[1].x++; break; case 4: tmp[2].x--; break; case 5: tmp[2].x++; break; case 6: tmp[0].y--; break; case 7: tmp[0].y++; break; case 8: tmp[1].y--; break; case 9: tmp[1].y++; break; case 10: tmp[2].y--; break; case 11: tmp[2].y++; break; } c1 = tmp[1] - tmp[0]; c2 = tmp[2] - tmp[0]; if( !( c1 * c2 ) && c1.nz() && c2.nz() ) { cout << "ALMOST"; return 0; } c1 = tmp[0] - tmp[1]; c2 = tmp[2] - tmp[1]; if( !( c1 * c2 ) && c1.nz() && c2.nz() ) { cout << "ALMOST"; return 0; } c1 = tmp[0] - tmp[2]; c2 = tmp[1] - tmp[2]; if( !( c1 * c2 ) && c1.nz() && c2.nz() ) { cout << "ALMOST"; return 0; } } } cout << "NEITHER"; }
はい、汚いですね・・・
だって、書きながら考えてるからどうしてもこうなるんだもん＞＜ ←
ちなみに最後のiのループは不要です。
書いてる途中でやり方が変わったため不要になったのですが、そんな消してる余裕もないし、そんな時間があったら次の問題にいった方がいいので放置しました。
ちなみに、ちゃんとこれで通りました。
まぁ、今時のコンピュータだったらこれぐらい問題ないよね！
Ｂ．Platforms
問題
1次元上（つまりある直線上）で0を開始点とし、幅dの間隔で+方向にジャンプを行う。
この1次元上にはn個の足場があり、k番目の足場は[(k-1)m, (k-1)m+l]の区間にある。
このとき、足場に乗れず落ちる点はどこか？
解法
要はジャンプを繰り返していき、一番最初に区間外になる点を探せばいいだけです。
よって、条件としては区間外かどうかとなります。
さらに、区間外でも考えるのはあるkについてジャンプ先が(k-1)*m未満であるかどうかだけを考えます。
この値以上であったときは(k-1)*m+l以下である間はジャンプを繰り返し、これを超えた時点でkがインクリメントされてまた同じ条件で判定されます。
そして、(k-1)*m未満が最初に出てきた点が答えとなります。
注意点
ここで自分が嵌った点を2つ。
足場はn個しかありません。
よってn個まで到達したらその足場から出るジャンプをしたときはそこが落下地点となります。
n個の処理はしてたのですが、n個を超えた後の処理をすっかり忘れていて、最初提出したときは何も出力せずにそのまま終了するようなプログラムとなっていました。
これが原因でPEが出ました。。。orz
もう1点。
ジャンプを繰り返せばいいのですが、一回のジャンプで足場が常に次へ移るとは限りません。
つまり同じ足場内を繰り返しジャンプするかもしれません。
よって、(k-1)*m以上であったときは(k-1)*m+l以下である間は繰り返しジャンプを行えばいいのですが、この文章通りにプログラムを書くとループになると思います。
しかし、そのように書くと処理が増え時間がかかります。
これでTLEが発生してしまいました。。。orz
解答例
#include <cstdlib> #include <cmath> #include <map> #include <utility> #include <set> #include <sstream> #include <iostream> #include <iterator> #include <string> #include <vector> #include <list> #include <algorithm> #include <functional> #include <stack> #include <queue> using namespace std; #define mp make_pair #define pb push_back #define sz(x) ((x).size()) #define For(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) For(i,0,(n)) #define all(v) (v).begin(),(v).end() int main( void ) { long long n, d, m, l; long long p = 0; cin >> n >> d >> m >> l; p += d; rep( k, n ) { if( p < k * m ) { cout << p; return 0; } if( k * m + l >= p ) p += ( ( ( k * m + l ) - p ) / d ) * d; while( k * m + l >= p ) p += d; } cout << p; }
結構すっきりしています。
PEが発生した原因は最後の cout << p; の行がなかったため。
TLEが発生した原因は if( k * m + l >= p ) p += ( ( ( k * m + l ) - p ) / d ) * d; がなかったためです。
TLEの原因であるループはそのまま残してあります。
これはその前の条件の式がこの1文で現在の足場を抜けるまでの回数分を一度に足している自身がなかったためです。
これをしっかり考えてる暇があったら次の問題を（以下省略されました
ということで、この文の周辺は結構適当です。
恐らくこの文だけでは現在の足場は超えないでしょうね。
ですが、その後のwhileを残してあるため問題ありません。
ちなみに、前の文で足場を抜ける直前まで一度の計算ですませてあるのでこのwhile文はほとんどループしません。
＃多分ループしないんじゃないかな？
なので、while文は残ってはいますが実際には確実に計算量は減っています。
ただし、よいこのみんなは真似しないでね＞＜
Ｃ．Stripe
問題
一列に並んだ各マスに数字が書かれている。
これをマスにそったあるところで2つに切ったときにそれぞれの数字の合計が等しくなる切り方は何通りあるか。
問題文はストライプだの正方形だの書いてありますが、要約するとこんな感じじゃないですかね？
解法
最初、1番目のところで切ったときのそれぞれ計算し比較、2番目のところで切った時のそれぞれを計算し比較、・・・と考えましたがどう考えても時間がかかりすぎます。
で、よく考えたら1番目のところで切ったときのそれぞれの合計は、2番目の要素を片方からもう片方へ移せば2番目のところで切った時のそれぞれの合計になりますよね。
ということで、一度全ての数字を全部片方に加算します。
そして、1回ごとにその数字分を片方から引き、もう片方に加えてそれを比較、それが等しくなった時の数をカウントしていきます。
まぁこれはソースがそこそこ綺麗なのでソース読んだ方がわかりやすいかもｗ
注意点
これは一発で通ったので注意点はわからないです＞＜ ←
解答例
#include <cstdlib> #include <cmath> #include <map> #include <utility> #include <set> #include <sstream> #include <iostream> #include <iterator> #include <string> #include <vector> #include <list> #include <algorithm> #include <functional> #include <stack> #include <queue> using namespace std; #define mp make_pair #define pb push_back #define sz(x) ((x).size()) #define For(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) For(i,0,(n)) #define all(v) (v).begin(),(v).end() int d[int(1E6)]; int main( void ) { int res = 0; long long l = 0; long long r = 0; int n; cin >> n; rep( i, n ) { cin >> d[i]; l += d[i]; } rep( i, n - 1 ) { l -= d[i]; r += d[i]; if( l == r ) res++; } cout << res; }
短いですね。
ソース自体は難しくないし、そこそこ綺麗だと思うので多分理解出来るかと・・・
Ｄ．Seller Bob
Ｅ．Flag 2
え？
問題自体開いてないですよ？＾ｑ＾ ←
あとがき
まぁこんな感じでわかりますかね？
わからなかったらコメントなり[twitter:@rofi]に言ってくれればわかる範囲内で答えます＞＜
あと、こういうの需要ありますかね？
他の人も書いてる気がするのであまり役に立たないのでは〜と思ったり・・・
・・・あれ？
お外がなんか明るく・・・ ←
