ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

幾何

ABC016 D - 一刀両断

問題 提出コード 解法 分割される部分が1つ増えるには、線分ABと交差する多角形の辺が2本増える必要があります。 交差する多角形の辺が奇数になることは必ず存在しないので、多角形の辺と交差する辺の本数を2で割り、最後に1追加したものが答えとなります。 …

AOJ 2233 Carrot Tour

問題 提出コード 解法 これ自力で解ききれなかったの悔しいですね… dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値 とします。こうすることで、持っているにんじんの個数は自動的にkになります。 そして、 dis[i][j]…

AOJ 2600 - Koto Distance

問題 提出コード 解法 サンプルの図がわかりやすいのですが、ある座標(x,y)から距離w以内に効果がある場合、 (x-w,p)~(x+w,p)および(p,y-w)~(p,y+w)の範囲に効果があることになります。ここで、pは任意の数字になります。これは、横についてx-w~x+wの範囲を…

AOJ 1175 - そして,いくつになった?

問題 提出コード 個人的にICPCの中でも結構好きな部類の問題です。 解法 今回もc言語です。 メモ化再帰をしていきます。 円盤の枚数はたかだか24で、状態としては”残っている”か、”取り去られている”の2通りです。なので、全体で種類の状態が存在しますが、…

AOJ 1190 - つながれた風船

問題 提出コード 二度とやりたくないです。。。 今回は諸事情でC言語となっています。 自分は高校数学がとてもできないので、今回もさまざまなサイトにお世話になりました。 四面体の体積を求める2つの公式with行列式 | 高校数学の美しい物語 ヘロンの公式…

AOJ 1194 - バンパイア

バンパイア 提出コード 初めての幾何問題です。 まずはのときの、x座標がの部分の太陽の高さを求めます。 ビルの左右の端が小数になることはないので、は整数の座標の部分のみ求めます。太陽の高さはの右側が単調減少、左側は単調増加となっているからです。…