masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

アルゴ式のテスターに選ばれました(4日目)

今日はやるだけにして書かないつもりでしたがやっぱり書きます.

進捗

動的計画法Q3-1,Q3-2をやりました. Q3-1はスムーズに解けましたが,Q3-2は2時間くらい悩んだと思います.

感想

Q3-2の問題はタイトルの通り,本当によく見るDPの問題でした.もちろん以前どこかで(多分EDPC)解こうとしたり解説を読んだりしたことがあります.ただ,今回は調べずに(アルゴ式を信じて)この3日でやってきたことを利用できないかという観点で考えました(邪道と言えば邪道かもしれない).

最初はdp[i][j]のようなリストを考えて,ボールiを箱に入れた時の重さを表して...などと考えていましたがうまくいきそうにありません(漸化式がたてれない).いろいろ考えるうちにdp[i]は重さiが(ボールの組み合わせで)作れるかどうか,というようにすればよいのではないかと考えました.そこからもう少し考えを進めて(DPの問題なのだからそこを利用すると...と考えました)dp[i][j]で最初のj個のボールを使って重さ[i]が作れるかを表せばうまくいきそうだと気づきました.

ここまで考えて,最初にやったQ3-1と同じ形の遷移になっていることにも気づくことができました.そうしたらあとは実装するだけなので(といってもここも少し手間取りました)無事ACを取ることができました.

N, M = map(int,input().split())
W = list(map(int,input().split()))
dp = [ [False]*(M+1) for _ in range(N)]
dp[0][0] = True

for i in range(N):
    for m in range(M):
        if dp[i][m]:
            if m+W[i] < M:
                dp[i][m+W[i]] = True
            elif m+W[i] == M:
                print('Yes')
                exit()
                
            if i+1 < N:
                dp[i+1][m] = True
                if m+W[i+1] < M:
                    dp[i+1][m+W[i+1]] = True

print('No')

ポイント

自分の中で2点ポイントになったことがあると感じています.1点目は事前にQ3-1が用意されていたことです.Q3-1の構造が頭にあったので,Q3-2のdp[i][j]を思いついたときに,この方法で答えを求めることができる,という確信につながりました.

2点目は重さを連続量だと考えないことです.自分の中でQ3-2で難しいと感じている点は「重さ」と「リストの添え字部分」を対応させるというところです.おそらくその理由の一つが,重さを連続量だと思っていて(一般的にはその通りだが,この問題では離散量と考えて良い),リストの添え字として使えるという発想に至るのに時間がかかったような気がしました.

あんまりわかっていないこと

TLEするような解法ってどんなのがあるんでしたっけ?

おわりに

明日,MacbookAirが届く予定です.