ABC182を解いたまとめ

初投稿です．
AtCoderを解いているので解いた解法を忘れないようにメモ代わりとして記載していきます．

A問題

問題はこちら

問題文に書いてあるように，フォロワー数をA，フォローできる最大数をMAXとすると

MAX = 2 * A + 100

となるため，このMAXから入力値Bを引けばOKです．

B問題

問題はこちら

問題文を理解するのにだいぶ時間がかかってしまいましたが，表でまとめると

このようになるかと思います．いわゆる一番右列がその値のGCD度ということになります．

このときの一番右列Sの中の最大値をとるものの添え字番号を出力せよ，というのが問題でした．

なので，上記の表のような処理を行い，Sの集合を求め，その集合の最大値の添え字を出力すればOKです．

C問題

問題はこちら

ある数Nを受け取り，桁数をkとしたときNの桁を0～k個未満消して残った数字をそのまま連結し，3の倍数かどうかを判定するという問題．消す桁数の最小値を求める必要があります．

まずは3の倍数の性質を考えます．3の倍数であるかどうかの判定を行うためには各位の和が3の倍数かどうかを調べれば良いですね．

せっかくなのでこちらも証明してみます．

例えば3桁の整数Nの百の位をa，十の位をb，一の位をc，(0≦a, b, c ≦9) とすると

N=abc

とあらわすことができます．つまり，

N = a * 100 + b * 10 + c * 1

となるので，これをうまく分解すると

N = a * (99 + 1) + b * (9 + 1) + c * 1

= 99a + a + 9b + b + c

= 99a + 9b + (a + b + c)

となります．

Nが3の倍数になるためには，(a+b+c)が3の倍数となればよいので，各位の和が3の倍数かどうかで判断できることが分かりました．

ではC問題に戻ります．今回10^18の数が来る可能性があるのと，どこかの桁を消すという作業が入るので，String型で受け取っておきます．

まず初めにチェックすべきは消す必要がない，入力値がそもそも3の倍数の時です．こちらは受け取った時に各桁であるString型の1文字(つまりchar型)をint型に変え，和をとり，その和が3の倍数かどうかを判定します．3の倍数であれば0を出力して終わりでいいかなと思います．

1つ以上の桁を消す時を考えていきます．今回は累積和という手法を使って解きました．累積和とは，そこまでの和を配列でとっておくという手法です．

具体的には，ある数列a[0], a[1], ... ,a[n - 1]があった時，累積和を管理する配列をs[0], ..., s[n]とすると

s[0] = 0; // 0のときは0にしておく.
for (int i = 0; i < n; ++i) {
    s[i + 1] = a[i] + s[i]; // a[i]とs[i]をs[i+1]に足し合わせる
}

​とすればその添え字までのa[i]の和をあらかじめ求めておくことができます．これを求めておくことによって，数列a[]の部分和を簡単に求めることができます．

例えば，a[3] ～ a[6]までの和を求めたい，という場合

こうすれば求めることができました．

累積和とは，いわゆるその値までの和＝シグマということですね．

ここまでわかれば，区間を1～kまで回し，その時の累積和を総当たりして合計から引いた値が3の倍数かどうかを判定させればOKです．

ただ，この解法だとkが大きくなった場合には計算量が大きくなってしまうため改良が必要かもしれません．(もっといい解法があるのかも)

(2020/11/10：追記)

別解です．その桁を使うか使わないかの2択で判断することから，各桁に対して，使うなら1を，使わないなら0を割り当てるというbit全探索という手法を用いる方法です．

例えば3桁N=abcとして考えてみると，

この8通りで表現することができます．

この性質を利用すれば，もれなくすべてをチェックすることができます．

D問題

問題はこちら

こちらは解けませんでした．

同様に累積和で最大個所を求めればいいかと思ったのですが，各動作中内でも最大値を確認しないといけない，ということでしたので2重for文を使わないと解けないと思い，TLEしてしまいました．

この問題で単純な累積和を用いると，結局のところ各動作後の最終的な位置が求まるだけで，その操作中の最大の位置をとることはできません．

(2020/11/10：追記)

こちら累積和でACできました．累積和の理解不足でした．

入力を受け取るタイミングで累積和を作るところまではOKでしたが，その後の処理を少し工夫する必要があります．

累積和とは

という一般項で表されます．

つまり，式変形をすれば

と書き換えることができます．つまり，s[i+1]とs[i]の差はa[i]ということになるんですね．これを利用すれば，累積和だけで次の要素が何かを判断することができます．

では実際に解いてみます．

今の座標をpos，その動作の中での最大値をmx，答えとして出力する変数をansとしておきます．また，i番目までの入力の和(累積和)をs[i]とします．

結局今回の問題で詰まってしまったのはその動作内での最大値と動作終了後の変化量のどちらが大きいかを判別に入れていないということが原因でした．

最初mxを0として，mxにmx自身とs[i+1]を比較して大きいほうを格納します．すると，各納前mxがその動作の最大値，s[i+1]が累積和(動作終了後の変化量)となります．s[i+1]を比較対象とすることで，帰納的にa[i]がいくつなのかを知ることができます(上記の考察より)．格納後のmxは動作完了時の累積和or最大値が格納されていることになります．このように処理を書けば上記の問題は解決できます．

そして，答えであるansと(mx+pos)を比較すれば答えとなる最大値を更新することができます．

ここまでをfor文等で回せば，O(n)で解決することができます．

感想

なかなか茶色になれません．

今回茶色パフォ出ていたのですが今までの成績が悪かったせいでちょっとしか上がりませんでした．

C問題まで素早く，D問題をちゃんとACできるようにもっと鍛錬が必要だと痛感しました．

来週も頑張ります．