hotpepsiの練習帳

Codeforces 166

20:02

A. Beautiful Year

問題

• 美しい年とは全ての桁の数値が異なる年である
• 与えられた年以降で最初の美しい年を求める

方針

• ループして調べる
• 提出
• Passed System Test

B. Prime Matrix

問題

• 行列が与えられる
• ある要素を1回の操作で1だけ増やせる
• ある1行全てを素数、または、ある1列全てを素数にしたい
• 最小の操作回数を求める

方針

• 素数を求めてsetに入れておく
• 各要素について、その数以上の素数はlower_boundで求まるので、和を配列に入れる
• 全行、全列のうちの和の最小値が答え
• 提出
• Passed System Test

C. Secret

問題

• 1からNまでのN個の数値からなる集合XをK個の集合Uに分離したい
• Uの任意の2つの要素は互いに素
• Uの全ての和集合はX
• Uの要素は等差数列でないこと
• 条件を満たすUを求める

方針

• 等差数列を満たさないようにするためには要素が3個以上必要
• ということはN >= 3*K が必要 (そうでなければ-1を返す)
• 不規則的に配ればオッケー
• N=9、K=3のとき
• U1に1,2、U2に3,4、U3に5,6,...と2つずつ配ってから、U1に7、U2に8のように配れば不規則
• 余ったら全部U1に配ってよい
• 提出
• Passed System Test

D. Good Substrings

問題

• 文字列Sと、ダメな文字の一覧が与えられる
• ダメな文字を最大でK個まで含む、Sの連続したindexを使用した部分文字列の総数を求める

方針

• とりあえず愚直に
• 提出
• MLE

結果

ooo-- 2682pt 192nd/1677 rating 1687 -> 1680

Cまで解いて40分だったのでまあまあ良かった。

Dはハッシュ使えばいいらしい。