コドフォ Educational Contst 89 A~C 解説[python]

A~Cの3完。後半集中が切れてDが解けなかった。pythonにとっては不利な問題だったけどもう少し数学的な考察を加えてあげれば間に合ったので実力不足

A. Shovels and Swords

考察

Atcoderの昔のARCの問題を簡単にしたような問題(
atcoder.jp)

２つの操作があるので両方に共通するものが何か考える
　両方の操作で、必ずa,bは1つ以上は減る、かつ合計で3減るという２つの共通点が見つかる。
　
　合計で3減ることから上界は(a+b)/3となる。
　また、aが律速になるケースとbが律速になるケースがあり、それぞれa,bが上界となる

実装

min((a+b)//3, a,b)を実装する

import sys
import math

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    a, b = map(int, input().split())
    print(min(a, b, (a + b) // 3))

B. Shuffle

ジャンル

整数列、操作、貪欲

概要

0,0.. 1,0,0..0 という整数列(`a[x] = 1`で他0) があり、それをm 回swapをすることでak = 1 にできるかを判定
ただし、それぞれの操作でswapに選べる２つのindex の範囲が ` l[i]<=c,d<=r[i]`と決まっている

考察

swapのindex c,d は同じところを選んでもいいので変えないこともできる。
つまり、一度a[k] = 1にできたらそれで終了にできる。
また、xを含みえない範囲でswapしても何も変わらないので、1が取りうる範囲l,r を更新すれば良い
範囲に含むなら更新する

実装

import sys
import math

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    n, x, m = map(int, input().split())
    l_x, r_x = x, x
    for i in range(m):
        l, r = map(int, input().split())
        if l_x <= r:
            l_x = min(l_x, l)
        if r_x >= l:
            r_x = max(r_x, r)
    print(r_x - l_x + 1)

C. Palindromic Paths

回文、構築

概要

n*m のgrid があり、それぞれのマスは0か1である
左上から右下にいく最短パスが全て回文になるようにgridを変更する時、最小の操作回数を求めよ

考察

2<=n,m<=30なので、全てを考えるとTLEしそう。いい性質を見つける
全ての最短パスが回文になるので、同じマスが回文として対応するマスを考えてみると、始点、終点からの距離がk であるマスは全て同じ値になる
それらは0,1どちらをとってもいいので、最小の操作回数にするためには、距離k の中でmajorityに合わせる。つまり0,1の少ない個数分変更する

実装

真ん中は例外で何も変えなくて良いことを考察抜けして時間食った。（よくある

import sys
import math

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    n, m = map(int, input().split())
    # 始点、終点からの距離がk であるマスで0 の個数を数える
    # 全体の個数は
    cnt = [0] * ((n + m) // 2)
    cnt_zero = [0] * ((n + m) // 2)
    for i in range(n):
        a = list(map(int, input().split()))
        for j in range(m):
            k = min(i + j, n - 1 - i + m - 1 - j)
            cnt[k] += 1
            if a[j] == 1 and (k * 2 != n - 1 + m - 1):
                cnt_zero[k] += 1
    ans = 0
    # print(cnt, cnt_zero)
    for i in range(len(cnt)):
        ans += min(cnt_zero[i], cnt[i] - cnt_zero[i])
    print(ans)

実装で真ん中処理を考えてなかったのと、軽く
バグった
全体で20min