2022-10-06

GigaCode 2019 H 論理回路の構成満点解法

100点の提出がwriter含めて自分以外なかったので書いてます。考えてて楽しかったので、気になる人は問題からみてください。

問題のリンク

問題概要

真理値の変数が $(x_{1},x_{2},...,x_{N})$ と $N(\leq 10)$ 個ある。変数の組み合わせは $2^{N}$ 通りあるが、このうち入力で与えられる $K$ 通りの組み合わせを特別な組み合わせとする。

$\text{AND,OR,NOT,XOR}$ の論理ゲートを用いて、変数の組み合わせが特別なら $1$ をそうでないなら $0$ を返すような組み合わせ回路をできるだけ少ない数の論理ゲートを用いて作りなさい。

全てのテストケースに対して、ゲートの数が500以下で満点。

方針

数学的帰納法チックに考えます。ある $N=k$ について、正しく返す回路があったとします。この存在を用いて $N=k+1$ のときに正しく返す回路を作ることを考えます。

$K$ 個の組み合わせのうち、 $x_{k+1}=1$ であるような変数の組み合わせの $x_{k+1}$ を除いたもの集合を $S$ とします。

$k$ 個の変数を用いて $S$ に含まれているなら $1$ 、そうでないなら $0$ を返す回路は仮定より組めます。

この回路の返り値と $x_{k+1}$ を $\text{AND}$ ゲートに通せば $K$ 個のうち $x_{k+1}=1$ であるような変数の組み合わせに対してのみは $1$ を返すことができます。

$x_{k+1}=0$ である場合も、 $\text{NOT}$ ゲートを用いて同様に組むことができます。

ここで、 $N$ 個の変数に対して条件を満たす回路の論理ゲートの数を $f(N)$ とするとき、以下の漸化式が成り立ちます。

$f(N+1)=A+2f(N)$

$f(N+a)=A(2^{a}-1)+(2^{a})f(N)$

ただし、 $A$ はマージするのに必要なゲートの数で、上の図の場合だと $A=4$ です。

ここで、 $N=1$ のとき、２つの論理ゲートで目標を達成できることから $f(1)=2$ とすると、

$f(10)=A(2^{9}-1)+(2^{9})f(1)=3068$

となります。

上の式を見るとわかるのですが、この値は深さに対して指数的に増えるので、前計算をすることで、 $A$ の値や深さを改善していきます。

改善

まず、 $A$ の改善ですが、 $\text{NOT}$ を前計算するだけで、 $A=3$ となります。

次に深さの改善ですが、今回は前計算に $84$ 個のゲートを用いて、 $f(4)=3$ とします。

まず、 $2^{2^{2}}=16$ より、「$N=2$ のときの特別な変数の組み合わせ」の組み合わせは $16$ 通りあります。これを $16$ 個のゲートを用いて作ります。(ここの作り方は省略します。)

$(x_{3},x_{4})$の組み合わせは $4$ 通りあるので、 $4$ 個のゲートを使って、この２つの変数の真理値がある組み合わせの時にしか $1$ を返さないゲートを作り、$64$ 個の論理ゲートを用いて、「$N=4$ かつ、特別な変数の組み合わせの $(x_{3},x_{4})$ が $K$ 個全てで等しい」ときに答えを正しく出力するものを作ります。

このようにすると、$N=4$ のときは$4$ つの値を $\text{OR}$ でマージすることで、 $f(4)=3$ を達成できます。

以上の改善によって、

$f(10)=3(2^{6}-1)+3^{6}f(4)=381$

となります。前計算で使ったゲートの数が、 $10+84=94$ なので、全体で $475$ 個のゲートで題意を満たす回路を構成できます。

実装例

まとめ

公式解説にはマラソンによる改善や、特別な変数の組み合わせを減らすことによるゲート数の削減などがあり、この解法をベースにしてもっとゲートの数を減らせそうな気がします。

これを思いつくのは簡単ではなかったですが、満点が提出されていないのは意外でした。当時は放置されてたのかな...

2022-08-17

AGC058A - Make it Zigzag 解説

公式解説とは違うやり方で解いたので記しておきます。

問題へのリンク

問題の概要

順列 $p_{1},p_{2},...,p_{2N}$ が与えられるので、$N$ 回以下の隣接swapで以下の条件を満たすようにしなさい。

条件

$p_{1}<p_{2}>p_{3}<...>p_{2N-1}<p_{2N}$

