競プロ日記

三井住友信託銀行プログラミングコンテスト2019

A問題

B問題

C問題

D問題

E問題

F問題

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

namespace std {
template <typename A, typename B> struct hash<pair<A, B>> {
  size_t operator()(const pair<A, B> &p) const {
    const static size_t rand_seed = random_device()() + 0x9e3779b9;
    size_t seed = rand_seed;
    seed ^= hash<A>()(p.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    seed ^= hash<B>()(p.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
  }
};
}

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.clear(), graph.resize(vertices);
  for (const auto &e : edges) graph[e.src].emplace_back(e);
  if (!directed) for (const auto &e : edges) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
}

void dfs(Graph &g, int v, int p, int prev_col, unordered_map<pair<int, int>, int> &cmap) {
  int col = 0;
  for (const auto &e : g[v]) {
    if (e.dst == p) continue;
    ++col;
    if (col == prev_col) ++col;
    cmap[{ v, e.dst }] = col;
    dfs(g, e.dst, v, col, cmap);
  }
}

void bfs(Graph &g, unordered_map<pair<int, int>, int> &cmap) {
  queue<tuple<int, int, int>> que;
  que.push(make_tuple(0, -1, 0));
  while (!que.empty()) {
    int v = get<0>(que.front()), p = get<1>(que.front()), pc = get<2>(que.front());
    que.pop();
    int col = 1;
    for (const auto &e : g[v]) {
      if (e.dst == p) continue;
      if (col == pc) ++col;
      cmap[{ v, e.dst }] = col;
      que.push(make_tuple(e.dst, v, col));
      ++col;
    }
  }
}

Graph graph;
int main(void) {
  int n;
  cin >> n;
  Edges edges(n - 1);
  rep (i, n - 1) {
    int a, b;
    cin >> a >> b;
    edges[i] = {--a, --b, 0};
  }
  edges_to_graph(graph, edges, n, false);
  int maxi = 0;
  rep (i, n) maxi = max(maxi, (int)graph[i].size());
  unordered_map<pair<int, int>, int> cmap;
  dfs(graph, 0, -1, 0, cmap);
  // bfs(graph, cmap);
  cout << maxi << "\n";
  rep (i, n - 1) cout << cmap[{ edges[i].src, edges[i].dst }] << "\n";
  return 0;
}

3完してしまったやつ。
今回の学びポイントは全てのプログラムに関わるから大きい。

学びポイント①

配列の最大要素数は気をつけよう。
int型は4byte。
AtCoderのメモリ制限は多くの場合1024MB。
配列に入れられるint型の数は1024*10^6 / 4 = 256*10^6 ≒ 2*10^8個。
int[N][N]を取りたい場合、N=10^4はOKだけどN=10^5だったらだめ！
long longでもN=10^4までいけるが、これ以上大きなメモリ確保すると足りなさそう。
単純計算だとこうなるが、vectorだと余分にメモリ取るので最大でこれの半分以下になる。
通常配列は知らないけど滅多に使わないからいいや。

vector<int> v[N][N]
N=10^4まで。

vector<long long> v[N][N]
N=10^3まで。

学びポイント②

unordered_mapにpairを入れられるようにする。
2つの値をkeyにして値を取り出したいことは割と多い。
mapで計算量が間に合うならそれでも良いが、想定解法とは違うがC++パワーでunordered_mapを使えば間に合うなんてことがあるかもしれない。
そのためにpairのハッシュ関数を作成した。


以下本題
方針は合っていたが、TLE連発でつらい気持ちになりながら3つ程実装した。
全滅してコンテスト終了後に幅優先で実装してみたがこれもだめ。
？？？となりながら解説PDFの実装を参考にmapを使ってみると簡単にAC。
それ以外の反省点として、結果的にミスではないが、ai<biを見落としていた。
aiからbiへの値しか保存していなかったのだが、ai<biの制限がなければこれだと間違いになる。
v[ai][bi] = v[bi][a[i] = xとか、map[{ai, bi}] = map[{bi, ai}] = xとかする必要がある。

解法1
色数は頂点に集まる辺の最大数。
彩色する問題だし深さ・幅優先探索でいけそうだ。
まず深さ優先で実装。
探索しながらN*Nのvectorに辺の色を格納していく。
O(N)
サンプルケースが合ってるやったー！
TLE+MLE+RE。
初めてMLE見たかも。

解法2
とりあえず探索部分が悪いんだなと考える。
木の探索なんだから(辺の数-1)*2しかループしないはずなんだけどなぁ。
往々にして深さ優先は幅優先よりリソース食う感じがするので幅優先にしようかと考えるが、幅優先だと今まで使った色全部保存しないといけなさそうと勘違いして幅優先は諦め。
グラフを統一的に扱うために使っている自作のGraphクラス(ただの3重vector)がメモリ食うかも？ということで辺のみを管理するようにする。
O(N)
WA+TLE+MLE+RE。
全部のせ。
そもそもこの方針がダメなんだろうなと気づきながらも、一縷の願い的な感じで急いで実装したから色々抜けてたんだと思う。
TLEとMLEが出た時点でダメなんだなと判断して別の解法を考えた。

解法3
おれは探索をやめるぞ！ジョジョーーッ！！
辺ベースでループして、繋がっている両頂点の使っていない色のうち、最も小さいものを選ぶ。
各頂点の使っていない色はsetで管理。
事前に1～N-1までの数を格納していき、使ったら消す。
O(NlogN)
TLE。

解法3を提出した時点で終了5分前なのでほぼ諦めていたが、この後も考察を続けていくことを考えると、探索をやめてTLEになるのはたちが悪い。
探索がMLE,REの原因でしかない。
実際の原因はvectorの要素数が大きすぎること。
③も要素数NのsetをN個持ってるのでダメ。
setはvectorと違って要素数が上限を上回るたびにメモリ2倍とかしないから、かろうじてMLE,REは防げたのかな。
本来はN*Nの配列じゃなくてpair<int, int>の連想配列で持ちたかったのだが、O(1)で取り出せるunorderd_mapはデフォルトだとpairをハッシュ化できないので、O(logN)とわざわざ遅いmapを使うのはちょっと・・・となる。
そこでO(1)で取り出せるvectorを選んだわけだが見事に大失敗。
O(logN)でも間に合うのは間違いないのだが、あえて遅いの選ぶ必要もないかと思ってしまった。

pair<int, int>のハッシュ化

でもO(1)でできる内容なのは間違いないので、pairのハッシュ関数を作ってみた。
冒頭のACコードは、深さ優先+unordered_mapでO(N)の実装である。
64bit環境ならsize_tも64bitのはずなのでint型2つ並べるだけで衝突は起きないはずだが、より汎用的にするためにboost::hash_combineを真似た。
テンプレートの特殊化の本来の目的に沿うとpair<int, int>を別に指定するべきなのだろうが、普通に面倒である。
このハッシュ関数をテンプレート入りさせようかなと考えているし、32bit環境のオンラインジャッジもあるかもしれないので、汎用性 is 正義である。
速度的にもintを2つ並べる場合とほとんど変わらない。
数回程度の試行だが、5ms程度しか違いがなく、ハッシュが衝突したのかジャッジシステムの誤差なのか分からないレベルなので問題なく動作しているだろう。

一応動くようにはなったのだが、方向性を参考にした記事と見比べてみると乱数の使い方が違う。
参考にした記事では、初期seedを0とし、pair要素のhash値と同様にseedをシフトしたものと足し合わせている。
pairの値によって定まる部分を定数とおくと、こちらはseedをシフトして足し合わせる回数が少ないのと、足し合わせる順番が最初になっただけなので、記事の方法でランダム性が確保されるなら初期値を乱数にするだけでも良さそうな気がするのだが、正直全く分からない。
偉い人に教えてもらいたい。

ちなみにハッシュ関数を間違えてpairのfirstのみで計算するようにして提出してしまったのだが、その場合TLEが出た。
テストケースにstarとあったので、おそらく頂点1から頂点2~Nの全てに辺を張っているのだろう。
そう仮定するとpairのfirstは全て1になるので、全部のハッシュが一致することになり、毎回O(N)の比較が発生することになる。
全体でO(N^2)になるからTLEになる、なるほどハッシュ関数大事。

さらに蛇足で、ハッシュ関数を調べていて、ハッシュが一致した場合の処理を初めて知った。
よく考えてみればハッシュが一致したからと言って、それが本当に欲しいkeyなのかハッシュが衝突しているだけなのか分からないなぁとは思っていたのだが、詳しくは調べていなかった。
調べると普通にハッシュに対応するkeyと調べたいkeyを直接比較しているようだった。
試しにvectorのハッシュ関数を実装すると、値の取得にvectorの要素数に比例した時間がかかった。
次に自作の構造体とそのハッシュ関数だけを用意すると、「"=="が定義されてないよ」的なエラーメッセージが出てきてコンパイルエラーになった。
vectorを==で比較すると要素数に比例した時間がかかることから、ハッシュが一致すれば==で比較していると見て間違いないだろう。
元となるkeyのコピーがサイズに関わらず保存されていることになるので、自作の大きな構造体のハッシュ化関数を作成して構造体を直接keyにするより、被らないことを保証するハッシュ化関数を作成し、そのハッシュ値をkeyとした方がメモリには優しいということになるのかな。
STLは気にするべきことが多いね。
一度Effective STL読んでみたいな。

差分: +36

3完
3完再び・・・。
またこのレベルでレート下がるのか・・・と思ったけど下がらなかった。
ちょっとDが難しめだったみたい？
みんながどこで間違えたか分からないからどこがネックなのかは分からないが、自分のミスはこの問題に対するものではなく競プロ全般に対する知識が甘かったせいなので、たまたまみんなが解けなくてよかった。
それを除いて今回も細かいミスやらかした。
私の人生は常にミスとともにあることを再認識した。

A問題

かんたん。めんどくさい。
最近この手の問題は連想配列を使うことにしている。
問題文ではシングルクォーテーションで囲まれてて少しむっとなりながら全部手打ちしたが、置換とか使った方が良かったかな。

B問題

このループする系でかなり悩んで結局スマートに実装できなかったのがあるのだが、今回はそんなことなく簡単だった。
かなり悩んだ問題が競プロだったかどうかも分からないが、足して余り取って足してってしてたら元に戻っちゃってうわあああってなったの思い出す。
他の人の解法で見たが、Z超えたら26引くの方が簡単だったな。

C問題

びっくりするくらいすぐに二分探索だと分かった。
成長ポイント。
こっちはめぐるちゃんに二分探索教えてもらってるんだが？そんな問題でどうにかなると思ってるのか？
るんるん気分で15分溶かした。

問題文読んで二分探索と認識
+30秒

入力とか二分探索部分とか全体の実装
+2分

d(N)は十進表記での数・・・？それNと違うの？Nは何進法？よく見たら桁数だった。
改行位置の妙。
+1分

実装終わり！
・・・サンプルケースの計算が終わらない。
途中経過とか色々出力してmid=(ok+ng)/2であるべき部分を、mid=(ng-ok)/2にしていることに気づく。
+10分以上

mid=(ok+ng)/2よりもmid=(ng-ok)/2+okの方がより直感的だなと感じる人間なので、その感性と普段mid=(ok+ng)/2で書いてるのがすごく悪い感じに合わさってしまった形。
せっかく二分探索がすごく簡単になるように教えたのに、midの計算間違えるような人は知りませんってめぐるちゃんに言われそう。

D問題

あーうんうんグラフの探索ね。
色数は必ず二色でいけるのでは？と謎なこと思いながら木ってなんだっけと調べ直す。
木ってこんなんだっけと思いながら色数は頂点に集まる辺の数だなと分かる。
彩色する問題だし深さ優先探索でいけそうだ。
グラフの実装もだいぶ慣れてきたし特に確認もせず最後まで実装しちゃったが、サンプルケースは合ってるし提出したらTLE+MLE+RE。ひええ。
3つくらい解法試したが全部だめ。
詳しくは次の記事に書く。
結局はdp[10^5][10^5]の配列を作ったのが間違いで、mapに入れたら通った。
方針も実装も間違っていなかったのが悔やまれる。

E問題

え、うそなんでD解けないの・・・と絶望しながら見た。
うーーーーーん、難しいのか簡単なのか分からない。
こういう問題は手を出さない方が良い。

コンテスト終了後に軽く解説を読んだだけでは理解できなかった。
-1すれば個数を考える必要がないというのはなるほどという感じだが、何通りかを計算するのはどうやるんだろう？

ちなみにEの方が難しい問題は参加したコンテストでは初。

F問題

全く見てない。
コンテスト後に軽く解説を読んだら結構すぐに分かった。
本番でも(Dさえ解ければ)解けたかも？

1が続く部分では、多少損しても1の開始地点近くから始めないと1の連続を飛び越えることができないので、その辺どうしようというのが第一感想。
よく考えてみれば、なるべく多く進むようにして1が連続する手前で進む数を調整して例え1しか進めなくても良いとする場合と、何らかの良い感じに1が連続する手前に止まれるように進む方法を考える場合とでは、移動するサイコロを振る総回数は変わらなさそう。
どこで止まるべきかを再帰的に考えていくと、[0*a][1*b][0*c]みたいな1を0で挟む列になって、aの値はなるべく多く進むようにするかそうしないかでは回数的には一緒だなってことになる。
ならない？

回数求まったら、1の手前まで6,6,3みたいに進んでたのを3,6,6にすれば良いので、今度は再帰的の逆に一番短い[0*a][1*b][0*c]から増やして考えていくと、難しそうだなーってなる。
短い列から考えていくの再帰的って言うのか？
難しそうだなーってなりながらも、後ろから大きくすれば良いんだなと気付けた。
ってこれさっきやったやないかーいってことで、後ろからなるべく多く進めば良いと。

本番思いつけるならこの解法の可能性が高いが、この貪欲法よりもグラフ的な解法の方が勉強になるなぁと感じた。
マスXから行けるマスはX+1～X+Mなので、Xからそれぞれに辺を張ったグラフとして考え、各頂点からゴールまでの最短経路を考える。
ここまで考えられたらRMQ使えそうっていうのは分かる。
辞書順最小にしたいので、振る回数が最小になるものの中から一番手前にあるものを選んでいく。

この既にある情報を使ってグラフを作成する、というのはかなり身につけたい内容。
ABC143 E Travel by Carでも出てきたテクニックで、次のレベルに進む第一歩という気がしている。

ちなみにEでも軽く解説を読んでるが、参加したコンテストが終了した後は解けた解けてないもうすぐ解けそうに関わらずとりあえず軽く解説を読むことにしている。
結局時間内に解ききらなければいけないので、このレベルの考察をするためにはこの問題のこの部分が無駄だったという感覚を磨きたいから。
今の所ミスが無駄だったで終わってるのが悲しいところ。


そんな感じでまた3完。
今回のDのミスは二度としないという誓いのために個別に記事を書きます。
はー悔しい。

問題
ACコード - 元コード(掲載コード)
ACコード - 初期化を分ける

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 28;
constexpr lint   INFL = 1LL << 60;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n, t;
  cin >> n >> t;
  vector<pair<int, int>> ab(n);
  rep (i, n) cin >> ab[i].first >> ab[i].second;
  vector<vector<int>> dpl(n + 1, vector<int>(t)), dpr(n + 1, vector<int>(t));
  rep1 (i, n) {
    int li = i - 1, ri = n - i;
    rep (j, t) {
      int lnext = j + ab[li].first, rnext = j + ab[ri].first;
      dpl[i][j] = max(dpl[i][j], dpl[i - 1][j]);
      if (lnext < t) dpl[i][lnext] = max(dpl[i][lnext], dpl[i - 1][j] + ab[li].second);
      dpr[n - i][j] = max(dpr[n - i][j], dpr[n - i + 1][j]);
      if (rnext < t) dpr[n - i][rnext] = max(dpr[n - i + 1][rnext], dpr[n - i + 1][j] + ab[ri].second);
    }
  }
  int maxi = 0;
  rep (i, n) {
    rep (j, t) {
      int sum = dpl[i][j] + dpr[i + 1][t - 1 - j];
      maxi = max(maxi, sum + ab[i].second);
    }
  }
  cout << maxi << endl;
  return 0;
}

件のひどいACを解き直した。
出題者さんの想定解法の「DPを2つに分けて足し合わせる」解法で実装した。
参加記事でも書いたがコンテスト中に思いついた方針は合っていて、「iを除いた最大値のDPをそれぞれ考えると良さそうだがO(N^2*T)になってしまうどうしよう」と悩んでいた。
2つに分けてDPがまさにこれを解決するための手段で頭に残りそうなのでこちらにした。

理解が及ばないということは全くなくて本来なら記事も書かないのだが、かなり基本的だが気をつけないといけない部分があったので忘れないようにメモしておく。

問題なのは37,39行目で、この部分を忘れていて少し時間がかかった。
例えば37行目は、1つ前のiの値dp[i-1][j]をdp[i][j]に持ってきているだけで、初期化に近い。
これをどのように書けばスマートかというのが気になるポイント。

38行目の状態の遷移には関係ないので、例えば初期化として遷移の前にまとめて以下のようにしても問題ないはずである。
rep(j, t) dp[i][j] = dp[i-1][j]

前の状態から値を持ってくる必要があるか考え、必要なら初期化として先にまとめて処理するのは忘れにくくて良さそうな気がするが、初期化も状態の遷移の1つであると考えると、遷移が無駄に分けられているのは気持ち悪いような感じもある。
初期化を分けた場合の違いとしては、ループを別に回すのでその分ほんの僅かに処理増加するかも？と、maxの比較が必要なくなるので前者よりは明らかに若干の高速化が期待できるが、これはあまり考えなくて良いだろう。
ちなみに今回の問題だと、初期化を分けることで112ms→103msと、少しだけ早くなった。

記事を書くために初期化を分けて書いてみたが、こちらの方がすっきり書けたように感じられた。
いつも参考にさせてもらっているkmjpさんのコードを見ると、元々のコードのように初期化として分けない実装になっている。
真似するのも良いが、割と好き好きな感じもあるので、今後は分ける方針で書いていきたい。
そろそろDPコンテスト(Education～の方)をやろうと思ってたので、最近色々経験したDPの手法とか方針とかを定着させていきたい。

差分: +175

5完
申し訳程度に初5完。
申し訳程度に初水色パフォーマンス。
申し訳程度に緑になった。
Eで終了5分前にTLE3回出して終了17秒前に提出したのがAC。
ジャッジ中に終了通知が来て焦った。
EはACしたものの、いわゆる嘘解法ってやつな上にその嘘解法も未完成。
未完成なのは提出段階から分かっていたが、その部分直すのは時間間に合わ無さそうだったので、出さないよりも出した方がワンチャン！と思ったら通ってしまった。
後で(嘘解法を落とすのとは別の)ダメそうなテストケース考えてチェックしたら普通に間違ってる。

A問題

かんたん。
でも最後の中括弧間違えて消して提出しちゃってCE。
焦って再提出したのは次解くぞと開いていたB問題用のファイル。
つまりテンプレートをそのまま提出してしまった。
CEはジャッジに時間かかるし、テンプレートも入力形式も合ってなくてジャッジに時間かかるし、無駄に時間潰した+WA。
かなり凹んだ。

B問題

かんたん。

C問題

焦ったからなのかちょっと理解できなかったけど10分くらいでAC。
サンプルケース使って解くのはもはやただのパズル。
最初は以下のように考えていた。
町iから町jへの行き方はN-1通り。
それらは全て同じ確率のはずだから、iを固定してjをN-1回ループし、それぞれの距離の合計をN-1で割ったものをsumに足す。
町iをN回ループした後のsumが答え。
でも答えが合わない。
N-1で割るんじゃなくてNで割るようにしたらサンプル全部と合ってAC。

D問題

方針はすぐ立ったのに解き方がアホ。
解説PDFと同じように、n+2m=X, 2n+m=Yの連立方程式を立てた。
なんなら変数名まで同じだった。
そこからnを全探索した(?)。
どう考えても不定形の連立方程式じゃないので、解は一意に定まるはずである。
でも答えが何通りでMOD取るってことは、不定形のパラメータ付きの解になるんじゃないかと思い込み、nを1からXまで全探索した。
もちろんオーダーは計算して全探索にしたのだが、連立方程式を立てた意味が皆無である。
しかもひどいことに、係数2がかかる部分を勘違いして実装していて、全然気づかずに方針が間違っているのかと15分以上溶かした。
連立方程式活用してたらこんなことには・・・。
これ解いた時点で45分+1WA。

E問題

本番ACコード - スーパー嘘解法
スーパー嘘解法修正版(正しい嘘解法)

問題の嘘解法。
特に工夫するところも見つからず単純だけど難しいなぁという印象。
またお得意の問題理解ミスなのだが、「T-0.5分後以降に注文できない」を、「T+0.5分後までなら注文できる」と思い込んでいた。
もはや無茶苦茶である。
それに気付いたのが終了15分くらい前で、実装が大きく変化することはなかったものの、細かい部分はおかしかったり無理矢理だったりする。
無駄なソートをしていたり謎にdp[T]の値を使っていたり。
TLEしてるんだからせめてソート部分は消すべきだった・・・。
まずちょっとミスがあった状態でTLE(残り5分)。
ミス直して(時間に関わる部分は直していないので当然だが)TLE。
setをunorderd_setに直して、ソートされていないことに関わる部分も直してTLE。
unorderd_setの代入部分を参照変数に直してAC(残り17秒)。

以下色々書いて修正したけどそもそも方針が間違いだったというお話。
この嘘解法がTwitterでも報告されていたが、自分はその嘘解法すら未完成だった・・・。
未完成のスーパー嘘解法を嘘解法に昇華させる謎の考察だが、せっかく書いたので残しておく。
一番最初に考えたのは、「最後に注文する料理を決めてそれぞれに最大値求めたい！」というお手本のような方針だったのになぜこうなったのか・・・。

方針としてはDP。
dp[i分まで] = pair{おいしさの最大値, 今まで食べた料理の種類}
おいしさの種類がsetからunorderd_setに変えた部分。
iを0~T-1まで計算した後、全てのiに対して、dp[i]のおいしさの最大値+まだ食べていない料理の最大値を調べ、それの最大値が答え。
全体的には間違っていない(と思う)のだが、同じおいしさの時の処理をしていないのがダメ。
(2分, おいしさ2), (2分, おいしさ2), (4分, おいしさ4)という3つの料理があった場合、4分でおいしさ4を得る方法は、0,1番目を選ぶ方法と2番目のみを選ぶ方法があるが、最後に1つ好きなものを足せることを考えた場合、前者は+4できて後者は+2しかできないので、前者を選ぶべきである。
同じ美味しさだと処理しない実装なので、先に2番目が選ばれてていると間違えてしまう。
例えば、嘘解法のコードに[3 5 2 2 2 2 4 4]を入力すると誤った答えが出力される。(正:8, 誤:6)
これを解決するには、まだ選んでいない料理のおいしさの最大値を持てば良い。
が、それを確認するにはO(N)かかって辛いので、選んだ料理のおいしさの最大値を持つと良さそう。
選んだ料理のおいしさの最大値が小さい方が最後においしさが大きい料理を取れる。

あるいは、dpの情報を増やす代わりに、おいしさの小さい順にソートするのも良さそう。
こちらはあまり自信がないが、おいしさが小さい方から見るようにすれば、おいしさの合計値が同じ時に更新しなかった場合、おいしさが小さい料理が積極的に使われているはずである。
例えばおいしさ1,2,2,3,4,7からおいしさ7を作りたい場合、遷移をdp[i]=max(dp[i], dp[i-料理jの時間]+料理jのおいしさ)とする。
2を作る場合は、2のみ。
3を作る場合は1+2のみ。
4を作る場合は3+1が優先されるが、3には1が使われているので2+2。
5を作る場合は4+1が優先されて4+1。
6を作る場合は5+1が優先されるが、5には1が使われているので4+2を見るが、4には2が両方とも使われているので、3+4。
7を作る場合は、6+1が優先されるが、6には1が使われているので5+2を見るが、5には2が両方とも使われているので、4+3。
・・・とここまで書いて、使われているかどうかで優先されても選ばれないかもしれない可能性がありそうなので、うまく行かなさそうな感じがする。
ちょっとその辺の証明できるほどの実力はまだない。
素直に最大値持つことにする。
と言っても嘘解法でACしてしまっているので本当に正しいか分からない。
※正しくないです

F問題

ちょっと見たけど問題文の理解するよりE考えたほうが良さそうと思った。


初めて嘘解法って奴を通してしまった。
初の5完が嘘解法はちょっと嫌だなぁ。
実質4完である。
うまく行かないだろうなと気付いたものの、時間的に厳しそうでそのまま突っ走ってしまった。
Dの勘違いのタイムロスがなければ、最大値を持った正しい嘘解法はできてそう。

新ABC制覇してかなりコツ掴んできた感あったんだけどうまくいかないなぁ。
目下の目標は全体的な速度アップと間違った思い込みをなくすことだ。
今回嘘解法で不本意に緑になったが、その緑すら落とすようなことはないようにしたい。