algorithm - ACM ICPC の解決 - SEERC 2009

Question

私はこれにほぼ1週間座っています。PDF形式の質問はこちらです。

これまでのところ、アイデアは 1 つしか思い浮かびませんでしたが、失敗しました。アイデアは、O(num_of_connected_subgraphs) で機能するすべての接続されたサブグラフを再帰的に作成することでしたが、それは遅すぎます。

誰かが私の方向性を教えてくれることに本当に感謝しています。唯一の方法は動的プログラミングだと思う傾向がありますが、その方法を理解できないようです。

Answer 1

OK、ここに私が思いついたアルゴリズムの概念的な説明があります:

1. 両方の次元で -7 から 7 までの (x,y) ボード マップの配列を形成し、その上に対戦相手のピースを配置します。

2. 最初の行 (Y 値が最も低い、-N) から始めます。

   • 列にある 2 番目のプレイヤーの駒の可能な組み合わせをすべて列挙し、対戦相手の駒と競合するものだけを除外します。

   • この行の組み合わせごとに: -- 接続されたピースを個別のネットワークにグループ化し、これらのネットワークに 1 から昇順に番号を付けます。

     -- 以下を使用して、行をベクターとしてエンコードします。

     = 0 for any unoccupied or opponent position
     = (1-8) for the network group that that piece/position is in.
     

     -- そのような各グループ化に 1 の COUNT を与え、エンコードされたベクトルをキーとして使用して辞書/ハッシュセットに追加します

3. 次に、後続の行ごとに、昇順 {y=y+1}:

   • 前の行の辞書のすべてのエントリについて:

     -- エントリにグループが 1 つだけある場合は、その COUNT を TOTAL に追加します。

     -- 現在の行にある 2 番目のプレイヤーの駒の可能な組み合わせをすべて列挙し、対戦相手の駒と競合するものだけを除外します。(変更:)このステップでは、最初の組み合わせ (すべてのエントリがゼロ) をスキップする必要があります。これは、上記のステップで実際にカバーされているためです。現在の行のそのような組み合わせごとに:

     + produce a grouping vector as described above
     
     + compare the current row's group-vector to the previous row's 
       group-vector from the dictionary:
     
         ++ if there are any group-*numbers* from the previous row's 
           vector that are not adjacent to any gorups in the current
           row's vector, *for at least one value of X*, then skip 
           to the next combination.
     
         ++ any groups for the current row that are adjacent to any
           groups of the previous row, acquire the lowest such group
           number
     
         ++ any groups for the current row that are not adjacent to 
           any groups of the previous row, are assigned an unused
           group number
     
     + Re-Normalize the group-number assignments for the current-row's
       combination (**) and encode the vector, giving it a COUNT equal 
       to the previous row-vector's COUNT
     
     + Add the current-row's vector to the dictionary for the current
       Row, using its encoded vector as the key.  If it already exists,
       then add it's COUNT to the COUNT for the pre-exising entry
     

4. 最後に、最後の行のディクショナリ内のすべてのエントリに対して:

   • エントリにグループが 1 つだけある場合は、その COUNT を TOTAL に追加します

---

**: 再正規化とは、グループ番号を再割り当てして、グループ化パターンの順列を排除することを意味します。具体的には、新しいグループ番号は、1 から始めて、左から右へ昇順で割り当てられる必要があることを意味します。たとえば、前の行にグループ化した後、グループ化ベクトルが次のようになったとします。

2 0 5 5 0 3 0 5 0 7 ...

この通常の形式に再マップする必要があります。

1 0 2 2 0 3 0 2 0 4 ...

この例のように、最初の行の後では、グループ化が不連続になる可能性があることに注意してください。この関係を維持する必要があるため、「5」の 2 つのグループは再正規化で同じ番号 (「2」) に再マッピングされます。

---

OK、いくつかのメモ：

A.このアプローチは正しいと思いますが、確かではありませんので、審査などが必要になることは間違いありません。

B. 長いですが、まだ大雑把です。個々のステップは、それ自体が重要です。

C. 個々の最適化の機会はたくさんありますが、全体的なアルゴリズムはまだかなり複雑です。これは総当たりよりもはるかに優れていますが、それでも、私のナプキンの概算では、N=7 に対して (2.5 から 10)*10^11 操作程度です。

したがって、おそらく扱いやすいですが、3 秒で 74 のケースを処理するにはまだほど遠いです。Peter de Revaz の回答の詳細をすべて読んだわけではありませんが、「ダイヤモンド」を回転させるという彼のアイデアは、私のアルゴリズムで実行できる可能性があります。内部ループの複雑さは増しますが、辞書のサイズ (したがって、比較するグループ化ベクトルの数) は 100 分の 1 になる可能性がありますが、実際に試してみないとわかりません。 .

---

ここには動的プログラミングがないことにも注意してください。それを活用する簡単な方法を思いつくことができなかったので、それはまだ改善の余地があるかもしれません.

OK、上記の (C) のより良い推定値を取得するために、考えられるすべての有効なグループ化ベクトルを列挙しました。これにより、N=7 に対して O(3.5*10^9) に低下しました。これははるかに優れていますが、それでも 3 秒で 74 個のテストを完了するためにおそらく必要となる量を 1 桁上回っています。それはテストにもよりますが、それらのほとんどがN = 7よりも小さい場合、それを作成できる可能性があります.

Answer 2

これは、この問題に対するアプローチの大まかなスケッチです。

最初に、格子点には |x|+|y| が必要であることに注意してください。< N。これにより、座標 0,6 から 6,0 までのダイアモンド シェイプが生成されます。つまり、各辺に 7 つのポイントがあります。

このひし形を 45 度回転させると想像すると、7*7 の正方格子が考えやすいかもしれません。（ただし、中6段の高台もありますが。）

たとえば、N=3 の場合、元の格子点は次のようになります。

..A..
.BCD.
EFGHI
.JKL.
..M..

どちらに回転するか

A   D   I
  C   H
B   G   L
  F   K
E   J   M

（おそらく回転した）ラティスで、最後の列が特定の文字列になるように最初のx列に軍を配置する方法の数を数える問題を動的プログラミングによって解決しようとします（さらに、いくつかのポイントまだ配置されています）。

文字列には、各ラティス ポイントの数字が含まれます。

0 represents an empty location
1 represents an isolated point
2 represents the first of a new connected group
3 represents an intermediate in a connected group
4 represents the last in an connected group

アルゴリズム中、文字列は複数の接続されたグループを含む形状を表すことができますが、孤立した接続されたグループを残す変換は拒否されます。

すべての列を配置したら、最大で 1 つの連結グループを持つ文字列のみをカウントする必要があります。

たとえば、以下の形状の最初の 5 列の文字列は次のとおりです。

....+  = 2
..+++  = 3
..+..  = 0
..+.+  = 1
..+..  = 0
..+++  = 3
..+++  = 4

中央の + は現在接続されていませんが、後の列で接続される可能性があるため、引き続き追跡する必要があります。(この図では、上/下/左/右の 4 連結性も想定しています。回転した格子は、実際には対角連結性を使用する必要がありますが、視覚化するのが少し難しく、それがまだ有効なアプローチであるかどうかは完全にはわかりません。この接続で。)

この回答が完全ではないことは承知していますが（さらに多くの写真/説明が必要になる可能性があります）、おそらく他の誰かがより完全な解決策を提供するように促すでしょう.