Codeforces Round #393 (Div. 2)

参加しました

A.o
B.o
C.-

A. Petr and a calendar

問題概要

行ごとに月、火、……、日となっているカレンダーを作る
m月が何曜日始まりかがd(1:月、2:火、……、7:日）で与えられるので、
そのときのカレンダーが何列必要になるかを求める
ただしうるう年ではないとする

感想

まず各月が何日あるのかっていう情報が必要なので、それはリストに作っておく
で、最初の列に(7 - d + 1)日分が使われるのでその分を引く
最後に余った日数を７で割って、切り上げる
後はこれをコードにする、計算量はO(1)

関数使わないで切り上げをやるテクニックがあるみたいで、
a/bを切り上げにするには、(a + (b - 1))// b とすれば切り上げになる
これ使えば解説に書かれている式と一致するかな

簡単だけどちょっとめんどくさい問題
各月が何日あるのかを手打ちで入力するんだけど何かここにミスが入りそうだった
一応ググったけど覚えたほうがいいかな
「西向く士」（２，４，６，９，１１）っていう語呂合わせがあって
これらの月は３１日無い月、閏年じゃなければ２月は２８、それ以外は３０日
西向く士以外の月は全部３１日

添え字のズレでミスしそうだった

実際に書いたコード

import sys
import math

day_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

# print(sum(day_month))

m, d = map(int, input().split())

ans = 1 + math.ceil((day_month[m - 1] - (7 - d + 1)) / 7)

print(ans)

B. Frodo and pillows

問題概要

n人のホビットがいる
n個のベットが並んでいて、枕は全部でm個ある
ホビットは少なくとも１つの枕が無いと寝られないが、彼らは
できるだけ多くの枕を持って寝たいと考えている
ただし、隣との枕の差が２以上になるとホビットは怪我をしてしまう

フロードはk番目のベットで寝る
誰も怪我をしないように枕を分けたとき、フロードが持つことができる
枕の最大数を求める

制約条件

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

感想

問題文の解釈に手間取った
"any hobbit gets hurt if he has at least two pillows less than some of his neighbors have. "
が意味分かんなくて、グーグル翻訳に突っ込んでも
「彼の隣人の何人かよりも少なくても少なくとも2つの枕があれば、どんなホビットも怪我をするでしょう。」
ってなって？？？って感じだった
それで例を見て隣との枕の差が２以上になるとダメなんだろうなっていう風に解釈した
英語力が無くて例を見ないと問題が理解できないことが結構ある
直訳風に解釈するなら
「隣人の持っている枕の数より、少なくともそれより２つ少ない枕を持っているならば、ホビットは怪我をしてしまう」
って感じになるんだろうか

ともかく問題を理解（？）して、とりあえず絵を書いて方針を考えた

まず皆最低でも一つ枕が無いとダメなので最初にホビット全員に一つずつ枕を配る
次にフロードの枕（★）だけを一つ増やす
さらにフロードの枕を増やしたいが、隣との差が２になるとダメなので
フロードとその両隣の枕を一つ増やす
さらに枕を増やしたいが、今度は両隣の隣にも枕を増やさなければいけない
のでフロードと両隣、さらに二つ隣の枕を増やす
以下同様にやっていって、フロードの枕が増やせなくなったら終了

アルゴリズムの大枠としてはそんな感じだけど、
近いほうの境界に到達したときと全体に行きわたったときで場合分けする必要がある
それをコードにすると以下のような感じになる

何となく計算量的に不安があるけど、m - nが２乗の速度で減っていくので
最悪でもO(sqrt(m - n))には収まる、mが最大でも10^9なのでこれならPythonでも間に合う
実際はちょっと怖いからPypy3で出したけど、Python3でも割りと余裕を持って通っていた

実際に書いたコード

import sys
import math

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

ans = 1
m -= n
l = min(k - 1, n - k)
step = 1

for i in range(l):
    if m - step < 0:
        print(ans)
        sys.exit(0)

    m -= step
    step += 2
    ans += 1

while step < n:
    if m - step < 0:
        print(ans)
        sys.exit(0)

    m -= step
    step += 1
    ans += 1

ans += m // n

print(ans)

ちなみに想定解では二分探索を使おうということだった
二分探索というとソートされた配列から目的のものを探すときに
半分ずつ探索する領域を狭めていく方法だけど
こういう最大値や最小値を求める問題にも応用できるよう
この二分探索は、できる領域とできない領域の境界を求めようとしている
この二分探索が終了したときはできる領域の最大値（または最小値）と
できない領域の最小値（または最大値）が求まっている
バイナリサーチならO(log(m))なので確かにこっちのほうが優秀だと思った

import sys

def is_able(n, m, k, mid):
    res = 0

    if k < mid:
        res += (mid + mid - k + 1) * k // 2
    else:
        res += mid * (mid + 1) // 2 + k - mid

    right = n - k + 1
    if right < mid:
        res += (mid + mid - right + 1) * right // 2
    else:
        res += mid * (mid + 1) // 2 + right - mid

    res -= mid

    return True if res <= m else False

n, m, k = map(int, input().split())
btm = 1
top = m + 1

while top - btm > 1:
    mid = (top + btm) // 2

    if is_able(n, m, k, mid):
        btm = mid
    else:
        top = mid

ans = btm

print(ans)

このとき、btmの初期値にはいかなるときも達成できる値を
topの初期値にはいかなるときも達成できない値を選んでおく必要がある

C. Pavel and barbecue

問題概要

パベルはバーベキューをしている
n本の串があって、その串を置換pに従って動かしていく
そして串をひっくり返すかどうかはb_iによって決める
b_i = 1なら串をひっくり返す、そうでなければそのまま

全ての串が全ての場所を両方の向きで通るようにしたい
そのために与えられた置換pとb_iの数字をいくつ書き換えれば
条件を満たすようにできるかを求めよ

制約条件

• 1 <= n <= 2 * 10^5
• p_1, p_2, ..., p_n は置換
• b_i = 0 or 1

感想

英語力無さすぎてskewerが串だと知らずskierだと思ってた
何度か読んでやっと何がしたいのか分かったが、これは難しそう、解けないと思って
４５分くらい時間残ってた気がするけど、諦めて出来もしないハックに手を出した
それでC++分かんねー、人のコード読みにくいー、と思ってたら終わった
Aはともかく、Bは皆二分探索でやってたからなおさら分からなかったんだと思う

それで解説読んだらすごく簡単に解けるみたいだった
まずは置換pを巡回置換に分解したときの、巡回置換の数を数える
それが１だったら既に全ての場所を回るようになってるから
書き換えなくていい、２つ以上あるんだったらその巡回置換の数分だけ
書き換えたら全ての場所を回るようにできる
後者は一見分かりにくいけど、各巡回置換を島だと考えて、
その各島の間を一周できるように橋渡しをするって考えるといいかな

例えば
2 3 1 5 6 4 8 9 7
っていう置換があったとするとこんな感じ

それで、ひっくり返す操作のb_iだけどこれはもしb_iの総和が奇数だったら
一周して戻ってくるときに元の向きとは逆向きになっているのでそのまま
逆に偶数だったら一周しても元の向きのままなので、このまま何周させても
ずっと同じ場所に同じ向きでしか訪問できない
だからこのときはどこかのb_iを0から1にするか、1から0にすればよい
いずれにせよ書き換える回数は一回だけ

っていうのをコードにすればいい
計算量は巡回置換の数を数えるのに必要なO(n)か
巡回置換の数え方他に上手いやり方ありそう

想定解

import sys

n = int(input())
p = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 0
num_cycles = 0
checked = set()

for i in range(n):
    if i in checked:
        continue

    checked.add(i)

    nxt = p[i] - 1

    while nxt != i:
        checked.add(nxt)
        nxt = p[nxt] - 1

    num_cycles += 1

ans += num_cycles if num_cycles != 1 else 0
ans += (sum(b) % 2) == 0

print(ans)