hotpepsiの練習帳

Codeforces 139 Div2

02:32

A. Dice Tower

問題

• サイコロを縦に積む
• 一番上の面と、横の2面だけか見えている
• 並べ方が一意かどうかを求める

方針

• 上からありえないやつをフィルタしていったがWA
• 見えている2面が全部同じこと(＝上面で見えている面が横面に出ないこと)が条件

B. Well-known Numbers

問題

• 直前のk個の和からなる数列をkぼなっちと呼ぶ
• 数sをkぼなっちの和で表す

方針

• メモ化したらごみ(ゼロ)が入ってしまいWA
• 大きい数から貪欲でやればよいっぽい

C. Barcode

問題

• 与えられた模様をバーコード状に変更するための最小コストを求める
• それぞれの色はX以上Y以下の幅であること

方針

• コンテスト中は方針が立たず
• 他の方のブログを読む
• DP
• 長さlenのバーコードを考える
• 全体の長さがlenで、長さL(X～Y)で白で終わるバーコードを考える
• 全体の長さがゼロまたはlen-Lで、黒で終わるバーコードがあればOK

結果

半年ぶりに参加。ゼロ完。

AはA問題らしくてとても良い問題だと思う。

Bはテスト不足。

Cは典型問題。こういうのをさくっと解けるようになりたい。