AtCoder Regular Contest 068 - D言語で競プロ

参加しました
２完でした

C - X: Yet Another Die Game

C: X: Yet Another Die Game - AtCoder Regular Contest 068 | AtCoder

問題概要

６面体サイコロを９０度転がして一番上に来た面の数だけ点数がもらえる
このとき、x点以上取るために必要な最小の操作回数を求めよ
ただし最初は好きな面が上に来るように置くことができる

制約

1 <= x <= 10^5
xは整数

感想

最初問題見たときサイコロ問題めんどくさそー、って思った
で、できる限り大きい点数を取り続けるほうがいいから
6,5,6,5,6,5,...
って繰り返しいくのがよいって気づいたらサイコロほとんど関係なかった
なのでまず(x // 11) * 2回転がして後は
x % 11 == 0ならそれで終了
1 <= x % 11 <= 6 なら追加で+1,
x % 11 > 6 なら追加で+2
って感じでやりました、計算量はO(1)

実際に書いたコード

x = int(input())
 
ans = (x // 11) * 2
x %= 11
 
if x > 0:
    if x > 6:
        ans += 2
    else:
        ans += 1
 
print(ans)

解説聞いてたらこうやるのもいいけど、二分探索でやるのが楽ですねって言ってた
前のcodeforcesの枕の問題でも出たけど、境界探索型の二分探索みたいな奴ですね
自分的には楽っていう感覚は無いけど、確かに二分探索なら
ややこしい場合分けで複雑になって混乱しなさそうだと思った
振る回数をnとすると
nが偶数ならば、得点は(n // 2) * 11 もらえる
nが奇数ならば、得点は(n // 2) * 11 + 6 もらえる
この得点がx以上かどうかでバイナリサーチする
こんな感じかな？
計算量はO(log(x))なので、x = 10^15でも余裕ですね
logってすごい

x = int(input())
 
btm = 0
top = 10 ** 15
 
while top - btm > 1:
    mid = (top + btm) // 2
    if mid % 2 == 0:
        score = (mid // 2) * 11
    else:
        score = (mid // 2) * 11 + 6
 
    if score >= x:
        top = mid
    else:
        btm = mid
 
print(top)

btmには必ずx未満になる回数を
topには必ずx以上になる回数を初期値として設定する
このバイナリサーチが終わったときにtopに入ってる値が、得点がx以上になる操作回数の最小値になっている
書きなれてないせいか、やっぱり上の方法より楽って認識はあんまり無い

D - Card Eater

D: Card Eater - AtCoder Regular Contest 068 | AtCoder

問題概要

N枚のカードがある、それぞれには整数A_iが書かれている
この中から３枚を取り出して、最小値、最大値が書かれたカードを消すことができる
この操作を繰り返して全てのカードが相異なるようにしたとき最大で何枚のカードが残るか？
ただし、次のような条件がある

制約

Nは奇数
3 <= N <= 10^5
A_iは整数
1 <= A_i <= 10^5

感想

パッと解法が思い付かないので、小さな例から試します
例えば
1,1,2,3,3
とあれば1,2,3と取って、1,3を消せばオッケーですね
1,1,1,2,3
とあれば1,1,1と取って、1,1を消せばオッケーですね
だから基本的にダブってるカード２枚を最大値、最小値になるよう取ってきて、２枚ずつ消していけるなあって思いました
でもダブってるカードの総数が奇数のとき、最後の１枚を消すときにもう１枚はダブってないとこから犠牲を出す必要があるんですね
こういう感じでダブりを数えて、場合分けして、Nから引く、みたいな方法でやりました
こういうときに何かと便利なCounterを使いました、これほんと便利ですね
計算量はO(N)かな？

from collections import Counter

N = int(input())
cnt_A = Counter(map(int, input().split()))

dabuli = sum(cnt_A.values()) - len(cnt_A.values())
 
if dabuli % 2 == 0:
    ans = N - dabuli
else:
    ans = N - (dabuli + 1)
 
print(ans)

でも解説聞いたらもっと楽にできたみたいです
まずカードの種類数を求めて、それをmとすると、答えはmかm - 1のいずれかです
これは上の考察でもあったようにダブりが偶数ならダブった分だけ消せて、奇数ならダブってないところから１枚犠牲を出さなきゃいけない、という性質から分かります
問題はmかm-1、どっちが答えかということですが、これは最初に与えられるNが奇数で１回の操作で２枚ずつ減るという条件から、残る枚数は常に奇数であることが分かります
mとm-1、どちらか一方は偶数でどちから一方は奇数なことは明らかなので、奇数であるほうを出力すればよいです
なんか手品みたいなやり方で凄いと思った
種類数を求めるのはA_iを集合で受け取って、それの長さを測ればＯＫですね

というわけで理想解はこちら

N = int(input())
A = set(map(int, input().split()))

m = len(A)

if m % 2 == 0:
    ans = m - 1
else:
    ans = m

print(ans)

エレガントですね

E - Snuke Line

E: Snuke Line - AtCoder Regular Contest 068 | AtCoder

問題概要

0, 1, 2, ..., M - 1, M
と(M + 1)個の駅がある
駅0から出発して間隔dで下車してそこで売ってる名産品を買う
名産品はN種類あり、名産品iは[l_i, r_i]の区間で買うことができる
d = 1, 2, 3, ..., M
としたとき、それぞれ買える名産品の『種類数』を出力せよ

制約

1 <= N <= 3 * 10^5
1 <= M <= 10^5
1 <= l_i <= r_i <= M

感想

なんかこういうのっていもす法って奴でやればいいんだったっけ？
って思ってその方針で意気揚々とコーディングしてできたー！と思ったら
求められてるのは個数じゃなくて種類数だってことに気づいて時すでに遅しだった
間違った方向に走ってしまうって辛いですね、精神的に
そこでやっとこの問題の難しさに気づいて諦めました
一応ちょっと書き直してやったんですが計算量的に通るわけないコードでした
解説も聞いたけど、なんか難しそうで根本的な力不足を感じた
Fenwick Treeって前のcodeforcesの奴でも出てきたなあ

どう考えてもTLEするコード

N, M = map(int, input().split())
L = {}
R = {}
 
for i in range(N):
    left, right = map(int, input().split())
    if left in L:
        L[left].add(i)
    else:
        L[left] = {i}
 
    if (right + 1) in R:
        R[right + 1].add(i)
    else:
        R[right + 1] = {i}

eki_kaeru = [set()] * (M + 1)
tmp = set()
 
for eki in range(M + 1):
    if eki in L:
        eki_kaeru[eki] = tmp.union(L[eki])
    else:
        eki_kaeru[eki] = tmp.copy()
    if eki in R:
        eki_kaeru[eki] -= R[eki]
 
    tmp = eki_kaeru[eki]
 
ans = []
 
for d in range(1, M + 1):
    buy = set()
 
    for i in range(0, M + 1, d):
        buy = buy.union(eki_kaeru[i])
 
    ans.append(len(buy))
 
print(*ans, sep='\n')