AtCoder Beginner Contest 197（Sponsored by Panasonic）「D - Opposite」纏め

第4問も考え方が特殊だったので、一応メモを残して置きますφ(．．)

 

この問題のポイント

・正N角形

・Nは偶数

・与えられるのはx0,y0,xN2,yN2 

この3つがこの問題のミソです。

 

何がミソかと言うと、p0とｐ(n/2)は対角線の位置になるということ。

もう一つのポイントは正N角形。正N角形は全ての角が1つの円の円周上にあるということ。

この2つを考慮すると、p0とｐ(n/2)の中点が正N角形に外接する円の中心と一致する

ということで、中心は

X座標：（x0+x(n/2)）/2
Y座標：（y0+y(n/2)）/2

となります。

 

地味な落とし穴:型には気を付けろ

今までint型ばっかり使っていたのですが、今回地味な落とし穴がありました。

それは小数点表示ができない…

3 / 2 = 1.5 にならず

3 / 2= 1となってしまいました。

 

これは小学生的に考えると分かりやすくて

3 / 2=1 余り 1なので、商は1と言うことですね

 

これを小数点表示にするにはdouble型にキャストしてあげる必要があります。

 

ちなみに面倒なら最初からdouble型にしてしまうのも手です。ちなみに私はそうした

そうすると、キャスト不要になるので、コードを短くできます♪

 

外接円の中心から答えを求める

では、目的のp1を求める方法を考えていきましょう。

自分がパッと思いついたのはp0からx軸方向ずらしてあげる。

この時ずらすのは、三角関数で求められそう、そんな構想で考えるが、2個目の解けない…

ここで気づいたのはp0とp1の直線はx軸に平行じゃない

そう、斜めも存在するのだ…

ということはy軸方向にもずらさないと行けないけど、そうなってくると、中心角から三角関数で求めてあげましょう

つまり、中心から角度を出して、360°/N反時計回りにずらしてあげる、というのが正しいっぽいです。

なお、中心角とp0、x軸の角度は、atan2(x1, y1, x2, y2)で求められるみたいです。

 

中心から（x0,y0）の角度θ+360°/n反時計回りにずれた位置が回答になります。

x1=xc - cos(θ+360°/n) * r
y1=yc - sin(θ+360°/n) * r（rは半径）

 

今回は一発合格できました。

めでたしめでたし。

Submission #21523661 - AtCoder Beginner Contest 197（Sponsored by Panasonic）

AtCoder Beginner Contest 197（Sponsored by Panasonic）「ORXOR」纏め

AtCoderの問題を解き始めて、2つ目のコンテスト。(出場したとは言っていない)

大苦戦したので、ハマったポイントと、それに対する回答を整理したので、自己理解のために再整理しました。

 

今回は大苦戦した問題「AtCoder Beginner Contest 197（Sponsored by Panasonic）」の第3問「ORXOR」について、自己理解用にまとめました。

 

問題文

簡潔で、かつ難解な問題がこちら。

長さ N の数列 A が与えられます。
この数列を、1 つ以上の空でない連続した区間に分けます。
その後、分けた各区間で、区間内の数のビット単位 OR を計算します。
こうして得られた全ての値のビット単位 XOR として考えられる最小値を求めてください。

atcoder.jp

 

2行目の意味

自分が良く分からなかったポイントが、2行目

この数列を、1 つ以上の空でない連続した区間に分けます。

 

 これをbit全探索を使って処理を書くらしいのですが、bit全探索って何？という私には最初からチンプンカンプン。

bit全探索を調べると、複数のtrue・falseを網羅して調べるために使う手法です。

ざっくりと別記事で整理したので、そちらを参照してください

 

xyoshixaki.hateblo.jp

 

bit全探索の意味を理解して、すぐに次の疑問。

bit全探索を使ってtrue・falseを網羅したいと言っても、何を網羅するの？ 

 

結論から言うと、数列と数列の間に区間を仕切る区切りがあるか、無いか、の状態を網羅したかったみたいでした。

説明だけだと、イメージがつかないと思うので、具体例を出すと

 

ａ　⋮　ｂ　|　ｃ　⋮　ｄ

 

ａとｂ、bとｃの間に区切りが存在するか、否かを網羅したいみたいです。

上の例だとaとbで1区間、cとdで1区間でした。

 

もう1個、分からなかったポイントが区間って2個だけじゃないの？ってところでした。

こちらの答えがNo。何個でも区間が作れます。

先のイメージに追加するなら、こんな感じですね。

 

ａ　⋮　ｂ　|　ｃ　⋮　ｄ　|　ｅ

 

aとｂで1区間、cとｄで1区間、e単体で1区間。合計3つの区間が存在します。

最大N個の区間ができるということですね。

 

ここまで理解するのに、3時間くらいかかりました。

マジで問題文が理解できなかった。

 

2区間だけと思っていた時の回答がこちら。

