ebisuke競プロ初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。C言語も少しだけ勉強中

Educational DP Contest #3 C - Vacation

DPの勉強としてEducational DP Contestに取り組んでいます。
今回は3回目 C - VacationをPythonで解いてみます。

EDC C - Vacation

C - Vacation

問題文

明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。
夏休みはN日からなります。 各i(1≤i≤N) について、i日目には太郎君は次の活動のうちひとつを選んで行います。
・A: 海で泳ぐ。 幸福度aiを得る。
・B: 山で虫取りをする。 幸福度biを得る。
・C: 家で宿題をする。 幸福度ciを得る。太郎君は飽き性なので、2日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

制約

・入力はすべて整数である。
・1≤N≤10^5
・1≤ai,bi,ci≤10^4

n = int(input().strip())
a = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    a.append(array)

dp = [[0 for j in range(100010)]for i in range(3)] # ※1 夏休みの日数より多く、各要素が0の2次元配列を準備
# ※2 dp = [[0] * 100010] * 3は不可

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp1 = dp[j][i] + a[i][k]# ※3 i-1日目にjの行動、i日目にkの行動を行う場合の幸福度
            if dp1 > dp[k][i+1]: # ※4 dp[k][i+1]はi日目にkを行ったときの得られる幸福度
                dp[k][i+1] = dp1
                
dpmax = 0 # ※5 求める最大の幸福度
for i in range(3):
    if dp[i][n] > dpmax:
        dpmax = dp[i][n]

print(dpmax)

この問題では太郎君が夏休みの間、毎日A,B,Cの3通りのなかから1つの行動をとることができ、その行動により幸福度を得ます。
夏休みが終わるときの最大の幸福度を求める問題です。
注意として2日続けて同じ行動はとれないという制約があります。

上記のプログラムは配るDPの考え方で進めております。
まず前提として行動A→0,B→1,C→2のようにプログラム上は行動を数字で表しています。
※1のように用意する配列dpは2次元配列としました。
dp[a][b]は、b-1日目に行動aを行った場合の幸福度になります。
※2に記載しましたが、dp = [[0] * 100010] * 3のように2次元配列を作成すると、例えばdp[1][1]にある値に代入するとdp[0][1]やdp[2][1]まで同じ値が代入されました。
これでは意図した結果が得られないため、※2の2次元配列の作成の仕方はやめたほうがいいようです。
※3ではi-1日目に行動j、i日目に行動kの行動を行う場合の幸福度dp1を計算しています。
このときjとkは行動を表す数字で、jとkが等しいときi-1日目とi日目に同じ行動を行ったことになります。
したがって※3に至るまえにif文でjとkが等しい場合は※3以降の計算を行わないようにしています。
※4でdp[k][i+1]とdp1を比較し、dp1が大きければ代入します。
n日目までこの計算を繰り返してきます。
n日目に行う行動はA,B,Cの3パターンありますので※5以降でn日目の最大幸福度をdpmaxに代入し、最後にdpmaxを出力することでACでした。


今回は2次元配列を用いたDPでした。
初心者ゆえに2次元配列を思い通りに使いこなせず苦労しましたが、DPの考え方自体はこれまでの問題と大きく変わっていないと感じました。
ACに至るまで大変ですが、1問1問新たな学びがありますので今後もEDCを続けていきます。


これまでのEDCの記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

Educational DP Contest #2 B - Frog 2

前回に続きDPの勉強としてEducational DP Contestに取り組みます。
以前の記事の問題と似ていますので参考に貼っておきます。
ebisuke33.hatenablog.com

EDC B - Frog 2

B - Frog 2

問題文

N個の足場があります。 足場には1,2,…,Nと番号が振られています。 各i(1≤i≤N) について、足場iの高さはhiです。
最初、足場1にカエルがいます。 カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。
足場iにいるとき、足場i+1,i+2,…,i+Kのどれかへジャンプする。 このとき、ジャンプ先の足場をjとすると、コスト|hi−hj|を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

