こんにちは。ほうれんです。
普段は AtCoder などで競技プログラミングを嗜んでいる人ですが、最近就職活動を考えるようになって、paiza を眺める機会が増えています。はよインターンやれや
paiza を見ていると「記事書こうぜ！」みたいなキャンペーンがあり、そういえば自分が解説する機会も中々なかったので、今回は Qiita コラボのS問題5問をざっくり(重要)と解説する記事を書こうと思います。ネタバレ防止で閉じてありますので、適宜開くなどしてください！
普段 C++ で競プロをやっているので、#include <bits/stdc++.h> using namespace std; その他マクロをある程度含んでいますが悪しからず(可能な限り消しています)。
paizaの問題って公開したらダメなんじゃないの？という方向け
この問題群は配信が終了したQiitaコラボの問題です。 問題に対して色々な記事が飛び交うキャンペーンだそうなので大丈夫です。村人たちの友好関係
解説
$N\leq 500, Q\leq 5\times 10^4$ なので、${\rm O}(NQ)$ とか辺りはそこそこ高速です。
友好度が大きい村人の組が優先される優先度付きキューを使います。
各クエリごとに、グループの入退が変わる村人 $i$ と、入退状態の異なる村人 $j$ に対して、$(i,j)$ を優先度付きキューに入れます。
そして、キューが空になるか、先頭の村人の組が異なるグループに属している状態になるまで先頭を削除します。
その状態で、キューが空ならば $0$ 、そうでないならば先頭の組の友好度が答えです。
計算量について考えます。優先度付きキューに入る要素は、各クエリ辺り ${\rm O}(N)$ 個であるから、全体を通して ${\rm O}(NQ)$ 個です。先頭の要素の削除の回数もそれを超えません。そして、優先度付きキューの値の追加/削除にかかる時間はサイズに対して対数時間なので、${\rm O}(NQ \log{NQ})$ 時間で解くことができました。
P.S. 結構制限時間ギリギリだったんだけど、もっと速い解があるのかな
(追記 24/08/22)
最大全域木、賢い たしかにその通りですね
となると、動的木とか平方分割でもっと計算量が軽くなりそう！みたいなことを考えてみたくなりますね。
コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
struct P{ int i,j; };
int main(){
int n,m,q;
cin >> n >> m >> q;
vector<vector<int>> a(n+2, vector<int>(n+2, 0));
while(m--){
int u,v,f;
cin >> u >> v >> f;
--u, --v;
a[u][v] = a[v][u] = f;
}
vector<bool> g(n+2, false);
g[n] = true;
auto compare = [&](P x, P y) -> bool {
return a[x.i][x.j] < a[y.i][y.j];
};
priority_queue<P, vector<P>, decltype(compare)> pq{compare};
pq.push({n, n+1});
while(q--){
char c;
int x;
cin >> c >> x;
--x;
g[x] = !g[x];
rep(i,n){
if(g[i]!=g[x]) pq.push({i, x});
}
while(g[pq.top().i]==g[pq.top().j]) pq.pop();
cout << a[pq.top().i][pq.top().j] << '\n';
}
return 0;
}
島探し
解説
各マスにおいて 1 であるマスに頂点があり、上下左右に頂点が連続しているところに辺が引いてあるようなグラフに対して、その連結成分の個数を求めてください、という問題です。
というわけで、探索アルゴリズム(BFS/DFS) か、素集合データ構造(UnionFind) を使って解きましょう。計算量は、BFS/DFSなら ${\rm O}(NM)$、UnionFindなら ${\rm O}(NM~\alpha(NM))$ です($\alpha$ はアッカーマンの逆関数)。
多分この5問の中で一番簡単だと思います。
コード1
#include <bits/stdc++.h>
using namespace std;
const int H[] = {1,0,-1,0}, W[] = {0,1,0,-1};
struct P{ int i,j; };
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>> a(m+2,vector<int>(n+2,0));
for(int i=1;i<=m;++i)for(int j=1;j<=n;++j) cin >> a[i][j];
int ans = 0;
for(int i=1;i<=m;++i)for(int j=1;j<=n;++j){
if(a[i][j]){
++ans;
a[i][j] = 0;
queue<P> que;
que.push({i,j});
while(que.size()){
auto [p,q] = que.front();
que.pop();
for(int k=0;k<4;++k){
int np = p+H[k], nq = q+W[k];
if(a[np][nq]){
a[np][nq] = 0;
que.push({np,nq});
}
}
}
}
}
cout << ans << '\n';
return 0;
}
コード2
#include <bits/stdc++.h>
using namespace std;
const int H[] = {1,0,-1,0}, W[] = {0,1,0,-1};
struct UnionFind{
int cnt;
vector<int> par, siz;
UnionFind(int N) : par(N), siz(N,1){
for(int i=0;i<N;++i) par[i] = i;
cnt = N;
}
int root(int x){
if(par[x]==x) return x;
return par[x] = root(par[x]);
}
bool unite(int x,int y){
x = root(x); y = root(y);
if(x==y) return false;
cnt--;
if(siz[x]<siz[y]) swap(x,y);
par[y] = x;
siz[x] += siz[y];
return true;
}
};
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>> a(m+2,vector<int>(n+2,0));
for(int i=1;i<=m;++i)for(int j=1;j<=n;++j) cin >> a[i][j];
int ans = 0;
UnionFind uf(n*m);
for(int i=1;i<=m;++i)for(int j=1;j<=n;++j){
if(a[i][j]){
++ans;
for(int k=0;k<4;++k){
int ni = i+H[k], nj = j+W[k];
if(a[ni][nj]){
ans -= uf.unite((i-1)*n+j-1, (ni-1)*n+nj-1);
}
}
}
}
cout << ans << '\n';
return 0;
}
mod7占い
解説
動的計画法(DP)の問題です。
${\rm DP}[i][j][k] = (i~枚目まで見て、j~枚とった時のカードの合計~{\rm mod~}~ が~k~である)$
を遷移することで ${\rm O}(N)$ 時間で正解することができます。
入力で与えられる数値が最大で $2^{32}-1$ であり、int ではオーバーフローしてしまう点に注意しましょう。
別にDPじゃなくても解けますね…自分はDPがシンプルで良いと思いましたが (追記 24/07/23)
コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; ++i)
int main(){
int n;
cin >> n;
vector<vector<ll>> dp(4, vector<ll>(7, 0));
auto upd = dp;
dp[0][0] = 1;
while(n--){
unsigned int a;
cin >> a;
a %= 7;
rep(i,4)rep(j,7) upd[i][j] = dp[i][j];
rep(i,3)rep(j,7) upd[i+1][(j+a)%7] += dp[i][j];
swap(dp, upd);
}
cout << dp[3][0] << '\n';
return 0;
}
文字列収集
解説
prefix の探索を行う問題です。こういう問題には trie木 というデータ構造が有効です。
トライ木の各頂点に「この頂点に辿り着いたら答えはいくつか」という情報を持たせるのがシンプルで良いと思います。
コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
struct T{
vector<int> to;
int val = 0;
T(){ to.assign(26,-1); }
};
int main(){
int n,m;
cin >> n >> m;
vector<T> trie(n*100);
int siz = 1;
while(n--){
string s;
int p, now = 0;
cin >> s >> p;
for(char c:s){
c -= 'a';
if(trie[now].to[c]<0) trie[now].to[c] = siz++;
now = trie[now].to[c];
trie[now].val += p;
}
}
while(m--){
string s;
cin >> s;
int now = 0;
for(char c:s){
c -= 'a';
now = trie[now].to[c];
if(now<0) break;
}
cout << (now<0 ? 0 : trie[now].val) << '\n';
}
return 0;
}
十億連勝
えー むずいと思います(合わせるのがちょっと大変だった) AtCoderでも水diffくらいはあるんじゃないでしょうか？
解説
とりあえず、連勝がスタートする所は明らかにステージの最初のタイミングです。なので、『最後に負けたステージがどこか？』という情報があると嬉しいことが分かります。
よりもう少し具体的には、DP をします(このコラボ DP 多くない？)。bool値 ${\rm flag}$ をおいて、次の状態を持つことにします。また、最大連勝数が $X$ を超えてしまった場合については除外するものとします。
${\rm DP}[i][{\rm flag}] = (最後に負けたのがステージ~i~で、「負けた時点で最大連勝数が~X~である」 が {\rm flag} であるときの場合の数)$
これを遷移していき上手く合計を合わせることで、${\rm O}(N^2)$ 時間で正解することができます。実装も参考にしてください。よく分からない！とかもっといい方法あるよ！とかあればコメントください。
詳しい説明
修正がてら書く気になったので(追記 24/07/23)
$i\in \{0,\ldots,n\}$ と ${\rm flag}\in\{\rm False, True\}$ について、 ${\rm DP}[i][{\rm flag}]$ を求めたいです。$i=0$ は負けていないことを表し、自明に ${\rm DP}[0][{\rm False}]=1, {\rm DP}[0][{\rm True}]=0$ です。
$i\geq 1$ の ${\rm DP}$ の各値について考えます。「連勝が $X$ 未満で途切れる」場合と「連勝がちょうど $X$ で途切れる」場合に分けます。その上で、${\rm DP}[j]~(j<i)$ からの寄与、すなわち「ステージ $j+1$ から連勝し、ステージ $i$ のどこかで負ける状況」を考えます。${\rm DP}[i]$ を求めるとき、${\rm DP}[j]$ は全て求まっているものとします。
・連勝が $X$ 未満で途切れる場合
ステージ $i$ で負けるタイミングとして考えられる場合の数を $p_j$ とします。このとき、ある $j$ からの ${\rm DP}[i][{\rm flag}]$ への寄与は、${\rm DP}[j][{\rm flag}] \times p_j$ です。また、
p_j = \max\Bigl(\min\bigl(X-\sum_{k=j+1}^{i-1}{A_k}, A_i\bigr), 0\Bigr)
のように表せます。連勝が $X$ 未満で途切れる場合については、全ての $j<i$ の寄与を考えれば十分です。
・連勝がちょうど $X$ で途切れる場合
まず、連勝がちょうど $X$ で途切れるような負け方が存在する $j$ の集合を $J$ とします。すると、$j\in J$ は以下を満たします。
\sum_{k=j+1}^{i-1}{A_k}\leq X~かつ~\sum_{k=j+1}^{i}{A_k}> X.
この判定は容易に実装できます。また、そのような負け方が存在するとき、その場合の数は明らかに $1$ です。
これらの考察から遷移式は、
\begin{cases}
{\rm DP}[i][{\rm False}] = \sum_{k=0}^{i-1}{\bigl({\rm DP}[k][{\rm False}]\times p_k\bigr)},\\
{\rm DP}[i][{\rm True}] = \sum_{k=0}^{i-1}{\bigl({\rm DP}[k][{\rm True}]\times p_k\bigr)} + \sum_{k\in J}{\bigl({\rm DP}[k][{\rm False}]+{\rm DP}[k][{\rm True}]\bigr)}.
\end{cases}
と表せます。
・実装について
大筋は解説の内容をシンプルに実装してやれば ${\rm O}(N^2)$ になります。しかし、そのままのDP配列から最終的に求めたいものを計算するのは少し面倒です(難しくはない)。ここで、$1$ 試合だけからなるダミーのステージ $N+1$ を用意し、この試合に負けることを考えます。すると、${\rm DP}[N+1][{\rm True}]$ に求めたいものが集まってきます。これを出力すればよいです。
コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; ++i)
constexpr ll MOD = 1e9;
int main(){
int n,x;
cin >> n >> x;
vector<ll> a(n+1);
rep(i,n) cin >> a[i];
a[n] = 1;
vector<vector<ll>> dp(n+2, vector<ll>(2, 0));
dp[0][0] = 1;
rep(i,n+1){
ll tot = 0;
for(int j=i;;){
ll t = min(a[i], x-tot);
rep(k,2) dp[i+1][k] = (dp[i+1][k] + dp[j][k] * t) % MOD;
if(tot+a[i]>x) dp[i+1][1] = (dp[i+1][1] + dp[j][0] + dp[j][1]) % MOD;
if(!j) break;
tot += a[--j];
if(tot>x) break;
}
}
cout << dp[n+1][1] << '\n';
return 0;
}
おわりに
この記事では5問のS問題の解説を書きました。
解説の調子が結局競プロer向けになってしまったと思っているので、不親切だと感じる部分があるかもしれません。各データ構造・アルゴリズムについては興味があれば調べて頂ければ幸いです。
競プロ楽しいよ やろう