Tenka1 Programmer Beginner Contest2019

ハロートナミです。

Tenka1 Programmer Beginner Contest2019やりました。3完太郎なので3完でした
天下一なのにビギナーコンテスト

ネタバレがあります。

A

考え

AとBの大きい方よりCが小さく
AとBの小さい方よりCが大きいならYes

書いたソース

A,B,C = map(int, input().split())

if min(A, B) <= C and C <= max(A,B):
    print('Yes')
else:
    print('No')

B

考え

問題文が簡潔なので問題文通りにやる

書いたソース

N = int(input())
S = input()
K = int(input())

target = S[K-1]

a = ''
for c in S:
    if c != target:
        a += '*'
    else:
        a += c
print(a)

ここまではめちゃ簡単だったんですよ

C

問題文にめちゃくちゃ混乱してWA3回出しました

考え

最終的にどこからの場所から"左側が全部白、右側が全部黒"になればOK
なので、左から右までここでやったらコストなんぼ、を計算していく。
計算量が多くなりそうなので2分探索とかやる。

書いたソース

import bisect
N = int(input())
S = input()
# 右全部#
b = []
w = []
for i in range(N):
    if S[i] == '#':
        b.append(i)
    if S[i] == '.':
        w.append(i)

kouho = []
for i in range(0,N+1):
    cost = 0
    #iより右にある白の数
    cost += len(w) - bisect.bisect_left(w,i)
    #iより左にある黒の数
    cost += bisect.bisect_left(b,i)
    
    if cost >= 0:
        kouho.append(cost)

print(min(kouho))

コストが負になるの警戒してるけど多分バグが残ってた時の名残ですね。
これにたどり着くまで50分ぐらいかかったし、なんか日本語が全然読めなくて3回もWAしたし、ACした時はガッツポーズしました。このC難しかったよね？難しかったと信じたい

D

事前に600点だと発表されてたので多分厳しいだろうなとは思っていた

考え

えーなんか大変……
各値について、辺aに使う or 辺bに使う or 辺cに使う、の3つの候補がある。
aに使うのとbに使うのをシミュレートしてけば、辺cの長さはまだ使ってない数の和になるからうまい事計算出来る？

書いたソース

間違いなくTLEするけど時間かければ正しい答え出るだろーな、以上のソースが書けませんでした。それを載せます

N = int(input())
nList = []
for i in range(N):
    nList.append(int(input()))

nList.sort()
#三角形が存在する条件：最長辺が、残り2辺の合計未満である

#絶対TLEするけど記念にパピコしたい
kouho = []
def dfs(idx, a, b, c, at):
    if max(a,b,c) > a+b+c - max(a,b,c) + at:
        # 長辺が長すぎるので終わる
        return
    if idx == N:
        if a > 0 and b > 0 and c > 0:
            if max(a,b,c) < a+b+c - max(a,b,c):
                kouho.append((a,b,c))
        return
    re1 = dfs(idx+1, a+nList[idx], b, c, at-nList[idx])
    re2 = dfs(idx+1, a, b+nList[idx], c, at-nList[idx])
    re3 = dfs(idx+1, a, b, c+nList[idx], at-nList[idx])

dfs(0,0,0,0,sum(nList))
print((len(kouho)%998244353))

なんかこう、シンセティックカドマツを思い出しながらやってみたんですけどダメですね。解説読んできます

結果

ヤッター水色パフォでレートが1000を超えました。よかったね。おわり