・入力はすべて整数である。
・2≤N≤10^5
・1≤K≤100
・1≤hi≤10^4

n, k = map(int, input().strip().split())
h = list(map(int, input().strip().split()))

dp = [float('inf')] * 100010 # ※1足場数より数が多く、各要素が無限大の配列を準備

dp[0] = 0 # 初期条件

for i in range(n):
    for j in range(1,k+1):
        if i+j <= n-1:
            dpk = dp[i] + abs(h[i] - h[i+j]) # ※2足場iからk離れた足場へ移動したときのコスト
            if dpk < dp[i+j]:
                dp[i+j] = dpk

print(dp[n-1])

DPについてこちらの記事で学習しました。
わかりやすく記載されており大変助かりました。
動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita
DPの種類として貰うDPと配るDPがあり、以前の記事A - Frogでは貰うDP、今回は配るDPでプログラムが書かれています。
※1では足場の数が制約より多く、各要素が無限大の配列dpを準備しています。要素を無限大としたのは後で出てくるdpkと比較するためです。
B問題ではカエルはk個まで足場を飛ばして移動できるようになりました。
for文は2重ループになっており、※2で足場iからj個離れた足場に移動するときのコストdpkを配っています。
dp[i+j]の要素と配られてきたdpkを比較し、dpkが小さければ配列に代入します。
この繰り返しで、dp[n-1]の最小コストが求まります。

今回のプログラムはPythonとして提出するとTLEが3個出てしまいますが、Pypyで提出するとACとなりました。
まったく知識がなく説明はできないですが、PypyではACとなったことからプログラムの内容は問題なかったと思っています。

いろんなことにつまずきながらですが、今後もEDCの問題を解いていきます。

Educational DP Contest #1 A - Frog 1

ABC184のD問題を解くためにDPの学習方法を探していたところ、Educational DP Contest(EDC)の存在を知りました。
ちょうどよい機会でしたのでEDCを進めていきたいと思います。

DPについてはこちらの記事で勉強しました。大変助かりました。
動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita

EDC A - Frog 1

A - Frog 1

問題文

N個の足場があります。 足場には1,2,…,Nと番号が振られています。 各i(1≤i≤N) について、足場iの高さはhiです。
最初、足場1にカエルがいます。 カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。
足場iにいるとき、足場i+1またはi+2へジャンプする。 このとき、ジャンプ先の足場をjとすると、コスト|hi−hj|を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

・入力はすべて整数である。
・2≤N≤10^5
・1≤hi≤10^4

n = int(input().strip())
h = list(map(int, input().strip().split()))

dp = [0] * 100010 # (※1)制約条件の足場数より多い要素数の配列を準備

dp[0] = 0 # (※2)初期条件
dp[1] = abs(h[1] - h[0])

if n > 2:
    for i in range(2,n):
        dp1 = dp[i-1] + abs(h[i] - h[i-1]) # (※3)足場i-1から足場iへ移動したときのコスト
        dp2 = dp[i-2] + abs(h[i] - h[i-2]) # (※4)足場i-2から足場iへ移動したときのコスト
        if dp1 > dp2:
            dp[i] = dp2
        else:
            dp[i] = dp1

print(dp[n-1])

