初回 -> はじめに
ABC178を解きました。
4完です！
E問題は時間を過ぎて解けました。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 1min | xor | 8ms |
| B | 2min | 最大値 | 7ms |
| C | 31min | 包除原理 | 6ms |
| D | 44min | DP | 11ms |
| E | - | マンハッタン距離 | 71ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
ベン図が出てきたら包除原理ですね。覚えておこう。
マンハッタン距離が出てきたら45度回転させることで扱いやすくなります。
C問題とD問題に時間をかけすぎです。本番に弱いですね。。。
ここ2回、続けてレートが下がっているのでピンチです。
記事を投稿するのは久しぶりになります。
記事にすると覚えやすく、良い復習になりますね。
E問題が面白かったので書こうと思いました。
A - Not
int x;
cin >> x;
cout << (x ^ 1);
$0 \rightarrow 1$
$1 \rightarrow 0$
という変換ですね。
入力が0か1なので、1とのxor が答えになります。
B - Product Max
ll a, b, c, d;
cin >> a >> b >> c >> d;
cout << max({a*c, a*d, b*c, b*d});
条件より、区間の端どうしの積が答えになりそうですね。
区間の端どうしの積は4通りあるので、4通り計算してそのうちの最大値が答えになります。
答えはint型の範囲に収まらないので注意です。
C - Ubiquity
// a^n % mod を計算する O(log n)
ll powmod(ll a, ll n, ll mod) {
ll ret = 1;
while (n > 0) {
if (n % 2 == 1) { ret = ret * a % mod; }
a = a * a % mod;
n /= 2;
}
return ret;
}
void solve()
{
int n;
cin >> n;
const ll MOD = 1000000007;
cout <<
((powmod(10, n, MOD)
- powmod( 9, n, MOD) * 2 + MOD * 2) % MOD
+ powmod( 8, n, MOD)) % MOD;
}
数字をN個並べた数列の中で
・0が1つ以上含まれる
・9が1つ以上含まれる
というものの個数を数え上げる問題です。
ベン図がイメージできるかと思います。
ベン図といえば包除原理を使うと分かりやすいですね。
[10種類をN個並べる] - [0以外をN個並べる] - [9以外をN個並べる] + [0,9以外をN個並べる]
で求められます。
それぞれ計算すると
$10^n - 9^n - 9^n + 8^n$
になります。
数値が大きくなるので、計算のたびにmodをとりましょう。
コンテスト時はcombinationをつかって頑張る方法で解きました。
0,9以外の値を先に並べてから0,9を並べる方法です。
想像通り、考察と実装が重めになります。実行時間もかかるのでコンテスト時の解法には向いていない。
こちらの提出です。供養しておきます。
解説放送のライブラリを使っています。
D - Redistribution
int s;
cin >> s;
vector<mint> ans(s + 1, 1);
ans[0] = ans[1] = ans[2] = 0;
for(int i = 3; i <= s; ++i)
{
for(int j = 3; j <= i / 2; ++j)
{
ans[i] += ans[i - j] + ans[j];
if (i - j == j) ans[i] -= ans[j];
}
}
cout << ans[s];
このライブラリ(mint)を使っています。
DPですね。
ans[n] = 総和がnになる数列の数
です。
例えばs=8のとき、
わけない(8がひとつだけの数列)
5と3に分けて、[総和が5になる数列の数] + [総和が3になる数列の数]
4と4に分けて、[総和が4になる数列の数] + [総和が4になる数列の数]
の3つの組み合わせの和が答えになります。
つまり、
ans[8] = 1 + ans[5] + ans[3] + ans[4]
が答えになります。
sが偶数の時は半分に分けると余計にカウントされてしまうので、その分を引くことに注意です。
E - Dist Max
#define ALL(a) (a).begin(),(a).end()
ll n, x, y;
cin >> n;
vector<ll> d1(n);
vector<ll> d2(n);
for(int i = 0; i < n; ++i)
{
cin >> x >> y;
d1[i] = x - y;
d2[i] = x + y;
}
sort(ALL(d1));
sort(ALL(d2));
cout << max(d1.back() - d1[0], d2.back() - d2[0]);
マンハッタン距離を求める問題です。
これは調べて知ったのですが、マンハッタン距離は45度回転させると扱いやすくなります。
つまり回転行列を適用します。
45度回転させる行列は以下ですね。
\left(
\begin{array}{cc}
\cos{45^\circ} & -\sin{45^\circ} \\
\sin{45^\circ} & \cos{45^\circ} \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\end{array}
\right)
これを適用するのですが、$\frac{1}{\sqrt{2}}$が扱いにくいので$\sqrt{2}$倍します。
計算すると、以下のようになります。
\left(
\begin{array}{c}
x' \\
y'
\end{array}
\right)
=
\sqrt{2}*
\left(
\begin{array}{cc}
\cos{45^\circ} & -\sin{45^\circ} \\
\sin{45^\circ} & \cos{45^\circ} \\
\end{array}
\right)
\left(
\begin{array}{c}
x \\
y
\end{array}
\right)
=
\left(
\begin{array}{cc}
1 & -1 \\
1 & 1 \\
\end{array}
\right)
\left(
\begin{array}{c}
x \\
y
\end{array}
\right)
=
\left(
\begin{array}{c}
x - y \\
y + y
\end{array}
\right)
以上より、
$x' = x - y$
$y' = x + y$
となります。
勝手に$\sqrt{2}$倍しているように見えますが、軸を変えることでスケールも変わってしまうので、スケールを1.0倍に変換しています。問題ありません。
このようにすると、原点からのマンハッタン距離が同じものの点の軌跡は原点を中心として正方形になります。
この正方形の各辺は軸と並行です。(45度回転させない場合は各辺が軸と45度です。)
面白い性質ですね。
また、他にも扱いやすい性質があります。
というのも、 $x'$ と $y'$ は直行していて線形独立ですね。(45度回転させただけなので当然ですが。。。)
つまり、 $x'$ と $y'$ は独立して扱うことができます。
以上より、
$x' = x - y$と、$y' = x + y$ はそれぞれマンハッタン距離にあたり、独立して扱えます。
これより、 $x'$ と $y'$ をそれぞれ配列に入れてソートすれば距離が最大のものと距離が最小のものがわかります。
距離なのに負の値がでてきて少し気持ち悪いですが、座標が軸の正方向側にあるか負方向側にあるかを示していると考えてください。
コードではd1に$x'$、d2に$y'$を入れています。
配列がソート済みなら
d1.back() - d1[0]で$x'$軸方向の距離の最大値
d2.back() - d2[0]で$y'$軸方向の距離の最大値
がわかるので、その大きい方が答えになります。
以上です。ありがとうございました。