問題
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読んでみたいな。

問題
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の手法とか方針とかを定着させていきたい。

問題
ACコード
WAコード

#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) {
  string n;
  cin >> n;
  const int len = n.length();
  // dp[桁][3出た][5出た][7出た][nと一致][上位桁が全て0]
  int dp[11][2][2][2][2][2] = {0};
  dp[len][0][0][0][1][1] = 1;
  vector<int> num{3, 5, 7, 0};
  rrep (i, len) {
    int digit = n[len - i - 1] - '0';
    rep (j, 4) {
      vector<bool> next(4);
      next[j] = true;
      const int x = num[j];
      bool big = x > digit, same = x == digit;
      rep (a, 2) {
        rep (b, 2) {
          rep (c, 2) {
            rep (d, 2) {
              if (d && big) continue;
              rep (e, 2) {
                if (next[3] && !e) continue;
                int na = a | next[0];
                int nb = b | next[1];
                int nc = c | next[2];
                int nd = d & same;
                int ne = next[3];
                dp[i][na][nb][nc][nd][ne] += dp[i + 1][a][b][c][d][e];
              }
            }
          }
        }
      }
    }
  }
  int sum = 0;
  rep (i, 2) sum += dp[0][1][1][1][i][0];
  cout << sum << endl;
  return 0;
}

上から順番にやっているだけなのに桁DP強化月間みたいになってる。
そもそも想定解が桁DPではないが、いかにも桁DPできそうだったので・・・。
全探索の方はすぐに思いつかなかったが、桁DPを縛ったとしたら思いつけたかなぁ、微妙だ。

桁DPでやることを考えたら青くらいはあるんじゃないか？
そもそも桁DP自体が結構難易度高めで、桁DPというだけで水色以上レベルなのだと最近理解した。


今回の桁DPは最近得た知見を総動員しようと頑張ってみた。
前回の記事ABC117 D XXORの「桁DPは上の桁が全て0の場合、DPが初期値かどうかで遷移を変える」という知見も使おうと試行錯誤したのだが、全然うまくいかなかった。
やってみれば理由は明白で、0という数字が出てこないことを前提とした遷移をしているのに、上位桁が全て0の場合のみ0が出てくることが許されるためだ。
いわゆるLeading zero。
「このLeading zero内での遷移をLeading zero以外で0が出てきた場合の遷移と同様に扱えるか」、これが重要なのだと気付いた。
前回の初期値かどうかで遷移を変えるという部分も、初期値である=Leading zero内であるということなので、初期値を考えることの真髄はLeading zeroを考えることだったのだ。
これに気付けたので、DPの状態に「0以外の値が出てきたか」というのを持つことでACできた。

DPの遷移はABC138 F Coincidenceの経験を多いに生かした。
全ての遷移前を、ありえる可能性の回数(今回は0,3,5,7の4回)見て、条件によってcontinueしたり遷移先を変えたりする。
初見ではこんなDPできるか！と思ったものの、2回目の今回、問題のランクはかなり下がったとは言え、この書き方はかなり理にかなってるなと感じられた。
コード中の遷移ではあまり良くない部分でna~neを宣言しているが、今回やABC138Fのように遷移や条件が多い場合、速度や効率重視するより見やすさ大事にした方が良さそう。
dpの全ての状態と遷移は以下の通り。

dp[i][a][b][c][d][e] = dp[桁数][3を1度以上使った][5を1度以上使った][7を1度以上使った][今の所Nと一致][今の所0しか使っていない(Leading zero内かどうか)] = 何通りか
digit = Nのi桁目の数字
x = 遷移しようとしている数(0,3,5,7)

dp[i][na][nb][nc][nd][ne] += dp[i+1][a][b][c][d][e]の遷移を桁数×(0,3,5,7)の4回ループする。
1. x=0かつe=0なら、Leading zero外で0を選択することになるのでcontinue。
2. d=1かつdigit<xなら、Nを超えた遷移になってしまうのでcontinue。
3. x=3,5,7のとき、a,b,cのxに対応する部分を立ててそれ以外はそのまま(na, nb, nc)。
4. d=1かつdigit==xのときのみ、今の所Nと一致を継続できるのでnd=1、それ以外はnd=0。
5. Leading zero内を継続できるのは、今の所Leading zero内で遷移先が0のときのみである。
x=0の遷移が許されるのは1.の条件よりLeading zero内のみなので、x=0のときのみne=1。


ここから苦労話。

まず1番軽いところから。
さすがにDPの配列がここまで深くなるとvectorで書きたくないなぁとなって通常の配列を使ったのだが、普通の配列は0で初期化されないのである・・・。
ずっとvectorばかり使っていたらつい忘れてしまう。
値が明らかにおかしいと遷移を見てみると、オーバーフローのような値が出ていたので、配列外参照がないことを確かめた後、配列は0じゃないじゃんとすぐにたどり着けた。
学生時代に、「{}でも{0}でも初期化できるんだへー」と思ったのを思い出しながら{0]にしておいた。

