[Python]AtCoder Beginner Contest 161を解いてみた(A~C)

AtCoder Beginner Contest 161にPythonで参加しました。

A – ABC Swap
1. 問題
2. 自分の回答
B – Golden Coins
1. 問題
2. 自分の回答
C – Replacing Integer

A – ABC Swap

問題

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

箱Aと箱Bの中身を入れ替える
箱Aと箱Cの中身を入れ替える

自分の回答

X, Y, Z = input().split()
print(Z + " " + X + " " + Y)

順番を変えて、出力をしてあげれば良いですね。

B – Golden Coins

問題

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

自分の回答

N, M = map(int, input().split())
votes = sorted(list(map(int,input().split())), reverse=True)

for i in range(M):
  if votes[i] < sum(votes) / (4 * M):
    print("No")
    exit()

print("Yes")

入力の時点で、sorted関数を使って、値が降順(先頭に大きい数字がくる)に並べています。あとは、先頭から順にM個取り出して、取り出した値が総投票数の1/4M未満になっていないかを確認し、値が未満になった時点で”No”を出力して、プログラムを終了します。問題がなければ、”Yes”が出力されます。

C – Replacing Integer

問題

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

自分の回答

# 誤回答(Python)
N, K = map(int, input().split())
a = int(N / K)

b = abs(N - K * a)
c = abs(b - K)
print(min(b,c))

// 正解(C++)
#include <bits/stdc++.h>
using namespace std;
int main () {
  lomg int N, K;
  cin >> N >> K;
  
  long int a = N / K:

  long int b = abs(N - K * a):
  long int c = abs(b - K):

  cout << min(b, c) << endl;
}

解き方はすぐわかって上記のコードを書いたのですが、提出すると、一つの場合だけ不正解になってしまいます。結局解決できず、最終的にはC++で書き直して提出したところ正解となりました。やっていることは同じなのに何が違ったのでしょうか。

Pythonで書いたコードの二行目のa = int(N / K)としているところがよくなかったみたいです。不正解となるテストケースはN=548698204992839484、K=5の時です。この時、二行目のaの値がPythonとC++で違っていました。

Pythonの場合
a = int(N / K)　    => 109739640998567904
C++の場合
long int a = N / K　=> 109739640998567896

なんと全然違う値になっています。これでは、答えが違ってしまうのも当然です。一体、何故、このようなことになってしまったのでしょうか。
ここからは、自分でもよく理解していないので、推測も混じり、違ったことを言っているかもしれませんので、お気をつけください。

おそらく、float型からint型に変換するときに間違いとなる原因が発生しているのでは無いかと思いました。aを代入するときに、Pythonの場合、割り算をすると勝手にfloat型になるので、その後、int型に直しています。試しに、N/Kの値を出力してみると、1.097396409985679e+17となり、この時点で、C++が出した109739640998567896にはどうなってもならない気がします。1.097396409985679e+17をint型に直すと、109739640998567904となります。末尾の4がよく意味が分かりませんが、なんとなく、間違った値になってしまった理由が少し分かりました。Pythonでは、16桁より大きい値は勝手に丸められてしまうので、それをint型に直した時に、誤差が生じてしまったのでは無いでしょうか?C++のlong int型は最大値は9223372036854775807まで取れるので、問題なかったみたいです。
まだ、完璧に理解したわけではありませんが、なんとなくは理解できました。

Pythonの場合
    N / K  = 1.097396409985679e+17
int(N / K) = 109739640998567904

自分の回答(正)

N, K = map(int, input().split())

a = N % K
print(min(abs(a - K), a))

長くなってしまいましたが、他の方のを参考にPythonでも正解のコードを書きました。
結局、最小値をとる可能性のある値は、NをKで割った値の余りとそこからKを引いた値の二つになります。最初に書いたコードとやっていることは同じですが、%を使うことで、より端的に求められるようになっています。また、値が大きくなって、誤差が生まれることもありません。