初回 -> はじめに
ABC108を解きました。
3完です！
D問題は解けていません。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 2min | - | 7ms |
| B | 8min | ベクトル | 5ms |
| C | 25min | - | 7ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
座標を扱う問題はベクトルを使うと考えやすいです。
倍数が出てくる問題を考えるときは、係数で考えると考えやすいです。
A - Pair
int k;
cin >> k;
cout << k * k / 4;
K以下の整数のうち、[偶数の個数] * [奇数の個数]が答えですね。
それぞれk / 2個、(k + 1) / 2個あります。
切り捨てしているので注意です。
これをかけてまとめるとk * k / 4になります。
まとめるときも切り捨てを利用しています。
B - Ruined Square
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int vx = y1 - y2;
int vy = x2 - x1;
cout << x2 + vx << " " << y2 + vy << " ";
cout << x1 + vx << " " << y1 + vy;
座標を扱う問題はベクトルを使うと考えやすいです。今回は2次元平面ですね。
反時計回りに、入力の2つの頂点をV1, V2として、残りの2頂点をV3,V4とします。
また、V2 - V1を90度回転させたものをVdとします。
つまり、
\vec{V_d} = R(90^\circ)\ (\vec{V_2} - \vec{V_1}) =
\left(
\begin{array}{cc}
0 & -1 \\
1 & 0
\end{array}
\right)
\left(
\begin{array}{c}
V_{2x} - V_{1x} \\
V_{2y} - V_{1y}
\end{array}
\right)
=
\left(
\begin{array}{c}
V_{1y} - V_{2y} \\
V_{2x} - V_{1x}
\end{array}
\right)
とします。
このとき、V3,V4は以下のようになります。
\vec{V_3} = \vec{V_2} + \vec{V_d}\\
\vec{V_4} = \vec{V_1} + \vec{V_d}
これより答えがわかります。
ここで、回転させるときは以下の行列をかければできますね。
\\
R(\theta) = \left(
\begin{array}{cc}
\cos{\theta} & -\sin{\theta} \\
\sin{\theta} & \cos{\theta}
\end{array}
\right)
90度回転させるときは以下の式です。
\\
R(90^\circ) = \left(
\begin{array}{cc}
\cos{90^\circ} & -\sin{90^\circ} \\
\sin{90^\circ} & \cos{90^\circ}
\end{array}
\right)
=
\left(
\begin{array}{cc}
0 & -1 \\
1 & 0
\end{array}
\right)
ぶっちゃけると今回は回転行列のような複雑なことは考えなくても大丈夫です。
しっかりめに書きましたが、90度,180度,270度の回転ならばx座標とy座標を入れ替えて1倍か-1倍するとできます。
私が解いたときも回転行列を使わず、手で試しながら上の式の計算結果と同じものを導きました。
(60度等の回転をさせるときに真価を発揮します)
C - Triangular Relationship
ll n, k;
cin >> n >> k;
ll c_od = 0;
ll c_ev = 0;
if (k & 1)
{
// 奇数
c_od = n / k;
}
else
{
// 偶数
ll cnt = n / (k / 2);
c_od = (cnt + 1) / 2;
c_ev = cnt / 2;
}
cout << c_od * c_od * c_od + c_ev * c_ev * c_ev;
倍数が出てくる問題を考えるときは、Kを何倍するかの係数で考えると考えやすいです。
Kが奇数の時、Kの整数倍の数を3つ組み合わせたものが答えになります。
Kが偶数の時、Kの半分の数をKhとして、
・Khを奇数倍したものを3つ組み合わせたもの
・Khを偶数倍したものを3つ組み合わせたもの
の和が答えになります。
同じものを重複を許して3個とる組み合わせは単に3乗すれば求まります。
例えば入力例 (N=3, K=2) のときを考えます。
Kは偶数です。Kの半分の値はKh = 2/2 = 1です。
このとき、N = 3以下の正整数のうち、
Kh = 1の奇数倍は2個
Kh = 1の偶数倍は1個
ですね。
2^3 + 1^3 = 9が答えになります。
以上です。ありがとうございました。