競プロ日和

競技プログラミングを楽しむ

みんなのプロコン 2019 D

D atcoder

問題

解けなかった。

解答PDFを参考にすると、

f:id:kani_panda:20190212221026p:plain

となるので、配列をDPで更新していけば解けることが分かる。

import sys
readline = sys.stdin.readline
L = int(input())
dp = [0] * 5
for a in map(int, (readline() for _ in range(L))):
    back = a % 2 if a > 0 else 2
    through = (a + 1) % 2
    dp[4] = min(dp[:5]) + a
    dp[3] = min(dp[:4]) + back
    dp[2] = min(dp[:3]) + through
    dp[1] = min(dp[:2]) + back
    dp[0] += a
print(min(dp))

みんなのプロコン 2019 C

C atcoder

問題

選べるパターンは２つ

①ビスケットを1枚増やす

②ビスケットA枚をB枚に交換する（２回分の操作）

②の場合は、得られるのは次の３パターン

  1. B - A < 2

    この場合は①よりも少なくなるので①を選択

  2. B - A == 2

    この場合は①と同じになるので①を選択

  3. B - A > 2

    この場合は①よりも多くなるので、②を選択

①を選ぶ場合は、k + 1個のビスケットが得られる。

②の場合は、

  1. まずはビスケットをA枚に増やす（a - 1回）
  2. ②は２回分の操作のため、(k - a + 1) / 2回行える。得られるビスケットはB - A枚。
  3. 2を行った後にkが1回残っていた場合は①を行い、ビスケットを１枚得る。
def solve():
    k, a, b = map(int, input().split())
    if a > b - 2:
        return k + 1
    k -= (a - 1)
    return a + (b - a) * (k // 2) + (k & 1)
print(solve())

みんなのプロコン 2019 B

B atcoder

問題

一筆書きとして考えた。

すべての道を１回ずつ通ってすべての街を訪れることができるのは、N字型かコの字型の２パターンのみ（回転や反転したものは同一と考える）。

同じ道を２回以上通った場合は同じ町を３回訪れることになるので、その場合はNO。

それ以外はYES。

from collections import Counter
print("YES" if max(Counter("".join(input().replace(" ", "") for _ in range(3))).values()) <= 2 else "NO")

キーエンス プログラミング コンテスト 2019 C - Exam and Wizard

C atcoder

問題

解けなかった。

ヒープを使うのかと思い考えてみたが、解法が思いつかなかった。

解答PDFと動画を見て解き方を理解した。

まず、AよりもBが大きい場合は答えが存在しないため、-1を出力。

次に、配列A-Bの要素のパターンは３つ。

①マイナス(minus) : A < B

②0 : A == B

③プラス(plus) : A > B

このうち、②の0は無視し、①をminus配列に、③をplus配列に入れる。

minusは必ず変更するため、minusの個数をansに格納。

そうすると、plusからいくつの要素を変更するか、が要点となる。

結局、(minusの個数) + (変更したplusの個数) が答え。

pythonコード

キーエンス プログラミング コンテスト 2019 B - KEYENCE String

B atcoder

問題

YESのパターンは、余計な文字がkeyenceの後ろ、中、前の３つ。

①keyence・・・

②key・・・ence

③・・・keyence

それを考慮すればいい。

pythonコード