◇◇CS Academy - Beta Round #6◇◇

https://csacademy.com/contest/beta-round-6/summary/

文字列$S$が与えられる。さらに$N$個の文字列が与えられるので、その中でいくつの文字列が$S$と似ているかを出力せよ。ただし、ある文字列$W$が$S$に似ているとは以下の条件のうちどれかを満たしていることをいう。

• $S$と$W$が等しい
• $S$は$W$を1文字変更することによって得られる。
• $S$は$W$に1文字追加することによって得られる。
• $S$は$W$から1文字削除することによって得られる。

$W$が$S$と一致しない場合、変更・追加・削除のどれである可能性があるかは文字数から判別できるので添字をずらすなどして愚直に一致を見れば各文字列に対してO($|S|$)。すべての文字列について判定しようとすると間に合わない可能性があるが、文字数が2以上違うものは無視できるため間に合う。

自力AC。最初編集距離を調べて1以内なら〜、と思ったが編集距離を直接求めるのはO($|S||W|$)のため無理だと気づくなどの手順を踏んだ。解説では最長共通prefixと最長共通suffixの文字数が使われていた。

直線上に$N$個のドミノが並んでおり、それぞれのドミノの座標が整数で与えられる。この状態からさらに$K$個のドミノを追加で並べて、連続な座標に並んでいるドミノの数を最大化したい。最大でいくつのドミノを連続な座標に並べられるかを出力せよ。

$N, K\leq 10^5$かつ元々のドミノが配置されている座標が$1\leq x \leq 10^6$と小さいので、単純な尺取りが可能である。座標を1から順にみて、ドミノを置いた/置いてあった座標をqueueにpushしながら自分で置いたドミノの数が$K$以下になるようにpopしていけばよい。queueのサイズの最大値が答えである。座標は$x=10^7$程度まで見れば充分。

自力AC。はじめ座標の制約が小さいことに気付いておらず、面倒だが尺取りでいけそうだなと思っていたところで制約に気付いて楽勝になった。

$N$要素の正数列が与えられ、この数列を使ってAlexとBenがゲームをする。ゲームはAlexのターンからスタートし、ターンプレイヤーは数列から好きな整数$x$をひとつ選んで削除する。その後、$x-1$以下の正整数を$x-1$個まで自由に追加できる(追加する整数はそれぞれ異なっていてもよい)。整数がすべてなくなった状態でターンが回ってきたプレイヤーが負けとなる。お互いに最適にプレイしたときどちらが勝つか出力せよ。

ターン開始時に盤面に奇数個ある数が存在するとき、そのような数のなかで最大のものを消し、他に奇数個存在する数をすべて1つずつ生成すればすべての数を偶数個にすることが可能である。一方、ターン開始時にすべての数が偶数個だった場合には操作のあと必ず奇数個の数が1つは存在することになる。ここで、ターン開始時にすべての数字が0個だったプレイヤーが負けであることから、常にすべての数が偶数個の状態で相手にターンを回し続ければ必ず勝つことができる。

以上のことから、初期盤面に奇数個の数が1つでもあれば先手の勝ち、そうでなければ後手の勝ちとなる。

解説AC。問題設定が明らかにNim likeなゲームなので、Nimでいうところの石の数のxorのように「操作によって変えないことができないもの」を探せばいいんだろうなということまでわかっていたが、それが「奇数個である数の数」であることに気づけなかった。

$N$行$M$列の行列が与えられ、行ごとにその要素を並べ替えることができる。すべての要素がその上下の要素と同じ値をもたないようにできるかどうかを判定し、可能であればそのような行列を、不可能であれば-1を出力せよ。

前提として、$i$行目の並びには$i-1$行目の並びしか関係なく、ある行の並びによってそれ以降の行が並べられなくなったりはしない。よって、各行について$i$行目と$i+1$行目の2行だけ取り出して、以下のような問題を考えてよい。

$M$要素の数列$A, B$について、$B$を並べ替えて任意の$i$について$A_i \neq B_i$となるようにせよ。

以下、上述の問題について考える。まず$A, B$あわせて合計で$M+1$個以上ある数字が存在すれば、どうやっても条件を満たすように並べることはできない。そうでなければ条件を満たすような並べ方が1つは存在する。

