競プロ日記

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