cafelier@SRM

ACM-ICPC 2010 Tokyo Regional 問題F, G

その他 | 21:12 |

ACM-ICPC 2010 アジア地区予選 の問題FとGを解いてみたよ。

F

• 『素数 Q と、0-9 の数字が N 個並んだ列がある。その中で十進数として読んだら Q の倍数になる区間は何個？』
  • Q ≦ 1億
  • N ≦ 10万
• Q=3 で 12345 なら 12, 123, 12345, 234, 3, 345 の6個
• ゼロで始まる区間はカウントしません

• まず入力の最大サイズを見ると
  • O(N³) や O(NQ) や O(N²) の時間計算量では時間かかりすぎです
  • O(N) か O(N log N) か。

easy case

• とりあえず Q が 2 か 5 なら簡単で
• 「下一桁が0,2,4,6,8な区間を全部数える」や「下一桁が0,5な区間を全部数える」
• それだけですね。

int solve(const vector<int>& a, int Q)
{
   if( Q==2 || Q==5 )
      return easyCase(a, Q);
   else
      return hardCase(a, Q);
}

int easyCase(const vector<int>& a, int Q)
{
   int answer = 0;
   {
      int nonZero = 0;
      for(int i=0; i<a.size(); ++i)
      {
         nonZero += (a[i]!=0 ? 1 : 0);
         answer  += (a[i]%Q==0 ? nonZero : 0);
      }
   }
   return answer;
}

• Qの倍数を見かけたら、それより左にあったゼロじゃない桁の個数を足し合わせ。

hard case

• 問題は、Q が 2 でも 5 でもないとき。
• どうしましょう。問題を数式で整理すると
  • 10^k*a[i] + 10^k-1*a[i+1] + ... + 10¹*a[i+k-1] + a[i+k]
  • が Q の倍数になってるような i, k は全部で何個？
• でした。

• 10^k という余計なものが掛け算されてますが無視すると
• これは、a[i] + a[i+1] + ... + a[i+k-1] + a[i+k] という 配列の区間の和の話をしています。

• 区間和を扱うときにはよくでてくるアイデアがあって
  • b[0] = a[0]
  • b[1] = b[0] + a[1] (= a[0]+a[1])
  • b[2] = b[1] + a[2] (= a[0]+a[1]+a[2])
  • ...
• まず、こういう風に「端からの区間和」だけを全部求めておくと
  • a[i]+a[i+1]+...+a[i+k] = b[i+k] - b[i-1]
• あとは、どこでも好きな場所の区間和を引き算一発で求められます。

• これに似てるので、何か応用できないでしょうか。
• 問題には、単なる区間和ではなくて、
• 左にいくほど10が沢山かかった重み付け区間和が出てきているので
  • a[0], a[1], a[2], ..., a[N-2], a[N-1]
• これにとりあえず10を重みづけて掛けてみる。
  • 10^N-1*a[0], 10^N-2*a[1], 10^N-3*a[2], ..., 10*a[N-2], a[N-1]
• これにさっきの区間和計算を適用すると…？
• 欲しかった
  • 10^k*a[i] + 10^k-1*a[i+1] + ... + 10¹*a[i+k-1] + a[i+k]
• に
  • (10^k*a[i] + 10^k-1*a[i+1] + ... + 10¹*a[i+k-1] + a[i+k]) * 10^N-k-1
• 余計な 10^N-k-1 が掛け算された和なら、引き算一発で求まっちゃいます。

• 実はこれさえわかれば十分なのです。
• 「Q の倍数かどうか」しか気にしないので。
• Q が2でも5でもない素数なら、10を掛けても掛けなくても Qの倍数かどうかはかわりません！

• というわけで
  • a[] に 10 を重み付け掛け算
  • b[] = 区間和計算用の「端からの和」
  • b[i+k] - b[i-1] が Q の倍数になる i, k の組の個数を数える
• とやれば答えが求まります。
• 最後の組の個数を数える部分は2重ループすると時間が足りませんが、
• b[i] の値を Q で割った余りで分類してヒストグラム作っておけば1重ループで計算できます