i桁目の値をどう取り出すかがかなり大事だった。
最初文字列でやろうと思ったのだが、もともと数値なものを文字列に直してまた数値に直して計算するのはいかがなものかと。
10進数だから10で割って色々したらできるだろうとこの方針でやってみたらできたのだが、いかんせんややこしい。
初心に戻って文字列にしたらとても分かりやすい・・・。
さらに最上位の桁が既に分かっているので、NがLeading zeroということがなくなって遷移条件もすっきりできた。
Leading zero内かどうかを判断するために変な条件つけてミスったり、そこだけ抽出して遷移したがために肝心のDPの遷移が間違っていることに全然気付けなかったりと散々だった。
WAコードはこの方針でやっており、桁を取り出す部分やLeading zeroの判定部分は正しく行えているのだが、ACコードのほうが100倍分かりやすい。

もう1つ苦労したのが、テストケースを間違えて見ていたこと(?)。
この問題はテストケースが公開されているので、4つだけWAというところでテストケースを確かめに行ったのだが、間違えてDのテストケース(b16)を見ていた。
最近C問題で詰まるなんてことがなかったのでつい・・・。
他の人の解説のACコードもコードテストに貼り付けて確かめながらやっていたのだが、なんでこの遷移でだめなんだ・・・と、半ばやけくそでACコードにテストコードを貼り付けてみたところ、自分のコードと同じ結果を出したところでおや？となり気付いた。
試しにジャッジしてみたらあっさりAC。
何時間悩んだか。
運悪いことに、Dの入力も出力も同じような値だったのでぱっと見では気付けなかった。
解説も見たのに全然ACできなくて、理解が浅いのか実装をミスっているのか分からなくて何時間も悩み続けるこの感じ、最近は知識も実装力もついてきてほとんどなかったのだが久々に味わった。
もうちょっとで誰かこの桁DPを完成させてくれーーーと未解決問題として記事を書くところだった。


新ABC解き始めた頃、ほとんどテストケース公開されていないのがかなり辛い気持ちだったが、最近は公開されていてもテストケースはあまり見ないようにしている。
というのも、解説記事を見れば8割くらい正解のコードは書けるはずなので、そこからテストケースを見て答えが合うようにコードを弄るのは、意味も分からずパズルをかちゃかちゃして合わせているようであまり身になる気がしないからである。
見ないことに拘って時間を溶かすのも頭悪いが、見てさらに時間を溶かしたのは頭悪すぎる・・・。

問題
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 << 29;
constexpr lint   INFL = 1LL << 61;
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) {
  lint n, k;
  cin >> n >> k;
  vector<lint> a(n);
  rep (i, n) cin >> a[i];
  int limit = 1;
  while ((1LL << limit) < 1e12) ++limit;
  vector<int> digit_num(limit + 1);
  rep (i, n) {
    rep (j, limit + 1) {
      if (a[i] & (1LL << j)) ++digit_num[j];
    }
  }
  // inc[桁数][0or1] = 増加量
  vector<vector<lint>> inc(limit + 1, vector<lint>(2));
  rep (i, limit + 1) {
    inc[i][0] = (1LL << i) * digit_num[i];
    inc[i][1] = (1LL << i) * (n - digit_num[i]);
  }
  // dp[桁数][k以下が未確定or確定] = 合計
  vector<vector<lint>> dp(limit + 2, vector<lint>(2));
  rrep (i, limit + 1) {
    bool big = inc[i][0] < inc[i][1];
    if (dp[i + 1][1]) dp[i][1] = dp[i + 1][1] + inc[i][big];
    if (k & (1LL << i)) {
      dp[i][0] = dp[i + 1][0] + inc[i][1];
      dp[i][1] = max(dp[i][1], dp[i + 1][0] + inc[i][0]);
    } else {
      dp[i][0] = dp[i + 1][0] + inc[i][0];
    }
  }
  cout << max(dp[0][0], dp[0][1]) << endl;
  return 0;
}

自力で解けたものの実装が遅すぎる・・・！
大体こうやったら良いんだろうな、というのはわりとすぐに思い浮かんだものの、細部まで詰めて実装するのに時間がかかってしまった。

今回桁DPの状態で持つ桁数を、普通の数え方と同じく「下位からi桁目」にしてみた。
自分は桁DPするときは上の桁から見るので、前回桁DPを使った時は「上位からi桁目」としていたのだが、どちらが良いのだろう。
上位からの場合、仮定した最大桁数からi桁になってしまうので、実際のi桁目を取り出しづらいのがちょっと良くないが、遷移が直感的なのがちょっと良い。
下位からの場合、遷移の際に桁を足せば良いのか引けば良いのか少し分かりづらいのがちょっと良くないが、状態の桁数をそのまま実際の桁数に使えるのがちょっと良い。
前回上位からやったときは、i桁目を取り出す関数を作ったのだが、どうもスマートに感じなかったので今回は下位からやってみたのだが、やっぱり遷移の際に桁を足せば良いのか引けば良いのかに少し脳のリソースを取られるのが少し嫌だなぁ。
でもどちらかに明らかな優位性を感じるまではとりあえず下位からでやっていこうと思う。

