[Atcoder] 無矛盾な単位系 / マス目と整数

無矛盾な単位系

概要

  • 無向グラフが与えられるので、誤った閉路がないかどうか判定せよ。なお点は文字列として与えられる。

方法

  • まだ訪れていない点を調べる。
    • 解 説 には深さ優先探索とありますが、実装が適切であれば幅優先探索でも大丈夫っぽいです。ただ、2倍ほど遅くなります。
    • memoに加えるのは、深さ優先探索では入れる時出す時のいずれでも良いですが、幅優先探索だと入れる時に加える必要があります。
    • 訪れていたら、最初に訪れた時の値と同じかどうか確認します。

  • なお、独立な単位系が複数存在するかもしれない(連結成分が1個ではないかもしれない)ので、グラフが空になるまで取り出し続ける実装にする必要がある。

  • コード(深さ優先探索と幅優先探索をベンチマークするためにdequeにしていますが、深さ優先探索だけで良いならvectorの方が速いです)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <string>
#include <cstdio>
#include <unordered_map>
#include <deque>
#include <algorithm>
using namespace std;
typedef string key;

char b1[99],b2[99];
void main2(int n){
  unordered_map<key,deque<pair<key,long long>>>m;
  for(;n;n--){
      int d;
      scanf(" 1 %s = 10^%d %s",b1,&d,b2);
      string s1=b1,s2=b2;
      m[s1].emplace_back(s2,d);
      m[s2].emplace_back(s1,-d);
  }
  for(;!m.empty();){
      auto s=m.begin()->first;
      deque<pair<key,long long>>st={ {s,0} };
      unordered_map<key,long long>memo={ {s,0} };
      for(;!st.empty();){
          auto p=*st.rbegin();st.pop_back();
          auto cur=p.first;long long d=p.second;
          for(auto &e:m[cur]){
              if(memo.find(e.first)==memo.end()){
                  st.emplace_back(e.first,d+e.second);
                  memo[e.first]=d+e.second;
              }else if(memo[e.first]!=d+e.second){
                  puts("No");
                  return;
              }
          }
      }
      for(auto &e:memo)m.erase(m.find(e.first));
  }
  puts("Yes");
}
int main(){int n;for(;~scanf("%d",&n)&&n;)main2(n);}

マス目と整数

  • 入力を変更し、連結成分重み判定を加えるだけで、マス目と整数の解答に変更することができる。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

--- utpc2010_10125(aizu2207)_stack.cpp    2016-10-13 04:19:40.000000000 +0900
+++ atcodercodefestival2016qualaD.cpp 2016-10-13 04:42:46.000000000 +0900
@@ -1,22 +1,22 @@
-#include <string>
 #include <cstdio>
 #include <unordered_map>
 #include <deque>
 #include <algorithm>
 using namespace std;
-typedef string key;
+typedef int key;

-char b1[99],b2[99];
-void main2(int n){
+int main(){
+  int r,c,n;
+  scanf("%d%d%d",&r,&c,&n);
  unordered_map<key,deque<pair<key,long long>>>m;
  for(;n;n--){
-      int d;
-      scanf(" 1 %s = 10^%d %s",b1,&d,b2);
-      string s1=b1,s2=b2;
-      m[s1].emplace_back(s2,d);
-      m[s2].emplace_back(s1,-d);
+      int s1,s2,d;
+      scanf("%d%d%d",&s1,&s2,&d);
+      m[s1].emplace_back(s2+r,d);
+      m[s2+r].emplace_back(s1,-d);
  }
  for(;!m.empty();){
+      long long a=-1LL<<61,b=1LL<<61;
      auto s=m.begin()->first;
      deque<pair<key,long long>>st={ {s,0} };
      unordered_map<key,long long>memo={ {s,0} };
@@ -29,12 +29,17 @@
                  memo[e.first]=d+e.second;
              }else if(memo[e.first]!=d+e.second){
                  puts("No");
-                  return;
+                  return 0;
              }
          }
+          if(cur<=r)a=max(a,d);
+          else b=min(b,d);
      }
+      if(a>b){
+          puts("No");
+          return 0;
+      }
      for(auto &e:memo)m.erase(m.find(e.first));
  }
  puts("Yes");
 }
-int main(){int n;for(;~scanf("%d",&n)&&n;)main2(n);}

あとがき

  • Code Festival 予選中、無矛盾な単位系が類似問題として頭に浮かんだのですが、当時書いていたコードが 一行入力するごとにグラフを全走査する くそコードだったため、どうしようもできませんでした。
  • 結果的には復習になってよかったです。
  • ただ、連結成分重み判定はやはり本番中に思いつかなかったと思います…