次の足場へジャンプ(移動)するごとに高さにおうじたコストがかかるカエルが、目標の足場まで最も少ないコストで移動する方法を求める問題です。
下の絵のように足場iから足場i+1(青線)か足場i+2(赤線)のどちらかに移動できます。
f:id:ebisuke33:20201126220245p:plain
iからi+2へ移動したほうが、移動回数が減るのでコストは減りそうですが、足場の高さによっては逆にコストがかかることも考えられます。
このような問題でDPという手法が使えます。
※1のように想定される足場の数より多い要素数の配列dpを準備します。dp[i]は足場i+1まで移動するときの最小コストを書き込んでいきます。
※2では初期条件としてdp[0]つまりスタート地点のコストを代入しました。スタート時点ではまだ動いていないのでコストは0です。
次の行ではスタート地点の次の足場に移動するコストをdp[1]に代入しています。その後のループの条件分けが面倒だったためです。
足場の数Nが2の場合はdp[1]が解答となり、Nが2より大きければfor文でdp[i]を求めていきます。
※3 dp1は隣の足場i-1から足場iに移動するとき必要なコストを求めています。スタート地点から足場i-1までの移動コストdp[i-1]に、足場i-1からiに移動するときのコストを足すことで求められます。
※4 dp2は足場i-2から1つ飛ばしで足場iに移動するときのコストを求めています。
このdp1dp2を比較して小さいほうをdp[i]に代入することで足場iまでの最小コストがわかります。
この作業を繰り返すことで目的の足場Nまで移動するときの最小コストdp[i-1]が求まります。
最後にdp[i-1]を出力してACとなりました。

DPを学習していなければ、私はどのように進めるか方針を定めることができず、解けない問題だと感じました。
EDCはたくさん問題がありましたので、今後も学習を続けて記事にしていきます。

AtCoder ABC183 Pythonの解答例 #3

コンテストに出たときは解けなかったAtCoder ABC183のD問題に挑戦します。

いもす法を使って解いていきたいと思います。
ebisuke33.hatenablog.com

ABC 183 D - Water Heater

atcoder.jp

問題文

