chacoderのブログ

競技プログラミングそのほか

精進記録 精選7~13

ほとんど解いたことがある問題ばかりでしたが精選7~13をやりました。

7 最古の遺跡

C - 最古の遺跡

四角形ができるかの判別に幾何の知識が必要です。

ABC108BのRuined Squareはこの問題からとってるのでしょうね。

B - Ruined Square

正方形の隣接する2つの頂点の座標を(x1,y1),(x2,y2)とすると,
x = x2 − x1 , y = y2 − y1 として
残りの2つの頂点の座標は(x2-y,y2+x),(x1-y,y1+x)となります。

方眼紙に斜めの正方形を描いてみるとわかりやすいです。

座標入力時にその座標があるかないかだけを判定するためのテーブルを作っておくと実装が楽です。

12 派閥

D - 派閥

一度解いたはずでしたが解けませんでした。

bit全探索で考えられる組み合わせを列挙し,組み合わせ中のすべての要素について条件を充たすかを調べる方法を改めて理解しました。

1になっているビットの数を取得するcount()関数を確認しました。

t=bitset<32>(i).count();

13 おせんべい

E - おせんべい

こちらは15分ほどで自力で最後まで実装できました。

https://atcoder.jp/contests/joi2008yo/submissions/17657155