ABC182の解答
AtCoder Beginner Contest 182を解き終わったので解答を書いていきます。
問題はこちらから、
難易度はこんな感じでした。
A 0 （灰）
B 72 （灰）
C 235 （灰）
D 656 （茶）
E 1056 （緑）
F 2102 （黄）
では、書いていきます。
A twiblr
twiblrというsnsについての問題です。このsnsでは、フォロー数が2*(フォロワー数)+100を超えない範囲でフォロー数を増やせます。現在のフォロワー数は a でフォロー数が b のとき、フォロー数は後何人増やせますか？
という問題。
フォロー数の上限から現在のフォロー数を引いてあげれば答えが出ます。具体的には
2 * a +100 - b
ですね。サクッと実装しましょう。
#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;
int main()
{
int a, b;
cin >> a >> b;
int ans = 2 * a + 100 - b;
cout << ans << endl;
return 0;
}フォローとフォロワーを間違えなければ大丈夫です。
B Almost GCD
数列(a1, a2, ... ,an)が与えられます。数列の数のうち２以上の整数 k で割り切れるものの数をGCD度と定義します。GCD度が最大となる k を一つ求めましょう。
という問題。
ai を割り切る数について少し考えます。k を2から少しずつ大きくしていくのですが、果たしてこの k はどこまで大きくなるのでしょうか。ここで、20 を割り切ることのできる数を考えます。小さいほうから、
2, 4, 5, 10, 20
となりますね。ここで、大事なのは20よりも大きい数では絶対に割り切れないということです。つまり、ai を割り切る数を考える際には、2~ai までを試せばよいのです。
本問題では、数列の長さ n、数列の各要素 aiに関して
1 <= n <= 100
2 <= ai <= 1000
という制約があるので、最大ケースにおいても10^5で収まります。
したがって、
kを2からaiの最大値（または1000）まで増加させながら、
a1からanまで 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;
int main()
{
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int amax = 0;
rep(i, n) amax = max(a[i], amax);
int tmax = 0;
int ans;
reps(i, 2, amax + 1)
{
int ta = 0;
rep(j, n) if (a[j] % i == 0) ++ta;
if (tmax < ta)
{
tmax = ta;
ans = i;
}
}
cout << ans << endl;
return 0;
}本問題のように制約が緩い場合においても、制約が解法に結びつくので、しっかりと確認をして解きましょう。ということなんですね。たぶん。
あとは、最大値のみならず最大値を取る k も忘れずに保持するようにしましょう。
C TO 3
各桁に0 が出現しない正の整数が与えられます。n の桁数を k とします。 n の桁を 0 個以上 k 個未満消去することで、3の倍数を作りたいです。この時に、3の倍数が作れるかどうかを判定し、できる場合には作るのに必要な最小の消去する桁数を求めましょう。
という問題。
まずは3の倍数の判定方法について考えましょう。 例として100の位がa、10の位がb、1の位がc となる3桁の数を考えます。この数は以下のようにあらわされます。
abc(10) = a * 100 + b * 10 + c
変形していきます。
= a * 99 + a + b * 9 + b + c
= 3 * (33 * a + 3 * b) + (a + b + c)
1項目は明らかに3の倍数です。ということで、a+b+cが3の倍数であればよさそうですね。
今回は3桁でやりましたが、桁数が増えても同様の議論が成り立ちます。
したがって、3の倍数の判定法は、
各桁の和が3の倍数であるかどうか
となります。
3の倍数の判定法がわかりました。ここで、もう一つ大切なことは
各桁の和が大切であり、その順番は関係しない
ということです。そのため、本問題では、各桁を3で割った余りで3つに分類し、それぞれの個数を求める。そして、1, 2余る数を減らすことにより3が作れるかを判定していきます。
各桁の数を分類したのち、3の倍数になるかどうかを if 文にて書いても良いのですが、こういう面倒くさいところはプログラムに任せてしまいましょう（って公式放送で言ってました。コンテスト中の私はif で分けながら頑張りました。地獄でした。）。
そのために、グループ分けする際に各桁の和も保持しておきます。
桁をいくつか消していくのですが、1, 2においても3個以上消すことはあり得ません。なので、0~2個消した時の各桁の和が3で割れるかどうかを判定します（と書きましたが、これすらもめんどくさいなら全部消しましょう）。3の倍数になったなら、消した桁数を最小値と比べて、より小さければ更新しましょう。
注意点として、余り1 が1個しかない場合などは2個消さないようにしましょう。また、3桁以上なら確実に3の倍数が作れます。しかし、逆を言うと1桁, 2桁の場合はできない可能性があります。桁数分消してしまったら「ダメ」という処理を忘れないようにしましょう。
実装です。
#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;
const int inf = 1e9;
int solve1()
{
string s;
cin >> s;
vector<int> r3(3,0);
int l = s.length();
rep(i,l)
{
int d = s[i]-'0';
++r3[d%3];
}
int r = r3[1] + r3[2]*2;
int ans = inf;
rep(i1,3)rep(i2,3)
{
if(i1 > r3[1]) continue;
if(i2 > r3[2]) continue;
int tr = r - i1 - i2*2;
if(tr % 3 == 0)
{
ans = min(ans,i1+i2);
}
}
if(ans == l) ans = -1;
cout << ans << endl;
return 0;
}
int main()
{
solve1();
return 0;
}また、別解法としてbinaryで全探索してしまうというものがあります。試験後は「bit全探索」がtwitterのトレンドに入っていてびっくりしました。コンテスト中には全く浮かばなった手法ですので、「なんのこった？」って感じでしたが、勉強のために実装をしておきました。
4桁の数を例にざっと説明します。
4ビット用意して、0001(2)から1111(2)まで回して、0の桁の数を消す。
とやってあげます。7623(10)で1001(2)なら73(10)になるという感じですね。
補足として、本問題は桁数の制約が18以下であるため、bit全探索をしても、
2^18 = 262144
の計算量で収まるからという前提があります。ここ大事です。
bit全探索
const int inf = 1e9;
int solve2()
{
string s;
cin >> s;
vector<int> d;
int l = s.length();
rep(i, l) d.emplace_back(s[l-1-i]-'0');
int ans = inf;
reps(i,1,(1<<l))
{
ll ts = 0;
int cnt = 0;
ll a = 1;
rep(j,l)
{
if((i & (1<<j)) != 0)
{
ts += d[j]*a;
a*=10;
}
else ++cnt;
}
if(ts % 3 == 0) ans = min(ans, cnt);
}
if(ans == inf) ans = -1;
cout << ans << endl;
return 0;
}私は本問題に60分ぐらいかけて悩みに悩んだので、全探索をぱっと書くべきでした。まだまだ勉強が足りませんね。
D Wandering
数列 a1, a2, ... , an が与えられます。数直線上の座標 0 に置かれているロボットが次のように動きます。
正の向きに a1 進む。
正の向きに a1 進み、正の向きに a2 進む。
正の向きに a1 進み, 正の向きに a2 進み、... 、正の向きに an 進む。
動作中における座標の最大値はいくつでしょう。
という問題。
ai が全部正なら簡単ですね。一番最後が最大値です。ただ、そうはいきません。負の数も現れます。
また、制約が
1 <= n <= 200000
ですので、愚直にシミュレーションすることもできません。うまいことやりましょう。
abc182の感想でも書きましたが、本問題を見たときに次の問題がぱっと浮かびました。
10mの井戸の底にカエルがいる。1日で3m登り、寝ている間に2ｍずり落ちる。井戸から出られるのは何日後か？
1日で差し引き1ｍ登れるので、脱出までは10日。というのは誤りで、8日目の最大到達点は、8日目の開始点7m+1日の最大距離3mで 10mとなるので、この時点で脱出できます。もうちょっと詳しく書くと、1日で 1m 進むため、2日目の終了点は2mなのですが、その途中では4mまで到達しているのです。
本問題もなんとなく同じ感じがしませんか？
1~n日目まであって、前日の終点からその日の進む、戻るの結果を足したものが次の日の開始点となります。ただし、最大到達点はその日の進む、戻るのどっかに存在するかもね。っていう話です。
ということで、本問題において、到達した最大値を求めていきます（カエルの場合、1日目の 3 m、2日目の 4 m , 8日目の10 mに該当）。
これは、「各日の終点」と「１日における正の変位の最大値」の和で求めることができます。
まずは「各日の終点」（カエルの場合、1日目の1m、2日目の2m）を求めます。
そのために、i 日目の進む、戻るの結果の変位、つまり i 日目に進める距離をを考えます(カエルの場合 1 mに該当)。これは、問題文に与えられている通り、a1 から ai までの累積和となります。a1 から ai までの累積和を si とすると、i 日目には si m 進めることができます。
si を加算していくと、i 日目の終点の座標を取得することができます。これを累積和の累積和と表現している方もいらっしゃいました。
次に「１日における正の変位の最大値」(カエルの場合、一律 3 m)を求めます。
i 日目における一日の変位の最大値は、a1からaiまでを加算していき、j ( j<=i )までの和と j -1 項までの和の大きいほうになります。
このとき、注意しないといけないのが、例えば3日目の最大値を出す際に、4日目以降の変位を用いてはいけないことです。書いてる分には当たり前なのですが、私が実装した際には少し頭がこんがらがりました。
図で表すとこんな感じです。例えば、3日目は1だけ進むのではなく、3日目以前の全ての遷移を行っています。また、矢印の先端が、その日1日の差し引きの変位量となります。
以上より、「各日（前日）の終点」と「１日における正の変位の最大値」を求めることができました。この2つの和を保持して今までの値よりも大きかったら更新しましょう。
#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;
const ll inf = 1e18;
int main()
{
int n;
cin >> n;
vector<ll> a(n);
rep(i, n) cin >> a[i];
vector<ll> sa(n);
vector<ll> ma(n);
sa[0] = a[0];
//１日で進む距離を計算
reps(i, 1, n) sa[i] = a[i] + sa[i - 1];
ll tm = 0;
ll np = 0;
//１日の最大値
rep(i, n)
{
np += a[i];
tm = max(np, tm);
ma[i] = tm;
}
ll mp = 0;
ll ans = 0;
//最大到達点
rep(i, n)
{
ans = max(ans, mp + ma[i]);
mp += sa[i];
}
cout << ans << endl;
return 0;
}自分の中では理解できているつもりでしたが、この説明を書くのに非常に苦戦しました。それほどややこしいということですね。
また、某予備校の某科目の某有名な先生が「複雑な問題を考えるときは、とっても単純な1例と対比することが重要」とおっしゃってました。この問題ではカエルの例ですね。わからなくなってしまったら、カエルを軸にもう一度考えてみてください。
それでもわかりにくければご指摘いただけると幸いです。
E Akari
盤面の上に、いくつかの光源と壁がおかれています。光源はその上下左右のマスを壁にぶつかるまで照らすことが可能です。さて、光が届いているマスは何マスありますか？
という問題。
これを愚直に解こうとすると、一つの光源につき縦 h マス、横 w マス見る必要があるので、結果として、(h + w) * n 回の計算が必要となります。 公式解説曰く、これでは間に合わないそうなので、高速化しましょう。
まず、光の広がりを縦と横に分けて考えます。まずは横を考えましょう。
当然、光源から出た光は横方向に広がっていきます。しかし、縦の光がなくなったために、次のことが言えるようになります。
光を広げていき、
該当マスがすでに明るければその光源を追加しても範囲は変化しない。
（探索済み）
該当マスが暗い場合には、その光源の光が届く範囲はすべて暗い。
（未探索）
ということがわかります。探索済みの場所には何もしません。
このようにすれば、各マスに対して最大でも光が1回しか届かない（1度しか探索しない）ので、横方向では h * w の計算量で済みます。
縦の光も横と同様です。
最後に縦と横でどちらか一方でも光が届いている場所の数をカウントしましょう。縦と横の両方の光が当たっている場合はより眩しくなりますが、他と同じく1回のカウントとなります。
アルゴリズムはこんな感じです。
実装に関して少し書きます。
電球を置く位置に光が届いていたらその電球をスキップしています（探索済み）。また、光が壁にぶつかる処理を、横方向を例に説明します（a行b列に電球が存在）。まずは、該当の a 行に存在する壁(a行c列)を取得します（このために、行、列から電球の列、行を逆引きできる配列を用意）。次に、０, b, c, w-1を小さい順に並べ替えます。今回はb < c とします。その後、a行の [0, c)列を照らしてあげましょう。ここで、行の端なら閉区間 " [ ] " , 壁なら開区間 " ( ) " になる点に注意しましょう。壁が複数ある場合（a行c列、a行d列, a行e列）には, 0, b, c, d, e, w-1の並べ替えになります。0, c, d, b, e, w-1の順番としましょう。この場合には開区間 (d, e)を照らしましょう。
さて、実装です。
#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 h, w, n, m;
cin >> h >> w >> n >> m;
vector<vector<bool>> roomh(h, vector<bool>(w));
vector<vector<bool>> roomw(h, vector<bool>(w));
vector<P> li;
//壁の位置を逆引き
vector<vector<int>> wh(h);
vector<vector<int>> ww(w);
rep(i, n)
{
int a, b;
cin >> a >> b;
--a; --b;
li.emplace_back(a, b);
}
rep(i, m)
{
int c, d;
cin >> c >> d;
--c; --d;
wh[c].emplace_back(d);
ww[d].emplace_back(c);
}
//横方向
rep(i, n)
{
int a, b;
a = li[i].first;
b = li[i].second;
if (roomh[a][b]) continue;
vector<int> tw = wh[a];
sort(tw.begin(), tw.end());
int l = 0;
int r = w - 1;
for (auto ttw : tw)
{
if (ttw < b) l = ttw + 1; //開区間により+1
if (b < ttw)
{
r = ttw - 1; //開区間により-1
break;
}
}
reps(j, l, r + 1) roomh[a][j] = true;
}
//縦方向
rep(i, n)
{
int a, b;
a = li[i].first;
b = li[i].second;
if (roomw[a][b]) continue;
vector<int> tw = ww[b];
sort(tw.begin(), tw.end());
int s = 0;
int t = h - 1;
for (auto ttw : tw)
{
if (ttw < a) s = ttw + 1;
if (a < ttw)
{
t = ttw - 1;
break;
}
}
reps(j, s, t + 1) roomw[j][b] = true;
}
int ans = 0;
rep(i, h)rep(j, w)
{
if (roomh[i][j] || roomw[i][j]) ++ans;
}
cout << ans << endl;
return 0;
}実装は少し重めですが、比較的シンプルな問題なのではないでしょうか。
また、私のプログラムは多少の工夫はあるものの、ある程度愚直にやっています。そのため、C++以外の言語ですと、計算時間が厳しいかもしれません。
F Valid Payments
お金の話です。a1円玉, a2円玉, ... , an円玉の n 種類のコインがあります。ここで、a1 = 1で ai < ai+1 かつ ai+1はaiの倍数です。
ここで、お客さんが x 円の品物を買う際にレジにてy (>=x)円払いました。お釣りは y - x 円です。このとき、お客さんも店員さんもちょうど渡すのに最小のコインを受け渡したかつ、 支払いとお釣りに同じコインは存在しませんでした。
以上の条件の元、y として考えられる値は何通りあるでしょう？
という問題です。
これを一目見たとき、何を言っているのかよくわかりませんでした。そのため、日本円に置き換えてみます。
日本には1円玉、5円玉、10円玉、50円玉、100円玉があります（これ以降は省略）。これらの硬貨は ai < ai+1 かつ ai+1 は ai の倍数を満たしています。さて、ここで 97 円のポテチを買ったとしましょう。この際に色々なお金の払い方が考えられると思います。
100円払う(100円*1)→3円お釣り(1円*3)
102円払う(100円*1, 1円*2)→5円お釣り(5円*1)
107円払う(100円*1, 5円*1, 1円*2)→10円お釣り(10円*1)
147円払う(100円*1, 10円*4, 5円*1, 1円*2)→50円お釣り(50円*1)
97円払う(50円*1, 10円*4, 5円*1, 1円*2)→0円お釣り
この5通りですね。107円支払いなどはお釣りのコイン数を減らすために行う方もいると思います。
注意点としましては、
103円払う(100円*1, 1円*3)→6円お釣り(5円*1, 1円*1)
というのはダメです。渡した1円玉が戻ってきており、支払いとお釣りに同じ種類の硬貨は存在しないに反します。ただ、これは明らかにスマートではないですね。現実でも計算を間違えない限りはやらないと思います。
また、
100円払う(10円*10)
というのも禁止されています。これは最小のコインの受け渡しに反します。同じ理由で、5円のお釣りを1円玉5枚というのも起こりえません。この部分は現実とは少し違いますね。これは、お客さんが y 円を支払う際の硬貨の出し方は一意に定まると言い換えることもできます。
少々長くなりましたが、ここまでが問題設定です。ここから問題について考えていきましょう。
まず、簡単のために硬貨の種類を1円玉、10円玉、100円玉、1000円玉？札？とし、3137円のものを買ったとしましょう。
まず、お客さんが3200円払ったとします(1000円*1、100円*2)。お釣りは63円ですね（10円*6、1円*3）。
10進数と硬貨を対応させているので、筆算みたいに表記できます。この場合は問題なさそうですね。
次にダメな例を見ていきます。3300円払ったとします(1000円*1、100円*3)。お釣りは63円ですね（100円*1, 10円*6、1円*3）。
100の位に z と y でどちらも0以外の数字が出現しています。このため、同じ種類の硬貨の受け渡しが発生します。
また、現実ではやってしまうけれども、問題では禁止されている払い方で3200円を払ってみます（1000円*2,100円*12）。
各桁は 0~9 ですので、12が入るのはおかしいですね。繰り上がりが必要です。ただし、今は10000円札がないので最大桁に当たる1000円のみ10以上が許されます。
以上のことより、次の関係がわかります。
１、x, y, z の関係式は各桁の i 桁目（i の位）をxi, yi, zi とすると
yi = xi + zi + 前の桁からの繰り上がり - 次の桁への繰り上がり
２、yi か zi のどちらかは必ず 0 となる。（どっちも 0 でもよい。）
３、各桁には 0 から次の桁に繰り上がるまでの数しか入らない。
少し詳しく見ていきます。
１に関しては、繰り上がりを考える必要があります。足し算の繰り上がりですので、前の桁からのものは 0 or 1 です。また、次の桁への繰り上がる場合には次の桁に繰り上がりに必要な数を引いてあげます。３、でさらに述べますが、上の例にて 12 が繰り上がって 12 - 10 = 2 となったやつです。
２に関しては、少し言い換えをするのであれば、xi が既知なので、yiか zi のどちらかを 0 とすればもう片方は自動的に決定されるということです。実装の際にはそのようにして、値を求めて判定を行います。このとき、yi = zi = 0 も許されるのでその部分の数え上げに注意しましょう。
３に関しては、１の繰り上がりにもかかわってきます。今回の場合では各桁が 10 個入ると次の桁に上がるため、各桁には9 までしか入りません。日本の例でも考えると、
1円の桁：4
5円の桁：1
10円の桁：4
50円の桁：1
となります。この数を超えるとコインの重複が発生します。また、この数字は次桁を該当桁で割れば求まります（商 -1 が最大数）。
(ai+1) / ai
問題の考え方は以上となります。
あとは dp を使って数え上げを行うだけです。dp の設計は
dp[ i ][ j ] : i 桁目まで数えた、繰り上がりがある( j = 1)、ない（ j = 0）
ときの支払い方の数
としてあげます。
具体的には、まず上記の関係式にて y か z を 0 とします。今回は z = 0 としましょう。そうすると関係式は z が消えて
yi = xi + 前の桁からの繰り上がり - 次の桁への繰り上がり
ですね。ここから、前桁からの繰り上がりのあり or なし、と次桁への繰り上がりあり or なしの 4 つの遷移が発生します。その条件のもとで yi を計算して 0<= yi <= 各桁の上限 であれば、dpテーブルを更新します。
dp [i+1][次桁への繰り上がりあり、なし]
+= dp[i][前桁からの繰り上げりあり、なし]
先にも述べましたが、y = z =0 の場合の数え上げに注意しましょう。
長くなりましたが実装です。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll = long long;
int main()
{
int n;
ll x;
cin >> n >> x;
vector<ll> a(n);
rep(i,n) cin >> a[i];
vector<ll> d(n);
//x 円は各硬貨がいくつ必要か計算
for(int i=n-1; i>=0;--i)
{
d[i] = x / a[i];
x %= a[i];
}
vector<ll> ud(n);//繰り上がるためには前桁が何個必要か
rep(i,n-1) ud[i] = a[i+1]/a[i];
ud[n-1] = 1e18; //最大桁以上のところに大きい硬貨を用意しておく。
vector<vector<ll>> dp(n+1,vector<ll> (2));
dp[0][0] = 1;
rep(i,n)
{
//bj:before 下の桁からの繰り上がり
//aj:after 上の桁への繰り上がり
//y = x+z + bj -ud[i] *nj
rep(bj,2)rep(aj,2)
{
//z = 0
ll y = d[i] + bj -ud[i]*aj;
if(0 <= y && y < ud[i]) dp[i+1][aj] += dp[i][bj];
//y = 0
ll z = -d[i]-bj+ud[i]*aj;
//0 <= zとすると y = z = 0 を2回数え上げてしまう。
if(0 < z && z < ud[i]) dp[i+1][aj] += dp[i][bj];
}
}
cout << dp[n][0] << endl;
return 0;
}実装自体は軽めですね。コメントアウトを除けば相当短いと思います。
本問題はまず、問題文が何を言っているのかを理解することが特に重要であり大変であった思います。国語の力が問われますね。私自身、高校生のころ、国語の成績は褒められるものではなかったので、理解するのに時間がかかりました。
一方で、理解してしまえばかなり現実に即していることがわかります。数学では辺上を動く謎の点 p など、よくわからない出来事がたくさん起こっていますからね、、、
この解法が日常生活の役に立つかは疑問ですが、本問題は私たちの身近なことを題材にしており、取り組みやすかったのかな思います。
ただ、取り組みやすさと難易度はまた別ですね。とっても難しかったです。
この記事が気に入ったらサポートをしてみませんか？