ABC179の解答
ABC179の解答を書いていきます。
問題はこちらから。
A Plural Form
高橋語と呼ばれる言語を複数形にする問題です。文字列？英単語？sが与えられたとき、末尾がsならes、それ以外ならsを追加します。
文字列の操作ができれば簡単です。末尾要素へのアクセスは、s[s.length()-1]としてもいいで取れます。また、stringにはback()という関数があるみたいですね。放送を見て知りました。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main(){
string s;
cin >> s;
int l = s.length();
if(s[l-1] != 's') s += "s";
else s += "es";
cout << s << endl;
return 0;
}この条件の他にchならes, yの前が子音ならiesみたいなものが追加された問題をc++始めたばかりの頃にやりました。文字列の基本問題です。
あと、これを全ての英単語に対応させるのはどうなのでしょうか、無理なのですかね。
B Go to Jail
サイコロのゾロ目を確認する問題。サイコロ2つをn回投げて、そのうちにゾロ目が3連続で出たかどうかを判定します。
入力をとってきてゾロ目かどうかを判定、ゾロ目ならcountを+1、違ったら0に戻す。とやれば簡単に判定できます。
最高連続記録を求める必要もないので、3連続したら、切り上げてしまいましょう。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main(){
int n;
cin >> n;
vector<bool> eq;
rep(i,n){
int a, b;
cin >> a >> b;
if(a == b) eq.emplace_back(1);
else eq.emplace_back(0);
}
int cnt = 0;
rep(i,n){
if(eq[i]) cnt++;
else cnt = 0;
if(cnt >=3){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}問題名を見てパッとモノポリーが浮かびました。研究室に好きな同期がおり、モノポリーセットが片隅に鎮座してました。でも、3連続で刑務所行きっていうルール初めて知りました。ローカルルールなのでしょうか。
C A * B + C
自然数n = a * b + cを満たす自然数a, b, cの組の数を求める問題。
愚直にfor文を回すと、n < 10^6のO(n^3)なので、間に合いません。そのため、for文をどうやって減らすかを考えていきます。
まず、3重ループの場合は
for(a,n)for(b,n)for(c,n) if(n == a * b + c ) ++cnt
こんな感じですかね。
一つ減らします。足し算である c に注目します。c を n 側に移項すると右辺はa * bの1項になります。また、n - cを新しい変数 m とします。cは自然数なので、mの取りうる範囲は
m <= n - 1
となります。このとき、a * bが m 以下となれば条件を満たします。a * bでnに届かない分を c にて補完するイメージです。
for(a, n)for(b, n) if(n -1 < a * b) cnt++
2重になりました。がまだ計算が間に合いません。もう一つ減らします。
例を出して考えます。n = 11としましょう。m = 10です。
mに対応するa, b のaを固定します。a = 3のとき、対応するはb = 1, 2, 3の3通りです。この3という数をfor文を回さず求めます。
3 * 3という掛け算は3 + 3 + 3 となり、3を3回足しますよという意味です。10 を 3で割った商は3となり、10以下で3を足すことができる最大の回数となります。もちろんですが、3以下であれば、掛け算は10を超えません。
これを一般化すると、bの数 = m / aです。そのため、a, b, cの数は、
for(a,n) cnt += (n-1) / a
となります。これでO(n)になったので実装します。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main(){
int n;
cin >> n;
int n1 = n-1;
int ans = 0;
for(int i = 1; i < n+1; i++){
ans += n1 / i;
}
cout << ans << endl;
return 0;
}アルゴリズム自体は小学生でも理解できるものですが、四則演算を組み合わせるなかなかに面白い問題なのではないのでしょうか。
D Leaping Tak
進むマスが定められたすごろくでゴールまでの行き方の数を調べる問題です。
1マス目から始まり、nマス目まで行くのですが、進めるマスが区間により与えられます。1~3, 6~7とかだったら、1,2,3,6,7のサイコロを振る感じです。
まず、解法としてdpが考えられます。例えば、1,2のサイコロがあったします。２マス目までの行き方は1通りです。３マス目までの行き方は、1からと2からの2通り、４マス目なら２と３ですが、３マス目まで２通りの行き方があるので１＋２で３通りとなります。これをnまでやれば答えが出ます。
ただし、この手法だとO(n^2)になるので間に合いません。
計算時間削減のために「進めるマスが区間により与えられる」ことに注目します。2~4と与えられた場合、i マス目は i+2, i+3, i+4マス目の更新に寄与します。逆にいうと、iマス目は i-2, i-3, i-4マス目の３つの和により更新されるということです。
そのため、更新は値を先の要素に受け渡すのではなく、前の要素から受け取るイメージで行います。
i番目の更新は
dp[i] = dp[i-2] + dp[i-3] + dp[i-4]
とします。ただし、このままではアクセス数は変化しないので、区間和を保持してあげます。sumとでもしましょう。
sum[1] = dp[1]
sum[2] = dp[1] + dp[2]
sum[i] = dp[1] +dp[2] + ... +dp[i]
とすれば、dp[i]の更新は
dp[i] = sum[i-2] - sum[i-5]
で完了です。あとは、与えられた区間{l, r}に対応したsumで n までdpを回しましょう。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int mod = 998244353;
int dp[200010];
int main(){
int n, k;
cin >> n >> k;
vector<P> act;
vector<int> sum(n+1,0);
rep(i,k){
int l , r;
cin >> l >> r;
act.emplace_back(l,r);
}
dp[0] = 0;
dp[1] = 1;
sum[0] = 0;
sum[1] = 1;
for(int i= 2; i< n+1; ++i){
for(auto a : act){
int l = a.first;
int r = a.second;
l = max(0, i-l);
r = max(0, i-r-1);
int p = (sum[l] - sum[r]) % mod;
if(p < 0) p += mod;
dp[i] = (dp[i] + p) % mod;
}
sum[i] = (sum[i-1] + dp[i]) % mod;
}
cout << dp[n] << endl;
return 0;
}i - rなどにより配列の外に飛び出さないように注意しましょう。あと、c++だと%演算を正に戻す必要があります。
進み方が区間で与えられていることに注目すべきでした。ただ、時間を気にしないのであれば、dpの導入問題としてはうってつけなのではないでしょうか。
E Sequence Sum
数列の和を求める問題。
i 項目が i-1 項目の2乗をmで割った余りで構成される数列の和を求めます。
毎度のことながら愚直には解けません。
そのため、あまりの循環に注目します。数列はmで割った余りにより構成されるので、最大で0~m-1までのm種類しか存在しません。1ループのスコアを求めてしまえば、n が mよりも大きい際には、計算時間はmで押さえつけることができます。
ただし、この際にはきれいな和にはならず ρ のように尾びれのようなものがくっついた形になります。
初項7, m = 11とすると、
7 → 5 → 3 → 9 → 4 → 5 → ...
となり、7を尾びれにループします。そのため、ループが始まるまでの和、１ループの和、ループ回数、ループに満たなかった部分の和を求めてあげれば、答えが出ます。
実装の際には余りを記録しておく配列にて、インデックス番号で出た数字を、数値にて出現した場所を記録しておきます。はじめに-1で初期化をして、-1以外の数字の出現によりループを検知します。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main(){
ll n;
int x, m;
cin >> n >> x >> m;
vector<int> rem(m,-1);
ll ans = 0;
ll a = x;
int it = 0;
rep(i, n){
if(rem[a] != -1) break;
rem[a] = it;
ans += a;
a = (a * a) % m;
++it;
}
if(it == n){
cout << ans << endl;
return 0;
}
int its = rem[a];
int l = it - its;
vector<ll> sum(l+1);
sum[0] = 0;
rep(i,l){
sum[i+1] = sum[i] + a;
a = (a * a) % m;
}
ll r = n - it;
ans += (sum[l] * (r / l));
int r2 = r % l;
ans += sum[r2];
cout << ans << endl;
return 0;
}/ l でループ回数を求めたり、 % l で余りを求めたりと少し混乱しそうになりますが、落ち着いてやれば大丈夫です。また、ループ区間の和を求める際に、ループできなかった部分を迅速に出すために、部分和配列sumを用いています。
F Simplified Reversi
リバーシの問題。
n*nの盤面があり、フチの部分を除いた(n-2)*(n-2)マスに黒い石がおいてあり、右列と下行は白で埋め尽くされています。上行もしくは左列にq個白い石を置くクエリが与えられます。全てのクエリを順番に処理して行った時に盤面に残る黒い石は何個でしょう？という問題。
結論から言うと、今回はsegment treeにより解きました。seg木の基本的な機能として、「区間内の最小値の取得」と「1点更新」の２つがあります。後に述べますが、この機能を逆にして「1点の最小値の取得」と「区間の値を更新」とした方が、アルゴリズムとしては自然で理解しやすいと思います。先に今回実装した基本のseg木の方法を述べます。
私自身seg木は初めてで初めは理解できなかったので、気にせず通常の配列で考えます。あとで、時間削減に使います。
n-2の大きさの配列を2つ用意して、n-2で初期化をします。まず、白石を上列に置いて縦方向に石を取ることを考えます。n-2で初期化した配列のうち片方（xとします）を使います。
b番目に石を置く際には、xの中の b 番目からn-2番目までのなかの最小値を取得します。これが、取れる石の数になります。今回は1回目なので全部n-1がはいっていますが、、、
縦に取ったため、次から横とる際の石の数が減ってしまいます。そのため、もう一つの配列（yとします）を更新しておきます。
1回目でn-2個取得できたため、y の配列のn-2番目をbで書き換えておきます。そうすれば、次に横に置いた際には、次のbからn-2までの最小値が取得数になるため適切な値が取得できます。1点更新で操作が完了します。
ごちゃごちゃしてきたので、実際に数字をいれて考えます。
N =5 とします。そうすると、n-2の３*3の9マスに黒い石が存在している状態が初期位置になります。
初めに、上列の真ん中（b=1とする。）に石を置くと、xの配列は全部3ですので、3個取得できます。その後、yを更新します。yの3番目の要素(インデックスは0スタートだから2)をb = 1で更新します。
そのご、左列真ん中（b=1）に置いて、横の取得をします。
先ほど、yは更新してあるので、b=1からn-2＝3（インデックスだと２）までの要素の最小値は1なので、1個取得となります。
例えば、1回目のbが0なら、yには0がはいるので、横方向の取得は0になることがわかります。
これで、大体のアルゴリズムは完成しました。
１点問題となるのは取得した数を次の更新場所にしているので、更新をして行って、飛ばされてしまった部分を後から更新すると、不適切な更新が起こります。（b= 1で縦を3個取ったのちに、b=2で縦を3個とると、yの3番目の取得可能数が増加してしまう。）
そのため、いままでに更新した最も大きい列と行を保存しておきます。bがそれよりも小さい場合のみ更新をします。
アルゴリズムはこれで完成です。
あとは、ここにsegment treeを導入してあげます。
詳細は省きますが、木の構造をとり、根から2要素ずつをまとめ上げることにより、log Nオーダーで任意演算（基本は最小値演算）を可能とするデータ構造です。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T>
struct segtree{
const T inf = numeric_limits<T>::max();
int n;
vector<T> v;
segtree(int n_){ //引数のnだからn_,struct内のnと区別する。
int x = 1;
while(n_ > x) x *= 2;
n = x;
v.resize(2*n-1 ,inf);
}
void update(int k, T x){
k += n - 1;
v[k] = x;
while(k > 0){
k = (k - 1) / 2;
v[k] = min(v[k*2+1], v[k*2+2]);
}
}
T query(int a, int b) {return query_sub(a,b,0,0,n);}
T query_sub(int a, int b, int k, int l, int r){
if(b <= l || r <= a) return inf;
if(a <= l && r <= b) return v[k];
T c1 = query_sub(a, b, 2*k+1, l, (l + r) / 2);
T c2 = query_sub(a, b, 2*k+2, (l + r) / 2, r);
return min(c1, c2);
}
};
int main(){
ll n, q;
cin >> n >> q;
int mx,my;
mx = n-2, my = n-2;
segtree<int> sgx(n-2);
segtree<int> sgy(n-2);
rep(i,n-2) sgx.update(i,n-2);
rep(i,n-2) sgy.update(i,n-2);
ll w = 0;
rep(i,q){
int a, b;
cin >> a >> b;
b -= 2;
if(a == 1){
int y = sgx.query(b,n-1);
w += y;
if(mx > b){
sgy.update(y-1,b);
mx = b;
}
}
else{
int x = sgy.query(b,n-1);
w += x;
if(my > b){
sgx.update(x-1,b);
my = b;
}
}
}
ll ans = (n-2)*(n-2);
ans -= w;
cout <<ans << endl;
return 0;
}上の方の構造体がsegment treeです。詳しくはこちらから、
先に述べた通り、区間に関する更新をとるsegment treeについて述べます。こちらの方がアルゴリズムの理解は易しいと思います。
縦方向のb=1に置いてn-2個取得したのであれば、横方向の配列0~n-2までをb=1で更新します。そうすれば、取得数に関してインデックス番号の場所のみ検索すればよく、区間を考える必要がなくなります。その点にて取れる個数が1対1で対応してくれます。
だだし今回は、segment treeの基本構造を優先しました。
競技プログラミングの記事を書き始めて2ヶ月ですが、ようやくabcの問題であれば「はいはいセグ木ね」みたいに、アルゴリズムに抵抗がなくなるようになってきました。上を見れば青天井ですが、少しずつライブラリを整理していきちんまりと続けていこうと思います。
この記事が気に入ったらサポートをしてみませんか？