かD: 一刀両断 - AtCoder Beginner Contest #016 | AtCoder [問題] 多角形(凹凸)と線分1本が与えられる。線分により、多角形は何個に分割されるか？ [解答] 多角形の各辺について、線分との交差判定を行う。交差判定はベクトルの外積の符号判定を用いて行う(…

- AtCoder Beginner Contest #016 | AtCoder [問題] N人について、友達関係M個が与えられる。 それぞれの人について、「友達の友達」の人数を返す。 [解答] 友達の友達から、友達と自分を引く。 [コード](Ruby) https://paiza.io/projects/KIPFdk49anacJxZTY…

- AtCoder Beginner Contest #016 | AtCoder [問題] A,B,Cが与えられる。A+B=C、C-B=Dを満たすかどうかで、?(両方満たす), +(+のみ満たす), -(-のみ満たす), !(両方満たさない) のいづれかを返す。 [解答] ４通りチェックする。 [コード](Ruby) https://paiz…

- AtCoder Beginner Contest #016 | AtCoder [問題] 月が日で割り切れれば"YES",それ以外は"NO"を表示する。 [解答] 月%日==0で判定 [コード](Ruby) https://paiza.io/projects/BXfPvIAk9Mn-a-amw05H_g [感想] 頑張れば50バイトぐらいになるかなぁ？

No.86 TVザッピング(2) - yukicoder [問題] N x Mのマス目がある。あるボタンから開始して、通れるマス目を1回づつ巡って最初のマスに戻る。ただし、ボタンを巡る際、進行方向はまっすぐか左にのみいける。 [解答] 最初のボタンの前後では実質的に右み回るこ…

No.85 TVザッピング(1) - yukicoder [問題] X * Yのマス目にボタンがある。いずれかのボタンからスタートして、上下左右のいずれかのボタンに動いて最初のボタンに戻る。各ボタンは一度だけ辿ることができる。このように巡回することはできるか？ことはでき…

No.84 悪の算盤 - yukicoder [問題] R行C列のマス目から1個だけ選んで"*"を書く。 作れるパターンに0から順番に番号を付けると何番まで書けるか。 1<=R,C<=10^9 [回答] 基本的にパターン数はR*C。 縦横の長さが同じ場合、90度で回転させるので4で割る。違う…

No.83 最大マッチング - yukicoder [問題] 0..9のデジタル数字をマッチで書く。マッチN本で数字を書く時、最大で書ける数字(複数桁)は何か？ 2<=N<=10^5 [回答] 1本で書ける数字はない、2本で1が書ける、3本dで7が書ける。 桁数が多い方がいいので、1を使え…

No.82 市松模様 - yukicoder [問題] 幅W、高さH、左上C("B" or "W")で、"B"と"W"の市松模様を書く。 [回答] (w + h)%2==0 or 1で"B"又は"W"を出力。 Cが"B"か"W"で出力を反転。 [コード](Ruby) https://paiza.io/projects/8cO8BE7P9BK9mOHEVVh5pA [感想] 左…

B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder [問題] n頂点のツリーグラフがある。いくつかの頂点に宝石がある。頂点xから開始して、全部の宝石を取ってxに戻るには、最短で何個の辺を通ればいいか。 [回答] 頂点xから出発してDFS(深さ優先探索…

A: 閉路グラフ - AtCoder Regular Contest 030 | AtCoder [問題] N個の頂点が円のように線で結ばれて並んでいる。 ここからいつくかの頂点を取り除いて、K個の線分に分割することはできるか？できれば"YES",できなければ"NO"を返す 3<= n <= 10^5 1<= k <= 1…