給湯器が1つあり、毎分Wリットルのお湯を供給することができます。
N人の人がいます。i番目の人は時刻SiからTiまでの間 (時刻Tiちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分Piリットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。
すべての人に計画通りにお湯を供給することはできますか?

制約

・1≤N≤2×10^5
・0≤Si

n, w = map(int,input().strip().split())

a = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    a.append(array)

t = [0] * 200100 # (※1)すべての要素が0の配列 tの要素数は2×10^5以上

for i in range(n):
    t[a[i][0]] += a[i][2]  # (※2)時刻Si(=a[i][0])にPi(=a[i][2])だけ増加
    t[a[i][1]] -= a[i][2]  # (※3)時刻Ti(=a[i][1])にPi(=a[i][2])だけ減少

can = 1  # (※4)お湯の量が足りるか判定フラグ

for j in range(200050):
    t[j+1] += t[j] # (※5)累積和の計算
    if t[j] > w:
        can = 0 # (※6)時刻tの使用量t[i]がお湯の供給量Wを超えたらcanフラグを0に
        break

if can == 1:
    print("Yes")
else:
    print("No")

いもす法では※1のように要素がすべて0の配列を用意します。
この問題ではTiは2×10^5という制約がありますので、用意した配列tの要素数は2×10^5より大きい200100としました。
※2ではi番目の人がお湯を使い始める時刻Si(=a[i][0])においてお湯の使用量Pi(=a[i][2])分だけ配列tの要素を増加させています。
※3では反対にi番目の人がお湯を使い終わる時刻Ti(=a[i][1])で、お湯の使用量Pi(=a[i][2])分だけ配列tの要素を減少させています。
次に※4では判定する準備としてcanフラグを作成し、1を代入しました。判定ループを抜けても1のままならお湯の供給量は足りることになります。
※2と※3でお湯の使い初めと使い終わりの情報が入った配列が完成しましたので、※5で累積和を計算していきます。
これで配列tの要素は、その時刻におけるN人のお湯の使用量を表します。
お湯の供給量Wを配列tの要素が越えなければcanフラグは1のままで、超える場合はcanフラグに0が代入されループを抜けます。
ループを抜けた後にcanフラグの値に合わせて出力することでACとなりました。

NGパターン

次のコードは実際に私がコンテストに出たときに提出したものでTLEとなったものです。

n, w = map(int,input().strip().split())

a = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    a.append(array)

can = 1

for i in range(201000):
    sum_p = 0
    for j in range(n):
        if a[j][0] <= i and a[j][1] > i:
            sum_p += a[j][2]
    if sum_p > w:
        can = 0

if can == 1:
    print("Yes")
else:
    print("No")

時刻と使用者の2重ループでは時間切れとなりました。
計算量?が多すぎるようで、それを解決する方法のひとつがいもす法なんですね。
プログラムの書き方で実行速度が大きく変わることがわかりおもしろく感じました。
計算量についても学習し、記事にまとめられたらいいなと思います。


ABC183についての以前の記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

いもす法の勉強

AtCoder ABC183のD問題の公式解説に「いもす法」が紹介されていました。

今回はABC183のD問題を解く前にまず「いもす法」について勉強したいと思います。

参考させていただいた記事はこちら
いもす法 - いもす研 (imos laboratory)


ABC183のD問題を例題とします。
atcoder.jp
3人お湯を使う人がいて順にA・B・Cさんとします。
Aさんは時間2~4まで5リットル、
Bさんは時間1~2まで2リットル、
Cさんは時間3~4まで4リットルのお湯を使います。
以上の条件でいもす法を用いて考え方を整理していきます。

①すべての時刻でお湯の量が0の配列を用意する
f:id:ebisuke33:20201123105550p:plain
②Aさんは時間2~4まで5リットル→使い始めの時刻2で+5、使い終わりの時刻4で-5
f:id:ebisuke33:20201123105625p:plain
③Bさんは時間1~2まで2リットル→使い始めの時刻1で+2、使い終わりの時刻2で-2
f:id:ebisuke33:20201123105647p:plain
④Cさんは時間3~4まで5リットル→使い始めの時刻3で+4、使い終わりの時刻4で-4
f:id:ebisuke33:20201123105714p:plain
⑤配列の累積和を計算する(要素N=要素N-1 + 要素N)
f:id:ebisuke33:20201123110153p:plain
上記の手順で各時刻におけるお湯の使用量がわかります。
時刻3の9リットルが最大使用量となります。

以上のようにすべて要素が0の配列に使い初めのタイミングに使う量をプラスし、使い終わり時刻でマイナスしていきます。
最後に累積和を計算することで最大の使用量がわかります。

いもす法を初めて学び考え方はわかりましたが、実際に使うときはなかなかうまくいかないと思います。
例題に使用したABC183のD問題で実際にプログラミングを行って、より深く学習したいと思います。

AtCoder ABC184 Pythonの解答例

AtCoderのABC184に出場し、初めてC問題まで解くことができました。
atcoder.jp

最適なプログラムにはほど遠いと思いますが、
C問題まで私の解答を例として書いていきたいと思います。

ABC184 A - Determinant

A - Determinant

問題文意訳

2×2行列 A が与えられます。Aの行列式はad−bcで求められます。Aの行列式を求めてください。

制約

・入力は全て整数
・−100≤a,b,c,d≤100

a, b = map(int,input().strip().split())
c, d = map(int,input().strip().split())

ans = a*d - b*c

print(ans)

入力を受け取って問題文通りの計算を行えば行列式ansが求まります。
ansを出力してACとなりました。

ABC184 B - Quizzes

B - Quizzes

問題文

高橋くんは、N問のクイズに答えます。高橋くんの持っている点数ははじめX点で、クイズに正解すると1点増え、不正解だと1点減ります。
ただし、持っている点数が0点のときに不正解となった場合は点数は減りません。
高橋くんのクイズの結果が文字列Sで与えられます。
Sの左からi番目の文字が o のとき、i問目が正解だったことを、x のとき、i問目が不正解だったことを表します。
高橋くんの最終的な点数はいくつでしょうか?

制約

・1≤N≤2×10^5
・0≤X≤2×10^5
・Sは o と x からなる長さNの文字列

n, x = map(int,input().strip().split())

s = input()

for i in range(n):
    if s[i] == "o":
            x += 1
    else:
            x -= 1
    if x <= 0:
        x = 0

print(x)

高橋君の持ち点がXで与えられ、文字列Sをもとに点数を増減させます。
for分で文字列の1個目から最後まで順に確認していきます。
文字列の該当する文字が○ならxを1増加させ、バツなら1減少させます。
問題文から点数は0点より小さくしてはいけないため、xが0以下なら0を代入しています。
ループを抜けた後、xを出力するとACでした。

ABC184 C - Super Ryuma

C - Super Ryuma

問題文

無限に広がる2次元グリッドがあり、マス(r1,c1)に駒「超竜馬」が置かれています。
この駒は、超竜馬がマス(a,b)にあるとき、以下のいずれかの条件を満たすマス(c,d)に動かすことができます。
・a+b=c+d
・a−b=c−d
・|a−c|+|b−d|≤3
超竜馬を(r1,c1)から(r2,c2)に動かすのに必要な最小手数を求めてください。

制約

・入力は全て整数
・1≤r1,c1,r2,c2≤10^9

r1, c1 = map(int,input().strip().split())

r2, c2 = map(int,input().strip().split())

ans = 0

if r1 == r2 and c1 == c2:
    ans = 0
elif r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2 or abs(r1 - r2) + abs(c1 - c2) <= 3:
    ans = 1
elif (abs(r1 - r2) + abs(c1 - c2)) % 2 == 0 or abs(abs(r1 - r2) - abs(c1 - c2)) <= 3 or abs(r1 - r2) + abs(c1 - c2) <= 6:
    ans = 2
else:
    ans = 3

print(ans)

超竜馬は斜めにどこまでも動くことができるので、3手あればどこマスでも移動できます。(これに気付くのに時間がかかりました…)
したがって、0手・1手・2手になる条件を考えていき、どれにも該当しなければ3手とするプログラムを考えました。
0手の条件は初期マスと目的マスが一致していることですので、入力から渡されるrとcをそれぞれ比較して確認できます。
1手で動ける範囲は問題文に記載してある条件ですので、そのまま書きました。
2手の条件は3通りあると思います。
まず将棋の角のように斜めにどこまでも動けるので、移動するマスの数が偶数であれば2手で移動できます。(将棋の盤面を描いて考えるとわかりやすかったです)
また、斜めにできるだけ近くまで動いたあとで目的のマスが3マス以内ならば2手ですので、その条件をabs(abs(r1 - r2) - abs(c1 - c2)) <= 3と書きました。
最後に目的のマスが6マス以内なら2手で動けますので、その条件も足しています。目的のマスが3マス以内の場合は先に記載してあるので、自動的に3より大きく6マス以下の2手で動ける条件となります。
以上のプログラムでACできました。


今回 初めてC問題まで解くことができましたが、D問題はさっぱりわかりませんでした。
公式解説を読むとまた新しい手法が載っていましたのでそちらも勉強したいと思います。
(勉強することが多くなりすぎてアウトプットが滞りがちです…)


2020/11/25追記
D問題を解くには確率DPを理解しなければならないようですが、そもそもDP自体の難易度が高いようです。
調べていくとEducational DP ContestというDPの教育的問題集がありましたので、こちらに取り組み理解を進めたいと思います。
D問題への再挑戦には時間がかかりそうです…

商の求め方

AtCoder競技プログラミング)をpythonで取り組んでいますが、
割り算をすると値が小数になってしまうことがありました。

これが地味に困る問題で
整数になるように次のようにint()を用いていました。

n = 10                         # 1から10までの和を求める
sum = int(n * (n + 1) / 2)     # 1からnまでの和の答え
# sum = 55

いろいろ他のプログラムをみていると次のように//を用いている方がいました。
試してみると値が小数から整数となり小さな悩みが解決しました。

n = 10                         # 1から10までの和を求める
sum = n * (n + 1)// 2     # 1からnまでの和の答え
# sum = 55

基礎的な勉強は大事ですね。
こんな手間のかかる方法で進めてしまっていたのは独学のデメリットだと思います。
周りの方から勉強させてもらい、いい方法を覚える姿勢を持ち続けたいです。