ABC116D_Various_Sushi
問題概要
N個の寿司について、それぞれパラメタ(ネタti, 美味しさdi)が設定されていて、ここからK個選んでscore = (美味しさdiの和+(ネタの種類x)^2)が最大となる時のscoreを求めよ。
方針・所感
並び替え可能で食べる優先順位が明らかに高いものがあるので貪欲っぽい、という初見の印象通り貪欲でした。同じ種類ボーナスポイント内で貪欲に寿司を選んで行って、種類数を変えて満足ポイントの最大値を見つける、という解にたどり着きましたが、
思考過程・実装過程としては、
(t,d)が{(1,100),(1,100),(1,100),(2,1)}とかの集合だったら前から順番に選んでいくべきだし、一方で、(t, d)が{(1,10),(1,9), (2,1), (3, 1), (4,1)...}などであったら種類が違うものを選んでいくべき
→前から順番に見ていって採用するかどうか決めるのは無理そう
→候補を絞ってその中での最大値を求める、とかなら大丈夫そう
→各ネタの中で最大の美味しさを持つ集合Sとそれ以外の集合Tに分ければ、同じ種類ボーナスポイントの中での美味しさ基礎ポイント最大値が貪欲に求められて、種類ボーナスポイントはO(10^5)しかないので行けそう
→(TLE後)美味しさ基礎ポイントの最大値は種類数が一つ違うところから2回の計算で求められて高速化できそう
→AC
という感じでした。
細かいところ・デバッグの記録
- 本当はmapで実装しないほうがメモリ的にエコっぽいが実装の楽さを優先。
- 書くのは面倒だがわかりやすさを優先してKとS_setの大小関係で場合分けした。
- 種類数がO(10^5)なので二乗するとO(10^10)となりintだとオーバーフローするのにはまってしまった。オーバーフロー注意すべし
これを書いた後にdrkenさんの書いた解説を見たら実装が100倍わかりやすかったのでそっちを見た方が良さげです。リンク->http://drken1215.hatenablog.com/entry/2019/05/15/002400
実装
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int N, K; cin >> N >> K;
//F_set := 各ネタで一番基礎ポイントが高いもの
//S_set := F_set以外
unordered_map<int,int> MP;
//F_setとS_setに分類します。
for(int i = 0 ; i < N; i++){
int t, d;
cin >> t >> d;
//ps[i] = {t, d};
if(MP[t] == 0) MP[t] = d;
else{
if(MP[t] < d){
S_set.push_back(MP[t]);
MP[t] = d;
}else{
S_set.push_back(d);
}
}
}
//(mapを全部表示するならunordered_mapの方が良い)
for(auto e: MP){
F_set.push_back(e.second);
}
sort(S_set.begin(), S_set.end(), greater<int>());
sort(F_set.begin(), F_set.end(), greater<int>());
// 各種類ポイントの時の最大値を求めて満足ポイント最大値をansとする。
ll ans = 0;
ll pref = 0; // 前のF_setの和を表示
ll pres = 0; // 前のS_setの和を表示
// KとS_setの大小関係で場合分け
if(K <= S_set.size()){
for(int i = 0; i < K; i++){
pres += S_set[i];
}
ans = pres;
//iは種類数
for(int i = 1; i <= K; i++){
if(i - 1 >= F_set.size()) break;
ll tmp = (ll)i * (ll)i;
pres -= S_set[K - i];
pref += F_set[i - 1];
tmp += pres + pref;
ans = max(ans, tmp);
}
}else{
for(int i = 0; i < S_set.size(); i++){
pres += S_set[i];
}
for(int i = 0; i < K - S_set.size(); i++){
pref += F_set[i];
}
for(int i = K - S_set.size() + 1; i <= K; i++){
if(i - 1 >= F_set.size()) break;
ll tmp = (ll)i * (ll)i;
pres -= S_set[K - i];
pref += F_set[i - 1];
tmp += pres + pref;
ans = max(ans, tmp);
}
}
cout << ans << endl;
}
参考にしたサイト等
-
AtCoder公式解説
*1:K - S_set.size(
ABC117D
問題概要
非負整数KとN個の非負整数列Aについて、0 <= X <= Kを満たす整数Xに対するf(X) =(X^A_1) + (X^A_2) + ...の最大値を求めよ。
方針・所感
問題を見てちょちょっとサンプルをいじってみた時は各ビットについてXは0,1の少ない方の値をとるのかと思いましたが、X <= Kの制限を忘れてました。(これで通るサンプルを選ぶ作問の方は素晴らしいと思います。)
これは上の桁から順に見て、XがX~Kとなって、自由にそれ以下のビットを選ぶことができない状態と、X < Kが確定して自由にそれ以下の桁を選べる状態間の遷移を考えてDPをするというのが正攻法っぽいです。所謂桁DPというやつ。
これは桁DPを知らなくても上から0,1を決めていく木さえ考えていれば自然に解法にたどり着きそうなので、分岐する選択肢から最善手を選ぶ系統の問題ではとりあえず木はイメージしたいところですね。
方針1: 桁DP
下に貼った実装の通りです。「 dp[i][j] := 上からi桁目について、ギリギリを選んだ(j == 0)時と、K未満が確定していて自由に下の桁を選べる時(j == 1)とで、f(X)が得ることが確定している値の最大値」と定義してあとは状態遷移に従ってdpテーブルを埋めています。
方針2: ギリギリの状態を考えた後にその下の桁で貪欲
Kのbitが立っている場所で0を選んだら、あとは自由に選べるので貪欲にいけるはずです。実装もそのうちしたい。
加筆予定
細かいところ・デバッグの記録
- 上からd桁目にbitが立っているか調べるのは、1LLを(桁数 - d)左シフトした値maskと、調べたい数Aとで、if(A & mask)を取れば良い。
- 最大桁を大きめに取る方が楽だが、その場合はギリギリの状態を持つ方がbitが立つ前に更新されないように注意する必要がある。
実装
実装(1)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_DIGIT = 50;
ll dp[100][2]; // 上からi桁目まで
int main(){
// 入力
ll N, K; cin >> N >> K;
ll dp[100][2];
for(int i = 0; i < N; i++) cin >> A[i];
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
// 各桁について処理
for(int d = 0; d < MAX_DIGIT; d++){
ll mask = 1LL << (MAX_DIGIT - d - 1);
// Aでもともとd桁目にビットが立っているものの個数
int num = 0;
for(int i = 0; i < N; i++) if(A[i] & mask) num++;
// Xのd桁目を0,1にした時に得られる値
ll get0 = mask * num;
ll get1 = mask * (N - num);
// smallerは最大桁の上では更新させない
if(dp[d][1] != -1) dp[d+1][1] = dp[d][1] + max(get0, get1);
// ビットが立ってるということは最大桁以下なので大丈夫
if(mask & K){
dp[d+1][1] = max(dp[d+1][1], dp[d][0] + get0);
dp[d+1][0] = dp[d][0] + get1;
}
else dp[d+1][0] = dp[d][0] + get0;
}
cout << max(dp[MAX_DIGIT][1], dp[MAX_DIGIT][0]) << endl;
}
実装(2)
coming soon...
参考にしたサイト等
ABC118D
問題概要
ちょうどN本のマッチ棒を使って作れる整数の中で最大のものを求めよ。
方針・所感
この問題のポイントは「『ちょうど』N本のマッチ棒を作る」という言葉にどれほど敏感になれたかにあるようです。(私は貪欲法でやって最後の方を全探索して値を求めようとしましたが、実装で詰みました。)貪欲法は、「〇〇以下の条件で、求める値のうち最大値」を考える時には強いですが、「ピッタリ」を考える場合は弱いみたい。
「ピッタリ」はDP！
以下DPによる2つの方針です。
方針1: 最大の整数を記録する
「(string)dp[i] := ちょうどi本のマッチ棒を使って条件を満たすことのできる整数の最大値」と定義して、1本目から順に更新していきます。これは最悪計算量がO(N^2MlonN)になりますがギリギリ通りました。実装がややこしいし遅いのでオススメ度低。
方針2: 最大の桁数を記録する
「dp[i] := ちょうどi本のマッチ棒を使って、条件を満たす整数を作る時の最大桁数」と定義します。これはdp[i] = max(dp[i - F[A_j] + 1)(F[x] := xに使うマッチ棒の数,1<=j<=M)でdp[N]までO(NM)で求めた後に、後ろからdpテーブルの桁数の変わり目を見ることで辞書順最大の整数を求める方法になります。DPテーブルを後ろから見て解を構成するのは典型っぽい。オススメ度高。
(↑例えば、以下にリンクを貼ったEDPCのF)
細かいところ・デバッグの記録
- intとstringの変換って面倒ですね。(string{(char)A[i] + '0'}とか一々しないといけない？)
- 方針1で桁数が元の数以上になった時に(dp[i] = max(dp[i - F[A[i]]] + 1, dp[i])として更新しようとしたところ、例えば77で9を更新しようとした時に辞書順では「9 > 77」なので更新できずバグらせた
- 方針2で、後ろから見る時に大きい整数から順に試していかないと最大整数にならない
実装
実装(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N, M; cin >> N >> M;
map<int,int> MP;
MP[1] = 2, MP[2] = 5, MP[3] = 5,MP[4] = 4, MP[5] = 5,
MP[6] = 6, MP[7] = 3, MP[8] = 7, MP[9] = 6;
for(int i = 0; i < M; i++) cin >> A[i];
for (int i = 1; i <= N; i++){
for(auto e: A){
if(i >= MP[e]){
if(dp[i - MP[e]].size() + 1 == dp[i].size()){
if*1{
string t = {(char)(e + '0')};
string tS = dp[i - MP[e]] + t;
sort(tS.begin(), tS.end(), greater<char>());
dp[i] = max(dp[i], tS);
}
}
else if(dp[i - MP[e]].size() + 1 > dp[i].size()){
if*2{
string t = {(char)(e + '0')};
string tS = dp[i - MP[e]] + t;
sort(tS.begin(), tS.end(), greater<char>());
dp[i] = tS;
}
}
}
}
}
cout << dp[N] << endl;
}
実装(2)
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
int main(){
//入力
int N, M; cin >> N >> M;
for(int i = 0; i < M; i++) cin >> A[i];
map<int,int> F; // F[i] := 数字iを作るのに使うマッチ数
F[1] = 2, F[2] = 5, F[3] = 5,F[4] = 4, F[5] = 5,
F[6] = 6, F[7] = 3, F[8] = 7, F[9] = 6;
string ans = "";
//dpテーブルを埋めていく
dp[0] = 0;
for(int i = 1; i <= N; i++){
for(int j = 0; j < M; j++){
if(i - F[A[j]] >= 0) dp[i] = max(dp[i], dp[i-F[A[j]]] + 1);
}
}
//前処理(数字がなるべく大きい方が辞書順が大きくなるので、数字が大きいものを先に並べておく)
sort(A.begin(), A.end(), greater<int>());
// dpテーブルが動いた時に数字は追加されているのでそれを逆に辿る
int remain = dp[N]; // 残り桁数
int match = N; // 残りマッチ数
while(match > 0){
for(int i = 0; i < M; i++){
if( match - F[A[i]] >= 0 && dp[match - F[A[i]]] == remain - 1){
ans += string{(char)(A[i] + '0')};
match -= F[A[i]];
remain--;
break;
}
}
}
// 最大桁数の中で辞書順最大なものを出力したい
sort(ans.begin(), ans.end());
reverse(ans.begin(), ans.end());
cout << ans << endl;
}
