今日の精進 ABC170D

一昨日のABCで3完でレートを冷やしてしまったのでその反省です。

D - Not Divisible

配点 : 400点

問題文

長さ Nの数式 Aが与えられます。 次の性質を満たす整数 i(1\leq i\leq N)の数を答えてください。

  • i \neq jである任意の整数  j(1 \leq j \leq N)について  A_i A_jで割り切れない

制約

  • 入力は全て整数
  • i \neq j
  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq A_i \leq10^{6}

コンテスト中の解法

  •  A_iの数についてそれぞれカウントし、重複がある場合既出扱いにする
  •  A_iを昇順にソート
  •  A_iに対して約数を列挙し、その約数が既出かどうかを判定する
    • 既出である場合、その数は割り切れるためカウントしない
    • 既出でない場合、カウントを行なう

約数列挙に O(\sqrt{A_i})かかるので全体で O(NA_i) \approx 2 \times 10^{8}C++なら行けるかなと思った。 結果、WA取れず。

https://atcoder.jp/contests/abc170/submissions/14403117

想定解

小さい方からエラストテネスの篩と同じように処理をして埋めていくことで解ける。 埋める数は徐々に減り、調和級数で表せるので全体で[tex: O(A{max}logA{max}+NlogN)]になる。 これならpythonでも問題なさそう。

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
a = sorted(list(set(a)))
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)

Submission #14403324 - AtCoder Beginner Contest 170

Kaggle Google Quest Q&A Labeling参加録

www.kaggle.com

タスク説明

f:id:bluexleoxgreen:20200211160142p:plain

  • QAサイトの質問文と解答文(+メタデータ)から質問・解答の点数を予測する
  • 採点項目は全部で30項目ある
  • 質問の形式に関するもの、質問になっていない、解答の妥当性など
  • 元のQAデータはおそらくこれ
  • 評価指標はスピアマンの順位相関係数

解法とコンペ中の動き

  • 結構早い段階でbert-baseの強いnotebookが出たので、これをベースに進めた Bert-base TF2.0 (now Huggingface transformer) | Kaggle
  • 一部の採点項目の点数が偏りすぎてルールベースで点数を決定するとスコアが伸びるという話がどこかにあった
  • それに関するdiscussionnotebookを投稿した
  • カテゴリ、ホストによって点数の分布が違うので、それらに関するfeatureを入れたモデルを作った

  • 最終的に提出したのは以下のモデルのアンサンブル

    • bert-base (TF hub) 5epoch学習、2、3、4epoch目のモデル
    • bert-large (TF hub) 5epoch学習、best epochのモデル
    • feature+distilbertのembeddingを使ったモデル
      • カテゴリ、ホストのfeatureはそれぞれの点数に対してtarget-encoding
  • 質問文に重複があるのでCVはGroupMultilabelStratifiedKFoldを使用

    • 同じ質問文のものを集約し、点数はそれらの平均値で置き換える
    • Neuron Engineerさんのありがたいml-stratifiersのMultilabelStratifiedKfoldに突っ込む
    • 集約したものを元に戻す
  • 重みの調整

    • 各モデル・foldの重みはspearmanrを最小化するようにした
    • この時、順位に関する情報が失われないようにscipyのrankdataで順位に置き換えて正規化した
  • 後処理

    • 点数に偏り(同順位)が多数あるので、spearmanrが最も高くなるように丸めた
  • 最終順位

    • Public Leaderboard 91st (Bronze)
    • Private Leaderboard 65th (Silver)

今回のコンペで覚えたtips

  • コンペ序盤は提出エラーが信じられないほど発生したので試行錯誤した f:id:bluexleoxgreen:20200211164423j:plain
  • 今回の評価指標の制約
    • 0<x<1の値を予測しないといけない
    • 列が全て同じ数値だとnanになってしまうのでエラーが出る

publicだけ予測する

  • これはnotebook onlyのあらゆるコンペで使える
  • privateの予測でエラーが出ているようだったので、しばらくはpublicのtestデータだけ予測した
  • 公開されているtest.csvのqa_idのデータだけ予測して残りを乱数で埋める
  • 遅そうだが以下でいける
sample = pd.read_csv("../input/google-quest-challenge/sample_submission.csv")
submission = pd.read_csv("../input/public_inf/submission.csv")
sub = pd.merge(sample["qa_id"], submission, on="qa_id", how='outer')
sub = sub.fillna(0)

for i in range(len(sub)):
    if int(sub.iloc[i].qa_id) not in set(submission["qa_id"].values):
        sub.iloc[i, 1:] = sub.iloc[i, 1:].apply(lambda x: random.random())
sub.to_csv("submission.csv", index=False)

推論のpythonファイルを切り出す

  • TF2.0のモデルをGPUに載せるとGPUメモリから消せなくなるバグ(?)があるようなので切り出した
  • multiprocessing使ったりimport cudaする方法も試したがうまく行かなかったので最終的にはこれで解決した
  • notebook内で! python inf.pyみたいにすれば良い