本題に入って、基本的な方針は色々言った通り桁DP。
全てのAの各桁に1が現れる総数を数え、桁iを0と1にしたときのf(X)の増加量inc[桁][0or1]をそれぞれ計算する。
後は通常通り、今見ている桁と、K以下が確定しているかどうかを状態に持ち、その状態までの合計で桁DPを行いたかった。
しかし、K以下という条件を入れ込むのにかなり苦労した。
今回のように、i桁目が1の時のみ増加ではなく、i桁目が0でも増加する場合、値が0でも想定した最大桁数分の0が蓄積されてしまう。
これを解決するためには、桁をどこから始めれば良いんだろうと結構な時間考えた。
Kの値を最大桁数にしてしまうと、Aがそれ以上だった場合に正しく計算できないのは当然だ。
Aの値を最大桁数にしてしまうと、Kがそれ以上だった場合に、Aの最大桁数とKの最大桁数の間の蓄積されるべき0を計算することができない。

なんやかんやあって、サンプルケースのDPの遷移を観察することで大きく進展した。
最大桁数に依存するのではなく、DPの遷移をもっと詰めるべきだった。
直感的に理解したのでなかなか文章に起こすのが難しいが、K以下が確定した状態の遷移を考えることが正解の鍵だった。
Kを最大桁数limitから見ていき、桁iまで見た段階で未だ1が一度も出ていない(=Kの最大桁数より大きい)場合、dp[i~limit][1]が更新されることはない。
なぜなら全て0なのだから、K以下が確定することはないためである。
未更新であることはつまり、dp[i~limit][1]が初期値のままであることと同じなので、初期値であればK以下が確定した状態は更新しなければ良い。

自分がpの遷移を考える場合、適当に分かりやすい部分を選んで考えることが多い。
K以下が確定しているならi桁目の数は0でも1でも好きな方を選んで良く、これはKのi桁目の値に関係なく行えるから条件式は要らない、と当初考えた。
しかしこれだと、正しい「K以下が確定した場合の合計」ではなかった。
1度でもKの桁に1が現れた(=dp[i+1][1]が初期値ではない)を条件に加えることで正解にたどり着けた。

1つ前の記事ABC118 D Match Matchingでも初期値かどうかで遷移するかどうか決めており、実はこの時もこれに気づくのに時間がかかった。
今までの桁DPでは、桁の値が0の場合は遷移先に変更を行わないようなものがほとんど(全て？)で、ABC138 F CoincidenceのようにMSBも状態に持つのかと最初考えてしまった。
さすがに問題のレベルが違う気がするので考え直したが、KのMSBがまだなら遷移しないというのは部分的に同じだ。
桁の値が0の場合は遷移先に変化がないような桁DPでは、最大桁数より上の桁が0で埋められているため、「桁の値が0なら変更しない」という条件で、「初期値なら遷移しない」という条件も覆えているだけで、本来なら後者の条件も入れるべき(のはず)。
初期値なら遷移しない、というのはDP全般において重要だと感じるのでしっかり覚えておきたい。

YouTubeの解説も見てみたのだが、途中までは同じなのにやっぱり頭良さを感じた。
途中のincを計算するところまでは同じだが、その後。
ある桁を0にするか1にするかによる全体の変化量の違いは、それぞれの増加量ではなくその差となるので、上位の桁から貪欲にとは行かないのはかなり初期の段階で分かったが、その差を保持することで貪欲に求められるとは。
そもそも、初期を0として、「1にするかどうか」という視点の持ち方がなかった。
「0を選ぶか1を選ぶか」とは内容的は変わらないが、差を考えるとそうはいかない。
「良い方を選んだらその差だけ増える」と考えるのではなくて、「1にしたら正負もつけてその差だけ増減する」と考える。
初期が0なので、上位の桁から考えるとある時点でその後はどう選んでも良くなる。
どう選んでも良いなら差がプラスのものを全て選べば良いので貪欲に求められる。
桁DPのような「K以下かどうか」という考え方を活かしつつ貪欲といった感じだろうか。
頭良い。

桁DPの解説も少しだけあったので、K以下が確定した状態を0とするか1とするかも確認できた。
たぶんいつも「確定したら0」としていたのだが、今回桁数を下位からに変えたのも影響して(?)、確定したら0か1どっちにしようとなぜか悩んでにした。
悩んで決めたものは実装中に分からなくなって混乱しそうなのでコメントも残しておいた。
確定していない状況が特殊な分岐が必要になるのだから、やっぱり「確定したら0」が自然だよなぁ。
なぜ混乱したのか。