ABC183の解答
AtCoder Beginner Contest183を解き終わったので、その解答を書いていきます。
問題はこちらから。
難易度はこんな感じ。
A 6 （灰）
B 128 （灰）
C 335 （灰）
D 662 （茶）
E 1288 （水）
F 1586 （水）
いつもより、Fが簡単だった？と感じる人もいるかもしれません。が、私ではまだまだ歯が立ちません。あとは、何でしょう、、、
学びの多い回でしたので、その辺を含めながら書いていきます。
ではいきます。
A ReLU
ReLUという関数を実装する。
という問題です。ReLUは
f(x) =
0 (x < 0)
x (x >= 0)
という関数です。要は、マイナスの値は0にして、0以上ならそのまま出力、という感じです。if 文なり、maxなり、色々と実装方法はあると思うので、好きなように実装をしましょう。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
using P = pair<int, int>;
int main()
{
int x;
cin >> x;
x = max(0, x);
cout << x << endl;
return 0;
}余談ですが、この関数は機械学習、主にニューラルネットの分類によく使用されるのですが、どのように呼ぶのが正しいのか未だに知りません。「れる、れりゅー」と呼ぶ方もいますが、私の担当教授はどうやらお気に召さないらしく「えるいーあーるゆー関数」と呼んでいました。自ずと私もそう呼んでいます。また別勢力として「ランプ関数」派もいます。いつの日か統一される日は来るのでしょうか？
B Billiards
ビリアードのように壁に球を反射させたのち、お目当ての場所に到達させる。このときに、壁に当たった位置を求めよ。
という問題です。ちょっと数学チックな問題ですね。とはいうものの、この手の「反射」問題には有名なテクニックがあるのでそれを用います。
ゴール地点の y 座標の符号を反転させてしまいましょう。もう少し厳密に言うのであれば、反射する線に関して線対称となるように目標地点の座標を変換します。
このようにすると簡単に反射位置がわかります。あとは、スタート地点とゴール地点（y反転）の2点を通る直線と、反射面（y=0）との交点を求めてあげれば答えです。
このように幾何的に考えてあげると、例えば、「スタートがゴールよりも右側にある」みたいな場合でも問題なく対応できます。
あとは、誤差10^(-6)に抑えなければならないので、値をdoubleで扱って、いい感じに出力しましょう。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
using P = pair<int, int>;
int main()
{
double sx, sy, gx, gy;
cin >> sx >> sy >> gx >> gy;
gy = -gy;
double gr = (gy - sy) / (gx - sx);
double ans = -sy / gr + sx;
cout << fixed << setprecision(7);
cout << ans << endl;
return 0;
}高校の数学IAとかでは教科書に載っているぐらいの基本問題ですので、簡単にわかった人も多いとは思いますが、少し苦戦した人もいるのではないでしょうか。座標を変換するとか、三角形の相似とか、当時はなんてことなかったのに、今、再び問題に取り組むと想像以上に忘れているものです。非常に恐ろしい話です。
C Travel
巡回セールスマン問題(TSP)の話です。都市 1 から出発して、n-1 個の都市を巡ったのちに都市1に戻るのに要する時間が k となるような都市の巡り方はいくつあるか。
という問題です。TSPはnp困難な問題として有名ですね。都市を巡る順番って驚くほど多く存在するため、「全部試そうぜ」とすると、私たちの寿命のみならず、宇宙の寿命まで尽きてしまいます。とはいうものの、本問題は制約が n<= 8でなおかつ、出発地点は都市１で固定です。そのため、都市の巡り方はせいぜい
7 ! = 5040 通り
です。これくらいなら全部試せますね。試しましょう。
試し方としましては、訪問する順番を持つ順列を用いて
｛2, 3, 4, 5, 6, 7, 8｝
｛3, 2, 4, 5, 6, 7, 8｝
｛3, 4, 2, 5, 6, 7, 8｝
...
{8, 7, 6, 5, 4, 3, 2}
を全通り行います。ありがたいことにC++では便利な関数
next_permutation
が用意されています。これは、上記のような順列を用意してあげると、すべての順番に対して１回ずつ処理を行ってくれるという優れものです。「面倒くさいことはプログラムにやらせる」とっても大事なことですね。上記の関数を使って、
まず１から出発して、他の都市を巡る。そして最後に１に戻ってくる。
という行動にかかる時間が k となる数をカウントしていきましょう。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
using P = pair<int, int>;
int main()
{
int n, k;
cin >> n >> k;
vector<vector<int>> t(n, vector<int>(n));
rep(i, n)rep(j, n) cin >> t[i][j];
vector<int> p;
rep(i, n - 1) p.emplace_back(i + 1);
int ans = 0;
do
{
int st = t[0][p[0]];
rep(i, n - 2) st += t[p[i]][p[i + 1]];
st += t[p[n - 2]][0];
if (st == k) ++ans;
} while (next_permutation(p.begin(), p.end()));
cout << ans << endl;
return 0;
}本手法は「順列全探索」と呼ばれているみたいですね。c++以外でも「next_permutation」に準ずる関数が用意されているか調べてみましょう。
この関数を知っていれば簡単に解けますし、知らないとなかなか苦戦する問題なのではないでしょうか。このように、様々な問題を経験して、少しずつスコアが伸びていくのも競プロの面白いところですね。
また、abc180にも巡回セールスマン問題が出題されていましたが、あちらはbitDPを用いて解きました。同じ問題でも設定によって求められることが違うので、落ち着いて適切に処理していきましょう。（私はコンテスト中、だいぶ焦りまして、途中までbitDPを組んでました。気づいてよかった。）
D Water Heater
ある給湯器は、毎分 w リットルお湯を沸かすことができるそうです。n 人がそれぞれのタイミングで p リットルのお湯を欲します。すべての人に計画通りにお湯が供給できますか。
という問題です。
愚直にシミュレーションを行えば、答えを求めることができますが、O(n*2)で、10^10なので間に合いません。いくらか工夫しましょう。
今回は公式の解説で取りあげられていた「いもす法」にて解いていきます。
まずは、ざっくりと手法について説明します。
まず、次のような設定を考えましょう。
1人目：1分から6分まで6L
2人目：4分から9分まで2L
3人目：2分から5分まで4L
お湯は毎分10 L 生成
この状況を図に表します。
それぞれの必要量を適切な時刻の上に配置して、某パズルゲームの要領でおろします。そうすると、その時刻において必要となるお湯の総量がわかります。この値が毎分の生産量のラインを越えなければ「供給可能」となるわけです。今回はダメですね。
アルゴリズムのイメージはこんな感じです。次に実装方法を見ていきます。もちろん、すべての時刻において該当する人を見つけて総和を取れば実現されますが、上記の通り時間が足りません。
そのため、お湯の必要開始点と終了地点にて操作を加えます。例えば、1人目であれば、1分目で+6、6分目で-6という情報を配列に記録しておきます。すべての人の情報を記録したら、累積和を取っていきます。そうすると、不思議なことに先ほどの図の状態を実現した配列を作ることができます。
以上が「いもす法」となります。この手法は高次元に拡張ができるそうなので、もうちょっと勉強してみます。
あとは配列の最大値とお湯の供給量を比べるだけです。
実装です。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
using P = pair<int, int>;
//いもす法
int solve2()
{
const int t_max = 2 * 1e5;
int n, w;
cin >> n >> w;
vector<ll> a(t_max + 1, 0);
rep(i, n)
{
int s, t, p;
cin >> s >> t >> p;
a[s] += p;
a[t] -= p;
}
rep(i, t_max) a[i + 1] += a[i];
ll max_w = *max_element(a.begin(), a.end());
if (max_w <= w) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
int main()
{
solve2();
return 0;
}solve2になっているということで、solve1もあります。現在のお湯の必要量を時系列で管理して、供給量と比較していきます。毎回、お湯の必要量を計算するのではなく、必要な区間の始点と終点で値を足し引きします。この辺は「いもす法」と似ていますね。
この時に重要なのが、加算、減算する値をpairで管理してソートすることです。以前pairのソート順に関して備忘録を書きましたが、なかなかに便利ですね。まず、1要素目（今回は時刻）を昇順に並び替え、等しい場合には2要素目（お湯の加算減算）で並んでくれます。これにより、同じ時刻に加減があった場合、減算を先に行うため、判定処理のタイミングを制御する必要がなくなります。
int solve1()
{
int n, w;
cin >> n >> w;
vector<P> e;
rep(i, n)
{
int s, t, p;
cin >> s >> t >> p;
e.emplace_back(s, p);
e.emplace_back(t, -p);
}
//まず、時間でソート、時間が同じ場合はお湯の量が負の値が先に来る
sort(e.begin(), e.end());
ll need = 0;
for (P ei : e)
{
int pi;
tie(ignore, pi) = ei;
need += pi;
if (need > w)
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}問題を通して言えることですが、時刻 t の時には既にお湯を欲していません。気を付けましょう。
最近、某まるか食品さんからとっても大きな某ペヤングが出ていて、それには途方もないほどのお湯がいるそうですね。本問題でもあの焼きそばを作ってた人が一人ぐらいいたのかもしれません。
E Queen on Grid
h * w の盤面の上のいくつかのマスにブロックが置かれています。盤面の左上にチェスのクイーンがいます。このクイーンは右、下、右下のいずれかにブロックを飛び越えない範囲で任意のマスだけ移動できます。盤面の右下への行き方は何通りありますか？
という問題です。これはdpで解けそうですね。まずは計算時間を気にせず考えていきます。
dpの設計は次の通りです。
dp[i][j] : マス（i, j）への行き方
シンプルですね。ここで、マス（i, j）から右、下、右下方向へ移動をしていきます。
まず、右移動です。j+1のマスがブロックかどうかを判定し、もし移動可能であれば、
dp[i][j+1] += dp[i][j]
として更新します。クイーンは任意のマスまで移動できますので、これを壁にぶつかるまで続けます。
dp[i][j+2] += dp[i][j]
dp[i][j+3] += dp[i][j]
...
他の方向も同様に行います。下方向では
dp[i+1][j]+=dp[i][j]
右下方向では
dp[i+1][j+1] += dp[i][j]
です。次に一つ進めて(i, j+1)としましょう。この場合も同様に
右：dp[i][j+2] += dp[i][j+1]
下：dp[i+1][j+1] += dp[i][j+1]
右下：dp[i+1][j+2] += dp[i][j+1]
と更新します。これを右下(h-1, w-1)まで行えば無事に答えが求まります。
さて、冒頭にも申しましたがこのままでは計算時間がO(n^3)？（おそらくそうです）になり、n<=2000ですので間に合いません。高速化しましょう。
ここで、右方向の遷移のみに注目をして考えていきます。
(i, j)からの遷移は上で書いた通り、
dp[i][j+1] += dp[i][j]
dp[i][j+2]+= dp[i][j]
dp[i][j+3] += dp[i][j]
dp[i][j+4] += dp[i][j]
...
次に(i, j+1)からの遷移は
dp[i][j+2]+= dp[i][j+1]
dp[i][j+3] += dp[i][j+1]
dp[i][j+4] += dp[i][j+1]
...
同様に(i, j+2)
dp[i][j+3] += dp[i][j+2]
dp[i][j+4] += dp[i][j+2]
...
(i, j+3)
dp[i][j+4] += dp[i][j+3]
...
となります。ここで、各マスがどのように更新されているかまとめてみましょう。
dp[i][j+1] += dp[i][j]
dp[i][j+2] += dp[i][j]+dp[i][j+1]
dp[i][j+3] += dp[i][j]+dp[i][j+1]+dp[i][j+2]
dp[i][j+4] += dp[i][j]+dp[i][j+1]+dp[i][j+2]+dp[i][j+3]
同じ要素がいっぱい登場しています。これってなんか累積和が使えそうですよね。ということで、(i, j)より左にある横要素の和をX[i][j]とします。ここで、X[i][j]=dp[i][j-1]+dp[i][j-2]+...であり、dp[i][j]を含みません。これを用いれば更新式は
dp[i][j+1] += X[i][j+1]
dp[i][j+2] += X[i][j+2]
dp[i][j+3] += X[i][j+3]
dp[i][j+4] += X[i][j+4]
となります。
下方向、右下方向も同様に累積和で表せます。下方向の累積和をY[i][j],右下方向の累積和をZ[i][j]とすれば、dp[i][j]は
dp[i][j] = X[i][j]+Y[i][j]+Z[i][j]
となります。ここで、先にも述べましたが、
dp[i][j]:(i, j)マスへの行き方
X[i][j] : (i, j-1)までの横方向の累積和
Y[i][j] : (i-1, j)までの縦方向の累積和
Z[i][j] : (i-1, j-1)までの斜め方向の累積和
であり、累積和には(i, j)は含みません。
あとは実装するだけです。このとき、数値が大きくなる場合がありますので10^9+7で適宜抑えてあげます。long longで扱っておけば、はみ出すことはないでしょう。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
using P = pair<int, int>;
const int mod = 1e9 + 7;
int main()
{
int h, w;
cin >> h >> w;
vector<vector<bool>> g(h, vector<bool>(w));
rep(i, h)rep(j, w)
{
char c; cin >> c;
if (c == '#') g[i][j] = false;
else g[i][j] = true;
}
vector<vector<ll>> dp(h, vector<ll>(w));
vector<vector<ll>> row(h, vector<ll>(w));
vector<vector<ll>> col(h, vector<ll>(w));
vector<vector<ll>> dia(h, vector<ll>(w));
dp[0][0] = 1;
row[0][0] = 0;
col[0][0] = 0;
dia[0][0] = 0;
rep(i, h)rep(j, w)
{
int x = j;
int y = i;
//‰¡•ûŒü
int rx = x + 1;
if (rx < w && g[y][rx])
{
row[y][rx] += row[y][x] + dp[y][x];
row[y][rx] %= mod;
dp[y][rx] += row[y][rx];
dp[y][rx] %= mod;
}
//c•ûŒü
int dy = y + 1;
if (dy < h && g[dy][x])
{
col[dy][x] += col[y][x] + dp[y][x];
col[dy][x] %= mod;
dp[dy][x] += col[dy][x];
dp[dy][x] %= mod;
}
//ŽÎ‚ß•ûŒü
if (rx < w && dy < h && g[dy][rx])
{
dia[dy][rx] += dia[y][x] + dp[y][x];
dia[dy][rx] %= mod;
dp[dy][rx] += dia[dy][rx];
dp[dy][rx] %= mod;
}
}
cout << dp[h - 1][w - 1] << endl;
return 0;
}私の手法の場合は累積和を足し合わせて答えを求めているので、dpの更新の前に累積和の更新をする必要があります。また、dp[0][0]=1ですが、累積和は(i,j)より前の要素の累積和のため[0][0]=0で探索を開始しています。
F Confluence
集団登校のお話です。a さんはクラス 1 に所属しています。登校途中で aさんは クラス2に所属するbさんと合流しました。はたまた、クラス2のcさんは、同じくクラス2のdさんと会いました。さて、ここでaさんが属する登校班にクラス2の人は何人いるでしょう？というような、合流、判定を適切に繰り返しましょう。
という問題です。
属する人たちを管理するということで、UnionFIndを用いて解いていきます。ただ、今回は「aが所属するグループの人数」ではなく、「aが所属するグループのなかで”クラス x の”人数」ということで、管理しなければならない情報が増えています。
まずはそれに対応しましょう。通常のUnionFindでは人数分の配列を用意して、要素に「根である」か「所属する根の番号」を入れることにより集合を管理します。所属自体はわかるので、「所属する根の集合におけるクラス x の人数」を管理できるように機能を追加します。
今回は連想配列（map）を用います。
map[I] : クラス i の人数
というものを、配列で管理します。つまり、
vector<map<int,int>> v( n )
と宣言してあげれば、
v[i]にはmap[j]が入っている。これは、人 i がいる集合における、クラス j の人数
を表していることになります。これにより、集合とクラスを管理できるようになりました。
次に人が合流した際におけるmapの更新について考えます。集合の更新に関しては、通常のUnionFindと同様です。
mapに関してですが、まず集合が結合、吸収されるために、どちらかの根の情報が更新されます（今まで根だったけど、枝になる）。次に枝になった方に含まれるクラスの人数の情報を新しい根へ加算していきます。文字で書くとややこしいですが、以下の図やコードをみると理解しやすいと思います。
また、今回はmapの要素を結合しているため通常よりも計算量がかかります（キーの要素取得でO(log n)かかるそうです）。
そのため、マージに関する工夫を用います。ざっくりと説明します（詳しくは別で書きたいと思います）。
結論から申しますと、マージの際には集合のサイズが小さい方を大きい方に結合するという構造を用いています。
まず、UnionFindの要素を結合する場合には、「結合される側」ではなく「結合する側」分の計算量がかかります。ということで、小さい方をくっつけた方が良い気がしてきます。また、結合をする際に小さい方の集合のサイズをSとしたとき、結合後のサイズは2S以上になることが保証されています。つまり、１回の結合で集合は2倍以上大きくなります。全要素を結合したときのサイズは n となりますので、一つの要素の結合回数は高々、log n に収まります。
あとは、なんでしょう。根が深くなるのを防いだり、ショートカット回数を減らしたりと、いろいろなメリット？言い方？があります。
説明は以上です。あとは、UnionFindを拡張して、頑張って計算してもらいましょう。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
using P = pair<int, int>;
template<typename T>
struct UnionFind {
vector<int> d;
//mp[i][c]
//人iが所属する集団のクラスcの人数
vector<map<int, int>> mp;
UnionFind(int n = 0) : d(n, -1), mp(n) {}
int find(int x) {
if (d[x] < 0) return x;
return d[x] = find(d[x]);
}
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
//大<-小にマージ
if (d[x] > d[y]) swap(x, y);
//xの方が大きい
//p.first : クラス番号
//p.second : クラスに所属する人数
for (auto p : mp[y])
{
mp[x][p.first] += p.second;
}
d[x] += d[y];
d[y] = x;
return true;
}
int size(int x) { return -d[find(x)]; }
bool same(int x, int y) { return (find(x) == find(y)); }
};
int main()
{
int n, q;
cin >> n >> q;
UnionFind<int> uf(n);
rep(i, n)
{
int c; cin >> c;
++uf.mp[i][c];
}
rep(i, q)
{
int qi; cin >> qi;
if (qi == 1)
{
int a, b; cin >> a >> b;
--a; --b;
uf.unite(a, b);
}
else
{
int x, y; cin >> x >> y;
--x;
cout << uf.mp[uf.find(x)][y] << endl;
}
}
return 0;
}以前まで使用していた、UnionFindと大体は同じなのですが、 以前はマージテクに関して誤った実装をしていました。答え自体には影響はないのですが、高速化ができていない状態でした。
そのため、今回の問題にて訂正をしておきました。
C問題のnext_permutationであったり、いもす法であったり、はたまたUnionFindの拡張であったりと、たくさんの学びがあった回でした。一歩ずつ成長してきたいものです。
この記事が気に入ったらサポートをしてみませんか？