解法

まず、一番大きい要素($2N$)の index は必ず偶数でなければいけません。

よって、もし奇数なら左右どちらか選んで swap させます。

これと同じようなことを繰り返します。

ちゃんと書くと、 $a=2N,2N-1,...,1$ の順に以下のことを繰り返します。

もし、今、 $a$ が存在するindex $i$ が奇数で、$p_{i-1}<a$ が成り立つなら $p_{i-1}$ と $p_{i}$ を swap する。成り立たないとき、 $p_{i+1}<a$ が成り立つなら、$p_{i+1}$ と $p_{i}$ を swap する。どちらも成り立たないなら swap をしない。

$i$ が偶数のときも何もしない。

各々の操作後に、 $a$ のindexが偶数なら、条件の式の中で、その両隣の符号は条件を満たします。また、奇数のindexの要素の値が増えたり、偶数のindexの要素の値が減ったりすることはないので、この操作を行なった後の列は条件を満たします。

また、操作の回数もindexが偶数のもの以下、つまり $N$ 以下になります。

実装例

2022-07-22

yukicoder No.2020 Sum of Common Prefix Length (yukicoder contest 353 G) 別解

公式解説ではクエリを全て受け取ってから前処理をしていますが、オンラインで解くことができます。

問題のリンク

問題概要

文字列が $N$ 個与えられるので、以下のクエリを $Q$ 回処理

クエリ1 : 文字列 $x$ の末尾に英小文字 $c$を加える

クエリ2 : $i=1,2,...,N$ に対して $S_{i}, S_{x}$ の最長共通接頭辞の長さを求め、それらの総和を答える。

クエリを先に受け取るときの解き方(ほぼ公式解説)

文字列の頭の部分が一緒といえば Trie木です(?)。

Trie木についてはこれとかこれとかをみてみましょう。

今回は通常の Trie木のノードごとにそのノード $p$ を通る文字列の数 $C_{p}$を記録しています。

すると答えは $S_{x}$ の末尾を表すノードから根っこのノード間にあるノードの $C_{p}$ の和となります。

公式解説ではクエリを先に全て受け取ることで、木上の一点加算とパス上の頂点の総和の問題に帰着しています。

別解

深さ $B$ で場合わけします。

まず、Trie木のノードごとにそのノード $p$ を通る全て文字列の index を記録した配列 $D_{p}$ を持ちます。また、長さ $N$ の配列 $base=(base_{1},...,base_{N})$ を用意します。(初期値は0)

$base_{x}$ というのは $S_{x}$ との最長共通接頭辞の長さが $B$ 以上の全てに対して文字列 $B$ 文字目以降で一致している文字数の総和です。

ある深さ $B$ より深いノードについてはそのノードに新しく文字列 $x$ が通過する際に($D_{p}$ に $x$ を追加する前に)以下の操作をします。

$D_{p}$ に含まれる全ての要素 $y$ に対して $base_{y}$ に1加算する。
$base_{x}$ に $|D_{p}|+1$ を加算する。

最初の文字列を追加する際やクエリ1を処理する際は以上の操作で十分です。

クエリ2を処理する際は以下のようにします。

まず、$ans=base_{x}$ とする。
文字列 $S_{x}$ の前 $B$ 文字が通っているノード $p$ について $ans$ に$|D_{p}|$ を加算する。

なぜ、これでいいのかというと、 $base_{x}$ というのは $B$ 文字目以降で一致している文字数の総和であるため、足りないのは $B$文字目より前で一致している文字数であるからです。

計算量

最初の文字列の長さの和を $M $ とします。

まず、クエリ2については一つ当たり $O(B)$ で処理することがでるので、全体で $O(QB)$ です。

文字を追加する操作ですが、一つ当たり最悪計算量が $O(N)$ なので、一見全体で $O((M+Q)N)$ のように見えますが違います。

例えば全ての文字列が深さ $B$ のノードを通るとき、 $N\times B \leq M+Q$ を満たす必要がありますが、これは $B$ が大きくなればなるほど困難になります。

自分の考察が間違っていなければ全体で $O(\frac{(M+Q)^2}{B})$ になるはずです。

よって、このアルゴリズム全体では計算量が $O(\frac{(M+Q)^2}{B}+QB)$ になります。

$B$ を適切な値にすることで十分高速に通ることができます。(テストケースにこの解法に強いものが存在しているのかは分かりません)

