0.はじめに
2週間前の開催分ですが、inoutファイルが公開されたので
再チャレンジ。
試験時は、Aを回避してBに挑戦したけど結局正解無しという惨憺たる結果でした。
今回、解説動画も見ながらA・Bの解答をしてみました。
1.A - Continuous 1
ぱっと見、細かい場合分けで行けるかなと思いましたが
場合分けパターンが多くなりそう＆Bがいけるかもと思いスルーしました。
後で解説を見て、目からうろこでした。
考え方(解説内容の整理)
条件を満たすパターンは
K個の1の連続が左から右に移動していくような感じになる。
例）N=5、K=3の時
①11100
②01110
③00111
文字列Sが、1)～3)をそれぞれ満たせるかを判断し、
満たせる場合が1個だけの時Yes、それ以外はNoを表示する。
実装
1)文字列Sのアドレスiを0～R(N-K)まで移動させていく。
変数ansに0をセット
1チェック用変数(連続1判定範囲内で1を取りうる桁の数を保持) C1と
0チェック用変数(連続1判定範囲外で0を取りうる桁の数を保持) C0を準備
1-1)i＝0の時
連続1判定範囲が右端の場合のC1、C0をカウント
文字列Sを変数jを0～N-1まで推移してチェックしていく。
・j<kの時
S[j]が1か?の時C1に1を加算
・j≧kの時
S[j]が0か?の時C0に1を加算
C1=Kかつ、C0=N-Kの時ansに1を加算
1-2)i!=0の時
連続1判定範囲が、右に1つずれるので、範囲から出るS[i-1]と
範囲に入るS[i+K-1]について、判定を行う
S[i-1]が、”1”の時→C1から1を減算
S[i-1]が、”?”の時→C1から1を減算、C0に1を加算
S[i-1]が、”0”の時→C0から1を減算
S[i+K-1]が、”1”の時→C1に1を加算
S[i+K-1]が、”?”の時→C1に1を加算、C0から1を減算
S[i+K-1]が、”0”の時→C0から1を減算
C1=Kかつ、C0=N-Kの時ansに1を加算
2)ans＝1の時”Yes”、それ以外の時”No”を表示
https://atcoder.jp/contests/arc150/submissions/35830614
2.B - Make Divisible
考え方１
1)以下の場合分け
(1)B%Aが0
答えは0
(2)AがBより大きい
答えはA-B
(3)上記以外
Xが0からA-(B%A)までの間の答えをすべて求め最小値を答えとする
答え、(A+X)-(B％(A+X))+X
と、安易に考え実装したところ、例題は通ったのでいけるかも！と提出
WA6、TLE16という結果に負け、試験日はここまでで断念
後日開示された答え見ると、TLEのところも、WAっぽい。
解説を見ながら再挑戦
考え方２(解説の内容を自分なりに飲み込むための整理)
(1)B%Aが0の時答えは0
(2)それ以外の時
以下の式を基本とし、A+xとzを遷移域内で変動させ、x+yの最小値を求める
B+y=(A+x)z
(2-1)遷移域の考え方
(2-1-1)回答の最大値
x+yの最小値を求める前提を一旦おいておいて、zを1としたとき
A>Bの場合
・x=0、y=A-Bとすれば、B+y=A+xとなり、A+xがB+yの倍数という条件を満たす
B>Aの場合
・y=0、x=B-Aとすれば、B+y=A+xとなり、A+xがB+yの倍数という条件を満たす
よって、答えはx=max(B-A,0)y=max(A-B,0)であるため、解=max(A,B)となる
(2-1-2)B+yの上限
B+yは、B+max(A,B)(最大でも)となるため、B+y≦2max(A,B)
(2-1-3)A+x および zの上限
B+y=(A+x)zかつ、B+y≦2max(A,B)の時
A+xとzのどちらか一方は√2max(A,B)以下となる。
(2-2)A+x=kとしkを可動させた場合の解
(2-2-1)kの範囲
・A≦k≦√2max(A,B)
(2-2-2)B+yの値
・kで割り切れるB以上の最小値
B%k=0の時
B+y＝B
それ以外の時
B+y＝k(B//k+1)
(2-2-3)x,yの値
B%k=0の時
x=(B//k)-A
y=0
B%k!=0の時
y=B*(B//k+1)-B
x=k-A
(2-3)z=kとしkを可動させた場合の解
(2-3-1)kの範囲
・1≦k≦√2max(A,B)
(2-3-2)B+yの値
B≦kAの時
・kA
B＞kAの時
・k*((B//k)+1)
(2-3-3)x,yの値
B≦kAの時
・x=0
・y=kA-B
B＞kAの時
・x=((B//k)+1)-A
・y=xk-B
(2-4)2-2・2-3で求めた答えの最小値を出力
実装時にちょいちょい修正したので実際の式はだいぶ変わってしまったが
なんとなく上のような考えでACいけました。