シコウノストレージ

自分自身の考えを整理するために書いています。

昨日のABC感想戦

A問題

XORの問題。

A ^ C = B → A ^ B = Cになるのでそのまま実装してAC。

 

B問題

ソートしてスコアの2番目を表示。

最初、上位から2番目と誤読していたがすぐ気づきAC。

 

C問題

wとhについて独立して考えればよいことに少し時間がかかったが気づいた。

しかし、実装うまくできずにWA14個。

この時点で考察があっているか確信がなかったのでとりあえずD問題へ。
結局戻ってこれず、WAのまま。

→答えを確認すると解法はあっていた。

解けた問題だけに、惜しかったでは終わらせられない。

問題点として実装の汚さがあると思う。

 

自分コード

  1. int main() {
  2. int h, w, n;
  3. cin >> h >> w >> n;
  4. vector<int> a(n), b(n);
  5. rep(i, n)cin >> a[i] >> b[i];
  6. //最初の値:変更後の値
  7. map<int, int> mh, mw;
  8. vector<int> aa=a, ab=b;
  9. rep(i, n) {
  10. mh[a[i]] = a[i];
  11. mw[b[i]] = b[i];
  12. }
  13. sort(all(a));
  14. sort(all(b));
  15. int starth = 0;
  16. int startw = 0;
  17. rep(i, n) {
  18.     mh[a[i]] -= (mh[a[i]] - starth-1);
  19.     mw[b[i]] -= (mw[b[i]] - startw-1);
  20.     starth = mh[a[i]];
  21.     startw = mw[b[i]];
  22. }
  23. rep(i, n) {
  24.     cout << mh[aa[i]] << " "<< mw[ab[i]] << endl;
  25. }
  26. }

これは元の順番の配列をソートしてしまったので急遽aa,abにソート前の順番でコピーして出力の際にだけ使っている。

これ自体は、出力の順番にしか使っていないしそこまで悪くないかなとは思う。

このコードで一番良くないと思うのが17行目からのコード。

特にmh[a[i]] -= mh[a[i]]-starth-1);が一目でわかりにくい。

そしてこの部分が間違っている。

内容としては、mapのmh,mwには{最初の数、最終的な値}として格納されており、小さい順にソートした上で、値の差分つまり何も書かれていないカードの部分を消した値を計算している。

しかしながらこれだと、11,12のような場合,11はうまく通過するが12の時に最後の値がstarthが1,mh[a[i]]が1であるため1 - 1 -1 でマイナスの値になってしまい結果的には1足される結果となり計算結果がずれてしまう。

 

もう一歩踏み込むには、なぜ計算結果がずれてしまうのかを考えなくてはならない。

まず、mhとmwは一緒の元考えていいのでmhの場合だけを考える。

mhは一次元座標ではないので11,12とhが同じであっても大丈夫だが上記の式の場合、次の場所に移るようになってしまう。

 

条件としては白い部分を消すつまりは、小さい順から考えて2個以上差があるなら詰める。しかし、0個1個の場合は詰めない。この場合の0個を考えられていなかったのが今回バグらせた原因。

 

解説コード

  1. //input---------------------------------------------
  2. //--------------------------------------------------
  3. //function------------------------------------------
  4. vector<int> compress(vector<int> a) {
  5. int n = a.size();
  6. map<int, int> mp;
  7. rep(i, n) mp[a[i]] = 0;
  8. int id = 1;
  9. for (auto& p : mp) p.second = id++;
  10. rep(i, n)a[i] = mp[a[i]];
  11. return a;
  12. }
  13. //--------------------------------------------------
  14. int main() {
  15. int h, w, n;
  16. cin >> h >> w >> n;
  17. vector<int> a(n), b(n);
  18. rep(i, n)cin >> a[i] >> b[i];
  19. a = compress(a);
  20. b = compress(b);
  21. rep(i, n)cout << a[i] << " " << b[i] << endl;
  22. }

解説コードは、compress(圧縮)という座標返還をする関数を作成している。

座標圧縮というアルゴリズムを使っているらしい。

この方法の方が同じコードを2回書く手間も省けるしミスが起こりにくい。

この問題において、2個以上差があるときだけ消すわけだからmapで小さい順にソートされていて同じマスは同じ移動で考えてよいわけだからその性質を利用して、mapの小さい順にインクリメントしていくというシンプルな実装になっている。

コードも短く、明らかにこちらの実装のほうが良い。

 

D問題。

C問題をいったん放置してD問題を見たが解法が思いつきそうだったので、実装することにした。

まず見たときにシミュレーションをやることを考えた。

方針としては、直接道路でつながっているということなのでその都市をBFSで求めて、スタックに入れていく。行ける道がないのならスタックを使って戻るような実装を考えた。

しかしながら実装していくうちにbfsといえどqueueは使う必要がないことに気づき消したり、行き当たりばったりのような実装になってしまったためバグらせてしまいACできず。。

 

この方針あっているような気はするが、TLE2つとWA11個でてしまい原因も不明なので解説の方針を使う。

 

解説ではオイラーツアーというアルゴリズムを使っている。

内容を見るとDFSの探索順に到達する頂点を出力することらしい。

今回の問題ほぼそのまま使えて、一つだけ小さい順に探索するという制約があるのでグラフを一回ソートしておく。

あとは再帰関数を使って潜るときと戻るときに引数をansに加えていけばよい。

  1. //input---------------------------------------------
  2. int n;
  3. vector<vector<int>>g;
  4. vector<int> ans;
  5. //--------------------------------------------------
  6. //function------------------------------------------
  7. void dfs(int v,int p = -1) {
  8. ans.push_back(v);
  9. for (auto nex : g[v]) {
  10. if (nex == p) continue;
  11. dfs(nex,v);
  12. ans.push_back(v);
  13. }
  14. }
  15. //--------------------------------------------------
  16. int main() {
  17. cin >> n;
  18. g.resize(n);
  19. rep(i, n-1) {
  20. int a, b;
  21. cin >> a >> b;
  22. --a, --b;
  23. g[a].push_back(b);
  24. g[b].push_back(a);
  25. }
  26. rep(i, n)sort(all(g[i]));
  27. dfs(0);
  28. for (int v : ans) cout << v + 1 << " ";
  29. }

この実装個人的にはやりたいが難しい部類で再起を再帰を親の頂点の場合に終了する処理がなかなか思いつかない気がする。

個人的にはused配列を用意してtureだったらcontinueで実装してしまうと思う。

それでもできるのでそれで良いともいえるがせっかくなので掘り下げてみておこうと思う。

まず初めに、問題文でn-1本の道かつすべての都市間は行き来できるとある(=連結グラフ)なので木であるということが分かる。

つまり閉路が存在しないので進み続けるといつかは行き止まりが存在する。

隣接リストの場合次に進む場所が親しかない場合、葉ということが分かる。

そのため、現在の頂点が親しかないような場合に再帰が終了することになる。

それ表現すると、

dfs(v,p)のVは現在の頂点でpが親の頂点。

親の頂点なので最初は-1で初期化。

nex == pの上限を満たすときcontinueで行き止まりと逆向きに探索することを防ぐ。

よってきれいに探索できるというわけだ。

 

今回は木なのでそれが適用できたが、閉路が存在するような場合においては先ほどのused配列で到達判定などをするる必要がある。