提出のデバッグ

  • 普通は提出した時のエラーがどこで発生しているのかわからない
  • 各セルの最後に! touch Aのようにファイルを生成しておき、提出ファイルを作る時に適当に公開notebookから持ってきたpublic testの予測値をsubmission.csvに突っ込むとどのセルでエラーが出て止まっているかわかる

datasetの20GB上限突破

  • datasetにアップロードできるモデルの上限は1ユーザにつき20GB
  • Bert baseだと1モデルで1.3GB、largeだと4GBなのでソロで5foldのモデルをアップロードするのは厳しい
  • notebookのoutputを利用すれば上限を突破できる
  • 1度datasetにアップロード→notebook内でcopyしてoutputに追加→datasetを削除
  • ただしnotebookの容量上限5GBがあるので、大きいデータは分割して出力する必要がある

AtCoder Beginner Contest 125

A - Biscuit Generator

A秒間隔でB個のビスケットを生産する装置がある時に、T+0.5秒ごに生産されるビスケットの総数を求める問題。

  • T+0.5の制約は、T秒に生産されたものも数えるという意味
  • 生産されるのは、A秒、2A秒、3A秒(スタート時点では生産されない)

解法

  • 秒数がT+0.5を越えるまでループして加算すれば良い
# A
a, b, t = map(int, input().split())

count = a
ans = 0
while True:
    if count > t + 0.5:
        break
    count += a
    ans += b
print(ans)

B - Resale

N個の宝石があり、i番目価値がViで購入にかかるコストがCiである。この時、合計価値-合計コストの最大値を求める問題。

解法

  • 価値-コストが最大になるものを全て選び、それらのプラス分を加算して行く問題
# B
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = 0
for i in range(n):
    gain = v[i] - c[i]
    if gain > 0:
        ans += gain
print(ans)

C - GCD on Blackboard

N個の整数があり、一つを好きな整数に書き換えることができる時、それらの整数の最大公約数の最大値を求める問題。

  • 最大公約数を求める問題なので、書き換える部分は「消す」という処理に置き換えることができる。
  • i番目以外のN-1個のgcdを計算すると、O(N2)となり、間に合わない。

解法

  • 最大公約数を左右からそれぞれ計算していく、それまでの最大公約数以上になることはないので、1つ前までの最大公約数と次の数の最大公約数のみを計算すれば良い。
# C
import functools
# 3.4以前は math の gcd が対応していないので fractions or 自作のものを使う
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)

# 入力
n = int(input())
a = list(map(int, input().split()))

# 左から一つずつ最大公約数をとるものと、右から一つずる最大公約数をとるものを作る
# O(N) + O(N)
gcd_left = [a[0]]
for i in range(1,n):
    if gcd_left[i-1] != 1:
        res = gcd(gcd_left[i-1], a[i])
    else:
        res = 1
    gcd_left.append(res)

gcd_right = [a[-1]]
for i in range(1,n):
    if gcd_right[i-1] != 1:
        res = gcd(gcd_right[i-1], a[-(i+1)])
    else:
        res = 1
    gcd_right.append(res)
gcd_right = gcd_right[::-1]

# 最大のものを探す
# O(N)
ans = 0
for i in range(n):
    if i == 0:
        res = gcd_right[1]
    elif i == n-1:
        res = gcd_left[-2]
    else:
        res = gcd(gcd_right[i+1], gcd_left[i-1])
    ans = max(res, ans)
print(ans)

D - Flipping Signs

N個の整数があり、連続する2つの整数の符号を反転させる処理を何度でも行うことができる。この時、処理後の整数の和の最大値を求める問題。

  • 連続する2つの整数の符号を反転させることができるので、実質離れたところにある2つの整数の符号をいくらでも反転できる。
  • ここで重要なのは、反転させることができるのは偶数個である点である。

解法

  • 入力された整数のうち、負のもの(0を含む)をできるだけプラスにすれば良い。
  • 負のものが奇数個の場合、1つはマイナスが残ってしまう。
  • 負のものが奇数個の場合は、正・負の中で絶対値が最も小さいものをマイナスにすることで合計をできるだけ大きくする。
# D
n = int(input())
a = list(map(int, input().split()))

l_minus = [i for i in a if i <= 0]
l_plus = [i for i in a if i > 0]

ans = 0
if len(l_minus) % 2 == 0:
    l_minus_edit = [-i for i in l_minus]
else:
    l_minus_edit = [-i for i in l_minus]
    temp = l_plus[:]
    temp.extend(l_minus_edit)
    l_minus_edit.append(-min(temp) * 2)

ans = sum(l_plus) + sum(l_minus_edit)
print(ans)

Tenka1 Programmer Beginner Contest 2019

Tenka1 Programmer Beginner Contest 2019 爆死しました。

A - On the Way

  • aからbに向かうときにcを通過するか否か。
# A
a, b, c = map(int, input().split())
if a <= c <= b or a >= c >= b:
    print("Yes")
else:
    print("No")

B - *e**** ********e* *e****e* ****e**

  • n文字の文字列sのk文字目以外の文字を*にする。
# B
n = int(input())
s = str(input())
k = int(input())