int hardCase(const vector<int>& a, int Q)
{
   int answer = 0;
   {
      map<int,int> freq;
      freq[0] = 1;

      int base = 1, sum = 0;
      for(int i=a.size()-1; i>=0; --i)
      {
         sum  = (a[i]*base + sum) % Q;
         base = (base*10) % Q;

         if( a[i] != 0 )
            answer += freq[sum];
         freq[sum] ++;
      }
   }
   return answer;
}

• というのを１回のループに全部まとめると、こうなりました。

advanced case

• 実は
  • 『Q が素数とは限らない』
• という問題設定でも、解けます。
• easyCase と hardCase の合わせ技。お暇な方はチャレンジしてみては。

G

• 『「有向グラフの最短経路長を求めよ」という問題をコンテストで出題しようと思ったんだけど、テストデータをランダム生成したら、面白くない答えばっかりになってしまいました。"2010" や "42" や "6502" のような意味ありげな答えになるネタを仕込みたいです。頑張ろう。』
  • 入力は
    • 点数 100 以下、辺数 1000 以下の、辺に非負重みが乗った有向グラフ
    • その頂点 s と t
    • 目標の最短経路長 c
  • 出力は
    • sからtへの最短経路長をピッタリ c にするために書き換えなきゃ行けない辺の本数の最小値
  • 条件として
    • 「元々の最短経路長より c の方が小さい」場合しか来ないそうです。

• 「ピッタリ c」と考えると難しいですが
• 「最短経路長を c 以下にする」という目標だとどうでしょうか。
• そうすると、辺の長さを書き換える時は徹底的に短く変えた方がお得になるので
• 0 に変えるケースだけ考えればよくなります。

• というわけで
  • (頂点, 辺を0に変える操作を使った回数)
• を頂点にした拡大グラフで最短路を求めればよし。

typedef int vert, cost, modify;
typedef vector< vector< pair<vert,cost> > > graph;

modify dijkstra(const graph& G, cost Ct, vert Src, vert Dst)
{
   modify mMin = G.size();

   typedef pair<vert, modify>  state;
   typedef pair<cost, state> c_state;
   priority_queue< c_state, vector<c_state>, greater<c_state> > Q;
   set<state> V;

   Q.push( c_state(0, state(Src,0)) );
   while( !Q.empty() )
   {
      cost   c = Q.top().first;
      vert   v = Q.top().second.first;
      modify m = Q.top().second.second;
      Q.pop();

      if( c>Ct || m>mMin || V.count(state(v,m)) )
         continue;
      V.insert(state(v,m));

      if( v==Dst && c<=Ct )
         mMin = min(mMin, m);

      for(int i=0; i<G[v].size(); ++i)
      {
         vert u  = G[v][i].first;
         cost cc = G[v][i].second;
         c_state next[2] = {c_state(c+cc,state(u,m)), c_state(c,state(u,m+1))};
         for(int j=0; j<2; ++j)
            if( !V.count(next[j].second) )
               Q.push(next[j]);
      }
   }
   return mMin;
}

int main()
{
   fstream fin("G.in");
   for(int Nv,Ne,Ct; fin>>Nv>>Ne>>Ct,Nv|Ne|Ct; )
   {
      graph G(Nv);
      for(int i=0; i<Ne; ++i)
      {
         vert f,t;
         cost c;
         cin >> f >> t >> c;
         G[f-1].push_back( make_pair(t-1,c) );
      }
      cout << dijkstra(G, Ct, 0, Nv-1) << endl;
   }
}

• この実装よりも、
• 「書き換え回数が少ないノードを先に探索して、距離c以下でtに辿り着けたらそこで探索打ち切り」
• という方が多分効率的ですかね。

• 実はこれで問題は解けていて、
• というのは「最短経路長をc以下にできる」なら
• 減らしすぎた部分をちょびちょび増やしていけば必ず「ピッタリcにもできる」ので。
• 難しく言うと、最短経路長は辺の長さに関する連続関数なので、中間値の定理によりOKです。

advanced case

• 『c は元々の最短経路長より長い』とすると、どうなるでしょう。
  • 同じように「c 以上にする」と考えて、
  • 「辺の長さを∞に変えるパターンだけ」扱うのは同じなのですが
  • その先は…？
• 私も答えがわからないので、どなたかすごい人考えてみて下さい

• 追記: 投機的撃墜例。最適解は真ん中の2本変えればいいので2です。