$A$と$B$から1要素ずつ取り出してペアにするとき、ペアが決まっていない要素だけを見たときに$M-1$要素の部分問題となっていることがわかる。このことから、ペアが決まっていない要素全体の半数を超える数字が存在しない状態を維持し続ければ必ず条件を満たすマッチングとなる。ここで、すべての数字が全体の半分以下となるようにするためには、$A$の要素のなかから$A, B$全体で最も多いもの$a$を選び、その下に$B$から選んだ適当な要素$b(\neq a)$をつけることを繰り返せばよい。$b$にしかない要素が全体の半分を超えることはないので、要素は常に$A$から選んでよい。

最初に$B$の要素をすべてstd::dequeに入れてソートしておくと、(うまくマッチングできている限り)dequeのfrontかbackのどちらかは必ず$a$でない要素になる。また、多い順に要素を取り出すためには残数の動的な管理が必要だが、std::priority_queueに($a, [1, num(a)]$)をすべて入れておき、各要素の残数を別で管理しておくことで擬似的に残数が多い順に取り出すことが可能である(2番目の数字が現在の残数より多いものが出てきたら捨てる)。

以上の要領ですべての行について操作を行えば、最終的に条件を満たす行列が出来上がる。

解説AC。第一印象では簡単だと思ったのだが、実際にはマッチングが思ったより自明ではなく、難しかった。

整数$K$が与えられる。(strictly increasingな)最長増加部分列をちょうど$K$個もつような100要素以下の数列をひとつ構築して出力せよ。

数字を昇順に並べたとき、そのLISの長さは並べた数字の種類数と同じであり、LISの数は各数字の個数をすべて掛け合わせたものになる。

よって、$N$を2進数で表したときの最大の桁が$n$桁目(0-indexed)であるとすると、各数字を2つずつペアにして$n+1$ペア並べることで$2^{n+1}$個のLISを作ることができる。

さらに、それらのペアどうしの間に別の数字を挟むことで$2^i$を表現できる。最後に数字を置いた場所を記録しておいて、$N$の2進数表示で$i$桁目が立っていれば$i$番目のペアの後ろに数字を挟み、そうでなければ最後に置いた場所にもう一つ数字を挟む。つまり、最初のいくつかのペアを経由したあと単体の数字のルートに移ることができるようにする。例として、$N=11,\;(1011)_2$であれば $$100,(1,1),101,102,(2,2),(3,3)$$ $N=18,\;(10010)_2$であれば $$(1,1),100,101,102,(2,2),(3,3),(4,4)$$ のようになる。単体の数字はそれらのみで昇順にする必要があり、すべてのペア数字より大きくなければならない(単体ルートに入ったあとペアルートに戻ることを防ぐため)。

解説AC。ほとんど解けていたのになぜか解けていないと勘違いして解説を見てしまったので悔しい。何かの数字を$N$にするような構築問題は2進数表示が鉄板な気がする。

$N$頂点$M$辺の重み付き無向グラフが与えられる。そのグラフ上にある閉路(単純閉路でなくてもよい)に属する辺の重みの総xorのなかで最大のものを出力せよ。ただし、グラフには多重辺や自己ループがあってもよい。

グラフ内の単純閉路および自己ループを列挙するには、頂点1からDFSをしながら頂点1から各頂点までをつなぐpathの総xorを保存しておき、backedgeを見つけたらその辺を含む単純閉路の総xorを記録していけばよい。

グラフ内の単純閉路/自己ループの任意の部分集合に対して、それを構成する単純閉路/自己ループをすべて通ることが可能である。なぜなら、頂点1からスタートして目的の単純閉路/自己ループを通り、来たときと同じ辺を通って頂点1まで戻ることができるからである。このとき、閉路の総xorは通った単純閉路/自己ループの総xorの総xorとなっている。

また、可能な閉路の総xorは、すべて単純閉路/自己ループの部分集合の総xorで表現できる。閉路に交差があればその頂点で2つの閉路に分解することができ、それを繰り返せばいずれば単純閉路/自己ループまで落とせるからである。

以上のことから、単純閉路/自己ループの数が$L$個であるとき、$L$要素の数列のなかから任意の部分集合を選んでその総xorを最大化する問題に言い換えることができた。部分集合の総xorの最大値は掃き出し法で求められるので、この問題が解ける。

解説AC。閉路が同じ辺を2度通って良いということを知らなかった。同じ辺を通らない閉路のことを閉道と呼ぶらしい。掃き出し法で部分集合の総xorを求める方法については、ABC141Fで見たので知っていた。

戻る