2020/2/23 バチャ反省

はじめに

緑上位に行きたいのでバチャを立てて参加しました。 難易度でいうと700~900の茶色上位~緑色下位です。

バチャリンク

結果

結果

nabefutaくんに負けました～～
2完...
1問ずつ通して解説していきます。

---

1問目 塗り絵

問題文

考察A(問題文をかみ砕く)

解説ACをしました

まず、

(x1, x2)からの距離がr以下の部分を赤く塗ります。

より、赤く塗られた部分=(x1, y1)を中心とした半径rの円であることがわかります。
次に、

x2 <= x <= x3, y2 <= y <= y3を満たす(x, y)を青く塗ります。

より、青く塗られた部分=(x2, y2), (x2, y3), (x3, y2), (x3, y3)を頂点とする長方形であることがわかります。

考察B(問題文の再把握)

考察Aより、問題文の

赤く塗られた部分と青く塗られた部分が存在するかどうかをそれぞれ判定してください。 というものが何を表しているかを考えることができます。

これはそれぞれ

• 赤く塗られた部分がある = 円が長方形に完全に内包されていない
• 青く塗られた部分がある = 長方形が円に完全に内包されていない

という風に言い換えることができます。なぜなら、その色がない時、もう片方の色に完全に重なっている=内包されているといえるからです。

これを踏まえて問題文を見ると、

1. 円が長方形に完全に内包されていたらNO, それ以外ならYESを出力
2. 長方形が円に完全に内包されていたらNO, それ以外ならYESを出力

をすればいいことがわかります。この時注意しなければならないのが、完全に内包されているかの真偽と出力のYES/NOが逆になっていることです

考察C(条件の整理)

では、どうすれば完全に内包されているかがわかるかを考えていきます。

円が長方形に完全に内包されているか

これは円のxの最大値最小値、yの最大値最小値が長方形のxの最大値最小値、yの最大値最小値に内包されているかを考えればよいです。分割して考えると、

1. 円のxの最小値(x1-r)が長方形のxの最小値(x2)以上か
2. 円のxの最大値(x1+r)が長方形のxの最大値(x3)以下か
3. 円のyの最小値(y1-r)が長方形のyの最小値(y2)以上か
4. 円のyの最大値(y1+r)が長方形のyの最大値(y3)以下か

になります。この四点だけ見ればよい理由のイメージとしては、長方形に比べて十分に小さい、長方形に完全に内包された円があるとき、それを拡大していくと最初に長方形の辺に触れるのがこの四点のどれかになるから、といった感じです。

よって、これをすべて満たしていたらNO, 一つでも満たしていなかったらYESを出力します

長方形が円に完全に内包されているか

これは長方形の各頂点が円に内包されているかを見ればよいです。理由としては上と同じで、円に比べて十分に小さい、円に完全に内包された長方形を考えると、それを拡大していくと最初に円に触れるのが各頂点のどれかだからです。

さて、ある頂点(x, y)が円に内包されているかを考えるのは、

(x, y)と(x1, x2)の距離がr以下か

と表すことができます。円は(x1, y1)からの距離がrの範囲なので、当然といえます。 なので、各頂点に対して距離を計算し、r以下かを判定すればよいです。

これをすべて満たしていたらNO, 一つでも満たしていなかったらYESを出力すればよいです。

実装

x1, y1, r = map(int, input().split())
x2, y2, x3, y3 = map(int, input().split())
if (x1 - r >= x2) and (x1 + r <= x3) and (y1 - r >= y2) and (y1 + r <= y3):
    print("NO")
else:
    print("YES")

def check_dis(x, y):
    dis = ((x - x1)**2 + (y - y1)**2)**0.5
    return dis <= r

if check_dis(x2, y2) and check_dis(x2, y3) and check_dis(x3, y2) and check_dis(x3, y3):
    print("NO")
else:
    print("YES")

---

2問目 □□□□□

問題文

　 高橋君は大きさ 1 メートル四方のタイルを n 枚持っています。
　高橋君はこれらのタイルのうちいくつかを、重ならないように隙間なく並べて大きな長方形を作ろうとしています。
　出来上がる長方形はできるだけ正方形に近いほうがよいですが、同時に、使わずに余るタイルの枚数ができるだけ少なくなるようにしたいと考えています。
　長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和を最小でいくつにできるでしょうか。

考察A(雑な推理)

とりあえず、

1. 縦と横の差分だけで見るとa*aの形が一番うれしい
2. あまりだけで見るとa*b<=n以下の範囲でa*bが最大になる形が一番うれしい

ということがわかります。

考察B(諦め)

Aより、a*aのかたちに近く、かつa*bを最大化すればいいっぽいことがわかりました。
困りました、これ以上わかりません。