Submission #21467772 - AtCoder Beginner Contest 197（Sponsored by Panasonic）

サンプルはあっているのに、検証はことごとく✖なので、絶望しました。

 

ちなみに、問題文の3行目、4行目は問題なく理解できたので、省略します。

（多分、数学の教科書やプログラミングの教科書を漁れば、詳しい解説が出ていると思います。）

 

区切り判定処理は前？後ろ？

最後の詰まったポイントは区切り判定処理でした。

1個1個の区間にor演算をして、最後にxor演算をしていきます。

 

そのため、区切り判定をした上で

  • 区切られていない場合はor演算
  • 区切られて入れる場合は初期化してor演算

とする必要があります。

 

私が実装したのが、or演算の前に区切り判定をしてしまいました。

 

先ほどのイメージを用いると、

　　ａ　⋮　ｂ　|　ｃ　⋮　ｄ　|　ｅ

aでは区切り判定をせず、bの処理の前に区切り判定！cの前で区切り判定！みたいな感じで実装していました。

結果は概ねOKでしたが、1個だけNGになりました。

「ふぁ～、1個だけNGとか意味分かんね～」となりましたが、ここまでさらに2時間…もはや、意地になって調べました。

詳しくはソースコードを読んで欲しいのですが、NGだったのは「Nが1の時に処理がスキップされてしまう」

結果として、1件NGとなり、失敗しました。

 

この時のソースコードがこちら。

Submission #21478308 - AtCoder Beginner Contest 197（Sponsored by Panasonic）

先ほどのソースと違いコメントアウトが大量に書いているのは、マジで、ここまでしないと理解できなかったです。

 

最終的に、区切り判定をor演算の前に持ってきて、無事成功しました。

最終的なソースコードはこちらです。

Submission #21487697 - AtCoder Beginner Contest 197（Sponsored by Panasonic）

 

今まで1問あたりそんなに時間かからなかったのに、まさか6時間クラスになるとは夢にも思っていなかったです。

同じ挫折を味わう人がいた時の参考になるように、自分の詰まったところを整理しました。

bit全探索について

競技プログラミングをやっていて、bit全探索というものを始めて聞いて、「ふぁ？」ってなったので、自己理解のためにまとめてしました。

 

 

bit全探索とは

bit全探索とは二進数とbitを用いて、全探索すること！

うむ、分からんw

取り敢えず分解してみましょ

 

二進数やbitって？ 

bitというと、0と1だけで数字を表現すること。

普段だと0～9という10個の数字で表現する10進数を使っていますが、そうではなく、0と1だけであらわします。10進数を2進数に直すとこんな感じ♪

例）2   ->    10

       3   ->     11

       4   ->   100

       6   ->   110

       8   ->  1000

 

全探索って

全探索とは全ての組み合わせを調べてあげる方法のことです（7割理解なので、厳密には違うかも）

例えば、a,b,cの3つの組み合わせを全部調べるなら、

「何もなし」「aのみ」「bのみ」「cのみ」「aとb」「bとc」「cとa」「aとbとc」

の8通り。2の3乗=8が組み合わせの数になります。

この8通りに対して、処理を実施するのが全探索です。

 

参考にした記事がこちらです

drken1215.hatenablog.com

 

つまり、

bit全探索とは

bit形式（二進数）にして、全ての組み合わせを調べること、らしいです

使用するメリット

使用するメリットはきちんと書いている記事が見つからなかったので、何とも言えないのですが、1問解いて感じたのは、処理を簡潔にできる。

bit形式で表記するのは、複数のtrue・falseを管理したい場合っぽいです。（有名なところだと、linuxのファイルパーミッション）

 

そういった複数のtrue・falseを網羅して、プログラムを書く時にそのまま書くと、1個1個条件分岐を書かないといけなくなってしまう。

すると、ネストがめちゃくちゃ深くなるし、ソースも複雑になってしまう。

 

ということで、処理を簡潔に書くために、bit形式にして複数のtrue・falseを一括管理してしまおうということがbit全探索を使用する目的っぽい感じがしました。

 

数字をbit全探索にしてみよう

javaを扱ったことがある人ならわかると思うけど、intクラスをただ使うだけじゃ、bit方式で計算してくれません(＞＜)

数字をbit全探索するには下の感じにする必要があります

 

		for (int i=0; i<(1<<n); i++) {
			//ループ処理
		}

 通常のfor文と違う点は2つ目のループ処理を抜けるための条件。

「(1<<n)」でbit形式として処理されるようです。

ループ回数は2のn乗回実行する、という意味です。

n=3の時だと2の3乗になるので、8回ループするということになります。

 

 

今回はbit全探索の解説をしました。 

何か、追加で分かったことがあったら、追記します。

 

※本記事は筆者の自己理解を整理するために作成しています。

　頭悪いので、間違った解釈をしている可能性があるので、そこは温かく見守って頂けると嬉しいです。