実装例

2022-07-04

AHC012 3位の参加記

TwitterでAHC012について調べている限りだと適当にグリッドの初期解を決めて焼きなましている人が多い印象を見受けられましたが、自分はDPだけで解いたのでその概要を示したいと思います。

問題のリンク

seed0の出力

最初の提出の方針

まず、イチゴをX座標の大きさでソートして適当なサイズ M (一番最初は M=15 で行った)に分けます。そのあと、イチゴをY座標の大きさでソート(Y座標が等しいならX座標の大きさ)して、このイチゴを分割することを考えます。

ここで、切り口 i を Y座標の大きさがi番目以下のイチゴとi番目より大きいイチゴを分断する切り口とします。

この分割の際にDPを行います。このDPの状態の持ち方は以下の通りです。

dp[i]...切り口iで切ったとき、その切り口よりY座標が小さい側だけを見たときの最善のスコアとその最善のスコアを達成する際の現在時点での配列$b$とこの切り口の一個前の切り口のindex

このdpの遷移は一個前の切り口のindexをjとすると、切り口iと切り口jの間に何個イチゴがのっているかを調べればいいです。

イメージとしては以下の図のようです。

イチゴの数は累積和を事前に求めておくことで $O(M)$で求めることができます。

jを全探索するとこのdpは全体で $O(N^2 M)$で求めることができます。

なお、スコア関数は問題のもののままではなく、(最終的には)以下のようになっています。

ll score(vector<int> &B){
    if(B[0]>K) return ILL;
    ll ans=0;
    for(ll i=1;i<=10;i++){
        if(A[i]<=B[i]) continue;
        ll tmp=(A[i]-B[i])*(A[i]-B[i]+1);
        tmp*=(ll)(INF);
        ans+=((i*4-1)*tmp)/A[i];
    }
    return ans;
}

$B[i]$ が1増えるごとにスコアが $(4i-1)\times \frac{A[i]-B[i]}{A[i]}$ 減るようになっています。

意図としては同じ個数イチゴがのったケーキが固まらないようにするため、特定の個数イチゴがのったケーキが極端に少なくなることがないようにするためです。

全体としての計算量は $O(N^2 M)$ であるため、TLEにならずに通ります。

本当の最初の実装はスコア関数があまり良くないもの((4i-1)の部分がないもの)でしたが、それでも90Mが出ました。

この方針の改善

直前の切り口を全探索していましたが、 $10M$ 個以上前の切り口を探索することはあまり効率が良くありません。なぜなら、11個以上イチゴがのったケーキが発生してしまうからです。

よって、jの探索範囲を狭めることでdpの計算量が $O(NM^2)$ へと改善されます。このことにより、 Mの値をいろいろな値で探索することができます。(最終的には 5~16 を全て調べました)

また、それでも実行時間に余裕があったため、最初のX座標で切り分ける際に等分にするのではなく、真ん中の部分に多めにイチゴがのるようにしたりなど様々な条件でdpをしました。

これらを全て実装したものを提出すると99.5Mが出ますが、コンテスト中の流れが以下のようだったので最終的な結果は99.3Mとなっています。

コンテスト中の流れ

~1:15

上記の方針を思いつき実装し提出する。(90M)

~1:30

M=15だけでなくM=10でも実行し、良い方を出力する。(92M)

~1:40

dpを高速化してMの値を色々変えて一番いいやつを出力する(93M)

~2:10

最初のX座標の分割の仕方を少し変えたものも試すようにする。(94.5M)

~3:00

スコア関数の$(4i-1)$の部分が今までなく、その部分を付け足すとスコアが劇的に良くなることに気がついたので、色々試してみる。(98.8M)

~3:50

X座標の分割方法のパターンを色々変えてみたりする(99M)

~4:00

dpが持つスコアを最後10%はなぜか真のスコアに変えていたので、それを5%にする(99.3M)

コンテスト後

dpが持つスコアを最後まで自作のスコアにする。また、スコア関数に余分な計算があって、正しく計算されていなかったので、それを修正する(99.5M)

感想

焼きなましとかできなくても問題によっては戦えるんだなと感じた。もしできたとしてもこれは局所解になってるだろうから改善できないだろうけど。あとMの値の候補を減らしてビームサーチみたいにたくさん状態を持ってdpをしたらスコアが改善されるのかなぁと感じている。

2022-06-21

ARC142D - Deterministic Placing 解説