c = s[k-1]
st = ""
for char in list(s):
    if char != c:
        st = st + "*"
    else:
        st = st + char
print(st)

C - Stones

  • ある地点から左側を全て白(".")、右側を全て黒("#")にしたとき、最も変化させるコストが少なくなる物を探す。
  • ある地点より左にある黒の数と白の数の和が最小になるように全探索する。
  • 左にある黒の数と右にある白の数を更新して保持しておくとO(N)になる。
# C after
n = int(input())
s = str(input())

count_dot = 0
for i in range(n):
    if s[i] == ".":
        count_dot += 1
count_sharp = 0

ans = n
for i in range(n):
    ans = min(ans, count_dot+count_sharp)
    if s[i] == "#":
        count_sharp += 1
    else:
        count_dot -= 1
ans = min(ans, count_dot+count_sharp)
print(ans)

D以降は難しい...

ビギナー用のコンテストに参加したつもりが、ノーマルの方に出場し、Cで爆死したので気をつけようと思った。

AtCoder Beginner Contest 123

今週から、コンテストで解いた問題と解説を聞いて理解できた問題を記録していきたいと思います。

今週のABC123、ABC問の三完でした。

AtCoder Beginner Contest 123 - AtCoder

A - Five Antennas

  • 入力は5つのアンテナの座標と、通信できる距離kだった。
  • 各アンテナが相互に直接通信できるか否かを判定する。

解法

2重for文で全てのアンテナの組み合わせに対して、距離がkより大きかったら答えをFalseにするようにした。

iとjが同じ時は比較しなくてよいが、答えに関係なかったのでそのままにした。

ソースコード(python)

# A 
a = []
for i in range(5):
    a.append(int(input()))
k = int(input())
ans = True
for i in range(5):
    for j in range(5):
        if abs(a[i] - a[j]) > k:
            ans = False
if ans:
    print('Yay!')
else:
    print(':(')

B - Five Dishes

  • 入力はA問とほぼ同じで、5つの整数入力だった。
  • 各入力は料理の調理時間で、時刻10nの時にのみ注文ができるという制約があった。
  • 最後の料理が届く最も早い時刻を出力する。

解法

この問題で重要なのは、調理時間ではなく、調理時間の1の位のみであることがわかる。 調理時間がXX1の料理は、料理が届いてから次の注文をするまでに9分の時間が必要である。 よって、XX1, XX2,..,XX9,XX0の順でソートして先頭の時間とその他の時間の1の位を切り上げた和を出力すればよい。

別解

よくよく考えてみると、入力が5しかないので、ソートしなくても入力値の一つをそのまま、他を切り上げ等で全探索すれば簡単に書ける。

ソースコード(python)

# B
import math
a = [[] for i in range(5)]
min_inp = 0
for i in range(5):
    inp = int(input())
    inp_ceil = math.ceil(inp/10)*10
    first = inp - int(inp/10) * 10
    if first == 0:
        first = 10
    a[i].append(inp)
    a[i].append(inp_ceil)
    a[i].append(first)
a = sorted(a, key=lambda x: x[2])
ans = a[0][0]

for i in range(4):
    ans += a[i+1][1]

print(ans)

C - Five Transportations

  • 入力は人数nと5つの整数値。
  • 5つの整数値は目的地に着く為に利用する乗り物の定員数。
  • 全ての乗り物が1分で目的地に到着する場合、全ての人が出発地から目的地に着くまでにかかる時間を出力する。

解法

この問題では、人数がどれだけ多くても、5つの交通機関のなかで定員が最も少ないものがボトルネックになり、それ以降の移動人数はその交通機関の定員となる。

簡単に書けたが、切り上げを間違えて1WA出してしまった。

ソースコード(python)

# C
import math
n = int(input())
a = []
for i in range(5):
    a.append(int(input()))
ans = math.ceil((n/min(a) + 5) - 1)
print(ans)

D - Cake 123

  • 1、2、3のキャンドルが付いたケーキにそれぞれ、美味しさが割り当てられている。
  • 美味しさの合計が大きくなるような123のケーキの組み合わせを見つけ、美味しさの和を1~k番目まで出力する。

    考えたこと

    3種類のケーキの中でa,b,cの組み合わせ数が3000を超えるようにそれぞれのケーキを上からとっていけば良いと思った。

解法

a,b,cの全探索で、cのループでa,b,cの個数が3000を超えたらループを抜けるようにすれば、109程の計算をせずに解くことができる。

他にも色々な解法がある。

ソースコード(python)

# D
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ans = []
for index_i, i in enumerate(a):
    for index_j, j in enumerate(b):
        for index_l, l in enumerate(c):
            if ((index_i+1)*(index_j+1)*(index_l+1) <= k):
                ans.append(i+j+l)
            else:
                break
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

レート変化

f:id:bluexleoxgreen:20190406235952p:plain
レート

反省

今回はAとBの入力がめんどくさかったり、難しく考えてしまったりで時間をとられてしまった。

Cはボトルネックに気づいたことで、すぐに解くことができた。

Dはとてもシンプルな解法だったので、残念だった。

次は4月13日にABC122があるので頑張りたい。