AtCoderBeginnerContest170復習＆まとめ（前半）

AtCoder ABC170

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

A問題　Five Variables

問題文
$5$つの変数$x_1,x_2,x_3,x_4,x_5$があります。
最初、変数$x_i$には整数$i$が代入されていました。
すぬけくんは、これらの変数の中から$1$つを選んで、その変数に$0$を代入する操作を行いました。
すぬけくんがこの操作を行ったあとの$5$つの変数の値が与えられます。
すぬけくんが$0$を代入した変数がどれであったかを答えてください。

提出は，for文回して，要素が0の部分を出力するようにしました．
たいていのプログラミング言語は，配列の先頭が$0$からスタートするので，そこに気を付ければ，WAの心配もないかなと思います．

abc170a.py

x = list(map(int, input().split()))
for i in range(5):
    if x[i] == 0:
        print(i + 1)

終わった後解説見て，答えが $15 − x_1 − x_2 − x_3 − x_4 − x_5$ になるのは，なるほどなと思いました．

B問題　Crane and Turtle

問題文
庭に何匹かの動物がいます。これらはそれぞれ、$2$本の足を持つ鶴か$4$本の足を持つ亀のいずれかです。
高橋くんは、「庭の動物の総数は$X$匹で、それらの足の総数は$Y$本である」と発言しています。この発言が正しいような鶴と亀の数の組合せが存在するか判定してください。

考えた順にルールをif文で追加していきました．

1. 全部カメにした場合の足の数より，足の総数$Y$が大きい場合は，"No"
2. 全部鶴にした場合の足の数より，足の総数$Y$が小さい場合は，"No"
3. 足の総数が奇数になることはないので，足の総数$Y$が奇数の場合は，"No"

abc170b.py

x, y = map(int, input().split())
if y < 2 * x or x * 4 < y:
    print("No")
else:
    if y % 2 == 1:
        print("No")
    else:
        print("Yes")

C問題　Forbidden List

問題文
整数$X$と、長さ$N$の整数列$p_1,…,p_N$が与えられます。
整数列$p_1,…,p_N$に含まれない整数 (正とは限らない) のうち$X$に最も近いもの、つまり$X$との差の絶対値が最小のものを求めてください。そのような整数が複数存在する場合は、そのうち最も小さいものを答えてください。

入力された$X$から順に，整数列に含まれない数字を探索しました．$N$が大きいとif x in list:に時間がかなりかかるので，listをdictに変えたりしますが，今回は$N$が小さいのでそのままにしました．

例えば，入力が$6$であれば，6, 5, 7, 4, 8, ...みたいな順番で探索しています．（プログラムは入力である $x = 6±0$ を二度調べているのですが，実行時間に差はそんなに出ないと思い，実装しやすい形で実装しました．）

abc170c.py

x, n = map(int, input().split())
p_list = list(map(int, input().split()))
for i in range(0, n // 2 + 2):
    if x - i not in p_list:
        print(x - i)
        break
    if x + i not in p_list:
        print(x + i)
        break

D問題　Not Divisible

問題文
長さ$N$の数列$A$が与えられます。
次の性質を満たす整数$i(1 \leq i \leq N)$の数を答えてください。
　・$i \neq j$である任意の整数$j(1 \leq j \leq N)$について$A_i$は$A_j$で割り切れない

コンテスト中はいろいろ工夫を考えましたが，解けませんでした．
"TLE"のコードは以下のものを提出しました．

abc170dTLE.py

import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)
i = 0
for key, count in sorted_dict:
    if flag_list[i] == 0:
        i += 1
        continue
    if count > 1:
        flag_list[i] = 0
    i += 1
    j = i
    for key1, count1 in sorted_dict[i:]:
        if flag_list[j] == 0:
            j += 1
            continue
        if key1 % key == 0:
            flag_list[j] = 0
        j += 1
print(sum(flag_list))

ソートして，小さいものでそれよりも大きいものを割れるかどうか確かめていけば，後半の計算量が少なくできると思ったのですが，ダメでしたね．

実際には，setに入れて管理し，ある$a_i$の$2$倍，$3$倍，$4$倍，...，$k$倍 ($k$ は $a_i × k \leq a_{max}$ を満たす最大の整数 $k$)をsetから除いていけば解けたようです．
思いつかなかったな．

abc170d.py

import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
a_set = set(a_list)
m = max(a_list)
for key, count in sorted_dict:
    if  key in a_set:
        j = key * 2
        while j <= m:
            a_set.discard(j)
            j += key
    if count > 1:
        a_set.discard(key)
print(len(a_set))

前半はここまでとなります．
個人的に，ここ最近rate落としまくりですが，過去問を解いたりする時間がデータ解析コンペや，論文書いたりで確保できてないので，当たり前ですね．
コンペの方の勉強も溜まってるので，少しずつ消化していきたいと思います（次回のコンペまでに最低限の方法論は理解し実装できるようにしたい）．
とりあえず，最低限ABCは毎回参加するようにしている習慣をしばらくは持続することを目標にやっていけたらと思います．
前半の最後まで読んでいただきありがとうございました．

後半はEF問題の解説となりますが，時間的に記事作成できないと思います（汗）．