公式の解説に具体例とかの図がなくて辛い人がいるかもしれないのと、自分が本番のときに紙面で木を作りまくって考察した痕跡を残すための記事です。

問題のリンク

条件を満たす配置とは

例えば以下の木に置かれたコマの配置は条件を満たします。この記事では黒マスをコマとして表現しています。

このコマの配置は1回操作をするたびに下の配置と行ったり来たりします。

この図のコマは左の3つのコマは左の4つの頂点を移動していて、右の2つのコマは右の3つの頂点を移動しています。なので、この木を２つのパス分解します。

具体的には以下のように分解します。

このパスは端点の一方にコマが置かれていないマスがあり、1回操作をするたびにその頂点が入れ替わります。 (コマが置かれていない頂点が端点でないとき、移動がそのパス内では不可能になるため)

もう1つ例を挙げます。以下のコマの配置も条件を満たします。

パスは以下のように分解されます。

このパス分解することが最終的に数え上げるときのベースになるのですが、パス分解ができるからといって条件を満たすわけではありません。

条件を満たすパス分解とは？

以下の配置を見てみましょう

この配置もさっきみたいにパス分解できそうです。

しかし、この配置は良い配置ではありません。なぜなら以下のように移動できるからです。

なぜうまくいっていないかというと、辺で隣り合っている端点のどちらもにコマが置いてある状態だと、本来移動できないはずの方向へ移動することができるからです。(下の図では真ん中の頂点が右に移動できてしまっています)

このような考察から、辺で隣り合っている別のパスの端点同士はどちらか一方のみに必ずコマが置いてある状態でなければなりません。

また、以下の置き方も良い置き方ではありません。

この実験からパスの端点でない頂点と別のパスの端点が辺で隣り合ってはいけないことがわかります。

以上のことを踏まえると辺でとなり合う異なる２つのパスは以下のいずれかが成り立っていないといけません。

コマが置かれている端点とコマが置かれていない端点が辺で結ばれている。
端点でない頂点同士が辺で結ばれている。

パスに対するコマの置き方の数は？

パスを決めたとき、そのパスに沿った良いコマの配置は何通りあるのでしょうか。以下のパスを参考にします。

パスが4つあるので $2^4$ 通り置けるのかというとそうではありません。例えば以下の配置は条件を満たしません。

これはなぜかというと、コマの置かれていな端点同士が結ばれているからです。

端点同士が結ばれている時はこのようにコマの置き方に制約が生じます。

一方、端点でない頂点同士が結ばれている時はそれらの間に制約が生じません。

以上の考察より、端点でない頂点同士が結ばれているパスでない辺の数を $a$ とおくと、コマの置き方は $2^{a+1}$ 通りあります。(この例だと a=1 なので 4通り)

木dp

ここまで考察できたら木dpでパスの置き方とその置き方に対するコマの数を数え上げます。

木の頂点の状態は以下の4つに場合分けします。

状態0 端点で、もう一方の端点はその頂点の子孫にある。

状態1 端点で、もう一方の端点はその頂点の子孫にない。

状態2 端点でない頂点で、端点のうち一方はその頂点の子孫の頂点で、もう一方は子孫でない頂点。

状態3 端点でない頂点で、そのパスの端点はどちらともその頂点の子孫である。

それぞれの状態の直属の子供は以下の条件を満たしている必要があります。

状態0

子供のうち、1つが状態1もしくは2で、その他の子供は0

状態1

全ての子供が0、もしくは、子供が存在しない。

状態2

子供のうち、1つが状態1もしくは2で、その他の子供は3

状態3

子供のうち、状態1もしくは2なものがちょうど2つ

状態3のときに、「パスに対するコマの置き方」のパートでの考察にあった通り、状態数を2倍します。

根の頂点が状態0だった時も2倍します。

あとはこれを実装するだけです。

実装例

終わりに

ここまで読んでくれてありがとうございます。思ったより長くなってしまいました。

この問題はAtCoder Problem上では新ARCのDの中で最難関のdiff2900↑でした。

しかし、個人的にはこの問題は天才パートもないし、難しい知識も必要ないし(木dp程度)、考察を丁寧にすれば実装もそんなに苦しくない問題です。

なのでdiffの割には取りやすい問題だと思っています。(多くの人が解けなくてこのdiffになっているのでそんなわけないだろ!という意見があって当然です)

頑張ってコンテスト中に解けるように精進頑張ろう!