Educational Codeforces Round 17

codeforces

参加しました
まともに解けたのBだけでした

A. k-th divisor

問題概要

正の整数n, kが与えられるので、nのk番目の小さい約数を求めよ
ただしそのような約数が存在しない場合、-1を出力せよ

制約条件

  • 1 <= n <= 10^15
  • 1 <= k <= 10^9

感想

nの上限が10^15と大きいので愚直に小さい方から試す方法でも
O(sqrt(n))かかってしまい、最大で10^7.5ぐらいのループになる
ちょっとPythonではきついとか、他の上手いやり方あるのかなあとか
考えてたけどなかなか分からなくて飛ばしてBに行った

それでBを解いてから戻ってきて、結局分からなかったんでググってしまった
結論としてはnを因数分解してから約数のリスト作るみたいな方法で
やったけど、結局nが素数のときはO(sqrt(n))かかってしまう
それはどうにもならなさそうだったのでPypy3で出したら通った
想定解は普通に小さい方からループ回していくってやり方だった
そっちは使い慣れないC++で書いてみたらかなり余裕だった
C++だと10^8ぐらいまでは2sあれば余裕なんだっけ

こういうのはさっと解けるようにそろそろ素数系のライブラリ作ったほうがいいかなとか思った

実際に書いたコード

import sys
import math

def factorization(n):
    res = []
    limit = math.ceil(math.sqrt(n))
    p = 2
    cnt = 0

    while n % p == 0:
        cnt += 1
        n //= p

    if cnt > 0:
        res.append((p, cnt))

    cnt = 0
    for p in range(3, limit + 1, 2):
        if n % p == 0:
            while n % p == 0:
                cnt += 1
                n //= p

            res.append((p, cnt))
        cnt = 0

    if n > 1:
        res.append((n, 1))

    return res

def divisor(n):
    res = set()

    factor = factorization(n)

    for p, c in factor:
        if res == set():
            for i in range(c + 1):
                res.add(p ** i)
        else:
            t = set()
            for i in range(1, c + 1):
                for m in res:
                    t.add(m * p**i)
            res = res | t

    res = list(sorted(res))
    return res

n, k = map(int, input().split())

# print(factorization(n), file=sys.stderr)
# print(divisor(n), file=sys.stderr)

n_div = divisor(n)

if n == 1:
    if k == 1:
        ans = 1
    else:
        ans = -1
elif k > len(n_div):
    ans = -1
else:
    ans = n_div[k - 1]

print(ans)

B. USB vs. PS/2

問題概要

大学で新調したコンピュータにマウスを買いそろえたい
しかし、うちa台はUSBのみ、b台はPS/2のみ、c台はどちらでも可能である
ここにm個のマウスのリストがあり、
マウスiの価格がval_iで、USBかPS/2かが書かれている
我々はなるべく多くのマウスを、できる限り安く揃えたいと思っている
そのときに買えるマウスの最大個数と、そのコストを出力せよ

制約条件

  • 0 <= a, b, c <= 10^5
  • 0 <= m <= 3 * 10^5
  • 1 <= val_i <= 10^9
  • 各マウスのタイプはUSBかPS/2のいずれか

感想

まずはUSBマウスのリストと、PS/2マウスのリストを作って、それぞれ昇順にソートする
できるだけ多くのマウスを買わなければいけないので
USBマウスは優先的にa台のコンピュータに、
PS/2マウスは優先的にb台のコンピュータに安い順から割り振る
そしてもしマウスが余ったら、c台のコンピュータにUSB、PS/2の最安から順に割り振っていく

考え方としてはこんな感じで、後はコードにする
USBのリストとPS/2のリストの末尾に∞の番兵をつけておくと
楽になりそうだと思ったのでつけた
なんかマージソートのマージでもこういうやり方でやってたなーと思って
そのイメージでやった
計算量はソートに一番時間がかかるのでO(mlog(m))かな
余ったc台にマウス割り振りのところは、くっつけて組み込みのソートで
ソートして小っちゃい順に取るってやり方でもよかったかも
計算量ちょっと増えるけどそっちのほうがシンプルな気がする

実際に書いたコード

import sys

a, b, c = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())

num_item = 0
cost = 0

usb_l = []
ps2_l = []

for i in range(m):
    val, type_p = sys.stdin.readline().split()
    val = int(val)

    if type_p[0] == 'U':
        usb_l.append(val)
    else:
        ps2_l.append(val)

usb_l.sort()
ps2_l.sort()

len_usb = len(usb_l)
len_ps2 = len(ps2_l)

usb_l.append(float('inf'))
ps2_l.append(float('inf'))

'''
print(usb_l, file=sys.stderr)
print(ps2_l, file=sys.stderr)
'''

pos1 = 0
pos2 = 0

if a > len_usb:
    num_item += len_usb
    cost += sum(usb_l[:-1])
    pos1 = len_usb
else:
    num_item += a
    cost += sum(usb_l[:a])
    pos1 = a

if b > len_ps2:
    num_item += len_ps2
    cost += sum(ps2_l[:-1])
    pos2 = len_ps2
else:
    num_item += b
    cost += sum(ps2_l[:b])
    pos2 = b

count = 0

while num_item < m and count < c:
    if usb_l[pos1] < ps2_l[pos2]:
        cost += usb_l[pos1]
        pos1 += 1
    else:
        cost += ps2_l[pos2]
        pos2 += 1

    num_item += 1
    count += 1

print(num_item, cost)

C. Two strings

問題概要

文字列a, bが与えられる
文字列bから連続した文字列を取り除いて新たな文字列b'を作った時に
b'がaの部分文字列になるようにしたい
このとき、bから最小の連続した文字列を除いてできるaの部分文字列b'を求めよ

ここで、sの部分文字列とはsから0文字以上の文字を消し去ってできる新たな文字列のことである

感想

時間も無かったし、分からなかった
どっかで見た尺取り法（？）ってのでやるのかなあとか考えてた
解説見ると、bの左から文字を見ていってaの一致するインデックスを記憶した配列と
bの右から文字を見ていってaの一致するインデックスを記憶した配列を作って
そっからどうたらこうたらするみたいだった
人のコード参考にしながら書いたけど、やり方がまずくてＷＡになってた
貪欲法でやったからダメだったんだと思う
また後でやる気があったら何とかするかも

ＷＡになるコード

import sys

a = input().rstrip()
b = input().rstrip()

len_a = len(a)
len_b = len(b)

fwd = [0] + [float('inf')] * len_b + [float('inf')]
bwd = [0] + [float('inf')] * len_b + [float('inf')]

i_a = 0
i_b = 0

while i_a < len_a and i_b < len_b:
    if a[i_a] == b[i_b]:
        fwd[i_b + 1] = i_a + 1
        i_b += 1

    i_a += 1

i_a = 0
i_b = 0

while i_a < len_a and i_b < len_b:
    if a[len_a - 1 - i_a] == b[len_b - 1 - i_b]:
        bwd[i_b + 1] = i_a + 1
        i_b += 1

    i_a += 1

# print(fwd, file=sys.stderr)
# print(bwd, file=sys.stderr)

left = 0
right = 0

while min(fwd[left + 1] + bwd[right], fwd[left] + bwd[right + 1]) <= len_a:
    if fwd[left + 1] + bwd[right] < fwd[left] + bwd[right + 1]:
        left += 1
    else:
        right += 1

ans = b[:left] + b[len_b - right:]

if ans:
    print(ans)
else:
    print('-')