AtCoderBeginnerContest161復習＆まとめ（前半）

AtCoder ABC161

2020-04-04(土)に行われたAtCoderBeginnerContest161の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

A問題　ABC Swap

問題文
3つの箱$A$,$B$,$C$があります。それぞれの箱には、整数が1つ入っています。
現在、箱$A$,$B$,$C$に入っている整数はそれぞれ$X$,$Y$,$Z$です。
これらの箱に対して以下の操作を順に行った後の、それぞれの箱に入っている整数を求めてください。
　・箱$A$と箱$B$の中身を入れ替える
　・箱$A$と箱$C$の中身を入れ替える

もともと箱$A$の中身は箱$B$に入り，箱Cの中身は箱$A$に入り，箱$B$の中身は箱$C$に入ります．
したがって，箱$A$に$Z$，箱$B$に$X$，箱$C$に$Y$が入っていることになるため，その順に出力すれば大丈夫です．

abc161a.py

x, y, z = map(int, input().split())
print(z, x, y)

B問題　Popular Vote

問題文
$N$種類の商品に対して人気投票を行いました。商品$i$は$A_i$票を得ています。
この中から人気商品$M$個を選びます。ただし、得票数が総投票数の$\frac{1}{4M}$未満であるような商品は選べません。
人気商品$M$個を選べるなら"Yes"、選べないなら"No"を出力してください。

解説には，最初にsortする方法が記載されていましたが，２つ目の解法の方がシンプルかなと思いました．得票数が総投票数の$\frac{1}{4M}$以上であるような商品を数え，それが$M$個以上あるかどうかで判定すれば大丈夫です．WAになるとしたら「未満」を以下と勘違いしたり，条件式に「=」入れるかどうかを間違えたりかなと思います．sum(a_list)はリストの中の数値を全て合計してくれる関数です．

abc161b.py

n, m = map(int, input().split())
a_list = list(map(int, input().split()))
sum_a = sum(a_list)
count = 0
for a in a_list:
    if a >= sum_a / (4 * m):
        count += 1
if count >= m:
    print("Yes")
else:
    print("No")

C問題　Replacing Integer

問題文
青木君は任意の整数$x$に対し、以下の操作を行うことができます。
操作:$x$を$x$と$K$の差の絶対値で置き換える。
整数$N$の初期値が与えられます。この整数に上記の操作を$0$回以上好きな回数行った時にとりうる$N$の最小値を求めてください。

この問題を解くのには少し時間をとられました．とりあえずルールに従ってループ回せば最小の$N$求められるだろうと思ってプログラム書いたら，入力例3の1000000000000000000 1が2secで解けず少し手が止まりました．よくよく考えたら入力$N$が大きく，$K$が小さい場合，引き算何回もするけど，それってとりあえず$N$ / $K$回行うことは確定してるから一気にその分引き算できると思って，以下のコードが完成しました．（引き算の結果が負になる方を詳しくコード書く時間なかったから，とりあえず(n - k)が負になる場合は，差の絶対値が元の数より大きければそれ以上やる必要ないし，小さければとりあえず差の絶対値をnに更新するようにしたらうまくいった）

abc161c.py

n, k = map(int, input().split())
while(True):
    if n - k > 0:
        if n // k > 0:
            n = n - k * (n // k)
        else:
            if n - k < n:
                n = n - k
            else:
                break
    else:
        if abs(n - k) < n:
            n = abs(n - k)
        else:
            break
print(n)

本番のコンテストならば，上記のコード書ければいいけど，せっかくのまとめ記事は解説を参考にもう少しシンプルに書き直しました．
解説は以下の通りです．

解説
$x$が$K$以上のとき、操作を行うことで$x−K$となります。すなわち、$N$から$N/K$回操作を行うことで、整数は$N$を$K$で割った余りとなります。$N$を$K$で割った余りを$t$とします。$t$に操作を行うと、$K−t$となります。$K−t$に操作を行うと、$t$に戻るだけです。すなわち$K$以下の値として取りうるものは$t$と$K−t$のいずれかのみとなります。よって答えは$t$と$K−t$のうち小さい方、すなわち$N$を$K$で割った余りと、$K−$($N$を$K$で割った余り)のうち小さい方です。

途中に書いてあることは長いですが，結論はシンプルで，あまりを使って答えを出せってことです．これを参考にコードを書くと以下のようになります．

abc161c.py

n, k = map(int, input().split())
t = n % k
print(min(t, k - t))

3行で書けました(笑)
自分がもともと提出したものと比べると一目瞭然ですね．
自分がもともと書いていたn = n - k * (n // k)の計算式がn = n % kであると気づけないあたり，反省してます．
解説が文字ばかりでわかりにくい場合は具体的な数値例考えると簡単に理解できると思います．いろいろなパターン全部挙げるのは記事が読みにくくなるので，典型的な例を一つあげるとn = 1003, k = 5のときを考えます．
この場合，1003から5をまずは200回引くことになりその結果は3となります．
この3は1003 / 5のあまりでもあるため，プログラムでは1003 % 5によって3を得ることができます．つまりt = 3となります．
最後にtとk-tのどちらが小さいかですが，k - t = abs(t - k) = abs(3-5) = 2となります．
よって3と2では2の方が小さいので答えは2となります．

前半はここまでとなります．
後半はDEF問題の解説となります．
とりあえず前半の最後まで読んでいただきありがとうございました．
後半に続く．