某「全探索するか～」

というわけで、sqrt(n)の周辺±1000位を全探索してみることにしました。

実装

from math import sqrt, floor
n = int(input())
ans = 10**10
for i in range(max(1, floor(sqrt(n))-1000), min(n+1, floor(sqrt(n))+1000)):
    for j in range(max(1, floor(sqrt(n))-1000), min(n+1, floor(sqrt(n))+1000)):
        if i*j <= n:
            ans = min(abs(i-j)+n-i*j, ans)
        else:
            break
print(ans)

ちゃんと通ってうれしいです。

---

3問目 Rain Flows into Dams

問題文

考察

解説ACをしました。

A_i :=ダムiにある水
X_i := 山iに振った水

降った水の総和とダムにある水の総和が等しいので、

S = A_1 + A_2 + ... + A_N = X_1 + X_2 + ... + X_N

が成り立ちます。 問題文より、

(X_i + X_(i+1)) / 2 = A_i

が成り立ち、2をかけて

X_i + X_(i+1) = 2 * A_i

になります。
Xを求めていきます。

X_1 = S - (X_2 + X_3 + ... + X_N)

ですが、

X_(n*2) + X_(n*2+1) = 2 * A_(n*2)

の性質を使うと、

X_2 + X_3 + ... + X_N =2 * (A_2 + A_4 + ... A_(N-1))

になります。この時、制約よりNは奇数なのでN-1が必ず偶数になり、式が成り立ちます。

これでX_1が求まり、同様にしていけばX_Nまで求まりますが時間計算量O(N²)かかってしまい、TLEしてしまいます。
ここで

X_i + X_(i+1) = 2 * A_i

より

X_(i+1) = 2 * A_i - X_i
X_i = 2 * A_(i-1) - X_(i-1)

の漸化式が立ち、楽に計算ができます。 これでX_2からX_NまでをO(N)で計算することができました

実装

N = int(input())
Alist = list(map(int, input().split()))
S = sum(Alist)
Xlist = [0] * N
Xlist[0] = S - 2 * sum([Alist[_] for _ in range(1, N, 2)])
print(Xlist[0], end=" ")
for i in range(1, N):
    Xlist[i] = 2*Alist[i-1] - Xlist[i-1]
    print(Xlist[i], end=" ")
print()

---

4問目 Binomial Coefficients

問題文

考察

解説ACです。
証明は以下の通りなんですが、 結論だけ言うと「nCrの最大化をするとき、nはalistのうち最大のもの、rはalistのうち最もn/2に近いもの」というらしいです。

これを実装していきます。 まず、nCrで考えるとnが入力と被ってしまうのでそれぞれm, ansと置きます。mは最大値をとるだけなので、固定です。alistの中から、ansを探索していくことがわかりました。

alistのうち最もa/2に近いものを探すには、差分をsbnとして、十分に大きい初期値を設定してから各aについて

abs(m/2 - a)

がsbn以下かを判定すればよく、sbn以下だったansをaに更新し、sbnをm/2- aに更新していけばよいです。

注意するべき点として、a==mの時は更新できません(i!=jなので)

実装

n = map(int, input().split())
alist = list(map(int, input().split()))
m = max(alist)
sbn = 10**10
for a in alist:
    if abs(m/2 - a) < sbn and a != m:
        ans = a
        sbn = abs(m/2 - a)
print(m, ans)

---

5問目 Special Trains

問題文

考察

駅Xからの経路を実際にシミュレーションをすればよさそうです。ある駅iから駅i+1に行く手順は共通で、以下の通りです。

1. 今の時間がS_iより小さければ、S_iにします、大きければ、そのまま進めます
2. now%F_i == 0なら、列車が出ます、それ以外なら、now + F_i - now % F_iまで待つ必要があります。
3. 列車に乗るので、now + C_iまで時間が動きます。

これを繰り返すことで、移動がシミュレーションできます。 コードにすると、以下のようになります。

now = max(now, C_i)
if now % F_i != 0:
    now += F_i - F_i % now
now += C_i

後はこれを始点iからNまで、iそれぞれについてシミュレーションしていけばいいです。
この時、NからNの経路は存在しないので素直に0を出力します

実装

N = int(input())
CSFlist = [list(map(int, input().split())) for _ in range(N-1)]
def calc_time(start):
    now = 0
    for i in range(start, N-1):
        C, S, F = CSFlist[i]
        now = max(now, S)
        if now % F != 0:
            now += F - now % F
        now += C
    return now
for _ in range(N-1):
    print(calc_time(_))
print(0)

終わりに

解説記事をバチャに対して書くのは初めてなんですが、すごい勉強になって最高ですね

これからもできるだけ書いていこうと思います！