ABC197の感想

AtCoder Beginner Contest 197（Sponsored by Panasonic）に参加しましたのでその感想を書いて行きます。

問題はこちらから。

Tasks - AtCoder Beginner Contest 197（Sponsored by Panasonic）

結果はこんな感じでした。

ABC（71:47 + 1WA）
順位：3196 / 7885
パフォーマンス：763

今回も3完でした。なんといいますか、D問題が解けないのはもちろんなのですが、ABCのいずれかで詰まることが多いですね。それで、Dを考える時間が少ない、D問題で焦ってしまう、悲しい連鎖が起こっています。精進にて問題を解くのはもちろんなのですが、時間をもう少し頭に入れてやる必要がありそうです。

感想です。

A問題

文字列の順番を変えて出力します。はじめ

string ans = s[1]+s[2]+s[0];

で書きましたけど、これダメでした。こんな書き方できなかったけ？と思いながら、

string ans;
ans += s[1];
ans += s[2];
ans += s[0];

で無事ACです。

B問題

地点 X, Y から上下左右に見ていきます。'.'でしたら++ansで、枠からはみ出す、または'#'にぶつかってしまったら、breakします。

X, Y の点の数え上げは忘れないようにしましょう、

C問題

or と xorを指定された用にしたときの最小値です。

まず、制約からbit全探索を思いつきました。が、 「N = 20を1~20グループに分ける」っていうのはなんか組み合わせが多くなりそうと思い、一旦、別解法を考えます。

1, 5, 7

の入力例を2進数表記して

001, 101, 111

をいろいろ動かして法則を見つけようとしましたがうまくいかず、、、

結局 2^20 は10^6 程度ということを電卓から教えてもらい bit全探索を書きました。ただ、0と1の連続した部分を一つのグループとしたのですが、連続したものの判定に少々手間取りました。

(bit & (1<<i) == bit & (1+i))

はじめはこれで書いてましたが、どうもうまくいかず。それもそうで、0,1が立っている場所が違いますね。ですので、

((bit & (1<<i)*2) == bit & (1+i))

こんな感じで一つずらしました。

maxを1e9にしていて、１WAを出しましたがなんとかAC。結構時間がかかりました。

D問題

正 N 角形（Nは偶数）のある頂点から一つだけ時計回りに回った頂点の座標をもとめます。

いまでならなんとでも言えますが、どうして直交座標系で頑張ってしまったのでしょう。この図形の外接円を考えれば中点から 2Π/N[rad] だけ、回転した座標が答えですね。焦りました。

結局、google先生から、正 N 角形の一片は外接円の直径の長さ 2* rを用いて

2r sin (π/n)

で求められると教わりました(ほんとですか？確かめてないです)。次に、2点の傾きを求めます。といいますか、挟角 θ を求めます。そうすると、答えの a の成分がcos と sin で表せます。並行移動します。2点を通る直線上にある、点(x0,y0)からのa 離れた点の座標が求まりました（x0 < x_(N/2)かどうかで場合分け）。次に正 N 角形の内角の和は180 * (N-2)ですので、答えの座標は先ほどの点を反時計回りに180 * (N-2) / 2だけ回転したものになります。

とここまで書きましたがあっているかは知りません。実装が間に合いませんでした。解いてる途中でも、想定解がこんなめんどくさいわけないよな、と思ってましたが時間も余裕もなく、このまま突き進んでました。

うーん、これは解きたかった。

E問題

みてないです。

F問題

同じく

あとがき

毎度の事ながらコンテストでうまくいかないと悔しいですね。なによりもレートが下がってしまうのがとっても悲しい。でも、参加しなければレートは上がらないのでこればっかりはしょうがないです。強くなればいつかレートは上がります。そんな感じで頑張ります。

あとは、時間ですね。いつもダラダラと精進してますが、時間を区切った方が良いのかもしれません。4月は時間を気にした、メリハリのあるお勉強を心がけて行きたいです。

また、今回も解答を書くつもりです。まずは、DEFを解きますので少々お待ちください。