上の操作が行列の行基本変形に酷似していることに頑張って気付こう.
結果的にいえば, 1bit目が立っているものを調べてそのような要素(a_rank)がなければそのbitは無視し,あるならばその他の要素(a_i)をその要素とのxor (a_i ^= a_rank)にして消していくというのをやれば良い.
これはxorをmod2での加算と見て,bit方向を列と見たときのGaussの消去法に他ならない.
またxorは逆操作が可能なので {a} -> {b} という操作が可能か?という問題でなく, {a}, {b} を共に共通の標準形にできるか?という問題に言い換えることができる.
よって {a}, {b} に上の操作をして,等しくなればYes,そうでなければNoになる.

メモ

逆操作が可能なら共通要素に変換できるか?という問題になる
bitを列にして行列で捉える味方

コード

2018-10-02

Mujin Programming Challenge 2018 F - チーム分け(600)

DP 数え上げグループ分け AtCoder 競プロ

問題

解法

良解説を聞くのが良い

とりあえずsortして分布(c[x] := #( a_i=x なる i ) )をまとめておく
1人ずつグループに入れていこうとすると,分布(k人グループが何個できているか)を持たないといけないので状態が指数時間になって無理
視点を変えて,人数がk人であるようなグループを全て作っていく,というようなことを考える
昇順にやっていこうとすると,2人組を作るときにaの値が(2,3)をペアにするのと(2,4)をペアにするのは区別しないといけない
降順を考えると,x人のグループを作ろうとしているときにa_i>=xであるようなa_iは区別しなくていいことに気づけたら勝ち

def.
dp[i][j] := (i人以上のチームをすでに作っていて, i人チームを作るときに自由に使える人がj人残っている)
初期.
dp[N+1][0] = 1
遷移.
解説の通り
ans.
dp[1][0]

メモ

これむずいけど好き.
制約はゆるい方から決めて行った方がいいのかな

コード

2018-10-01

ARC 103 D - Robot Arms (600)

AtCoder 必要条件の列挙競プロ構築

問題

解法

sample2をじっと見ると,必要条件として

X_i, Y_i の和のパリティが全て一致する

というのがあることがわかる
パリティに注目するのはよくやるのでこれは気づかないとどうにもならない.

実際に,そのときdとして1を20個/21個用意すれば300点は取れる.
(例えば (-3,2) のとき LLLUU(UD)*8 )

このような構築ゲーで2冪に注目するのが定跡なことを念頭に置いて,
アームを 2⁰ , 2¹, 2² , ..と増やしていくことにしよう.
すると 2^k まで使ったときに, abs(x) + abs(y) <= 2^k+1 - 1 のひし形内の和が奇数の点を全て取れることがわかる.
abs(x),abs(y) < 2³⁰ - 1 だから, abs(x) + abs(y) < 2³¹ - 2 で k = 30としてやれば十分.
和がevenの時は 2⁰, 2⁰, 2¹, .. , 2³⁰ とすれば良い.
このようにすれば必ず構築できることもわかったので,列挙した必要条件が必要十分条件だったこともわかった.(よくあるパターン)

実際の構築に関しては 2^k のkが大きい方から決めていき,
abs(x+dx) + abs(y+dy) が0に近くなるようにしてやれば良い
そうしていけば最終的に(0,0)に一致することは上で確かめられている.

メモ

2冪は頭にあったけど実際に書いて見なかったのがよくなかった.

コード

2018-10-01

ARC 103 E - Tr/ee (700)

競プロ AtCoder 構築グラフ木構造必要条件の列挙

問題

解法

まず十分条件を列挙していく.
0-indexedとして,

s[0] = 1
s[N-1] = 1
s[i] = s[N-1-i]

D問題でもそうだったが,自明な必要条件が必要十分条件になっているというパターン.

s = "100..01.." として,k番目に初めて1が現れるとする.
このとき,1つの辺を切断することで現れる高さ2の部分木は,k-1個の子をもつものしか作れないことがわかる.
これをどんどんやっていくと,
k-1番目までで x_1 = 1, x_2, x_3, .. (1<=a_i<=k-1) の子が作れるとして,
次に1がk番目に現れたとする. このとき,
k-1 = a_1 * x_1 + a_2 * x_2 + .. とx_iの線形和でノードがk個(子要素がk-1個)の木を作ってやることが必要になる.
一瞬DPをしたくなるが, よく見れば a_1 = k-1, a_2 = a_3 = .. = 0 としてやって 1の子要素で数を合わせれば良いことがわかる.
実際そうすれば解説動画のように必ずその木が作れることがわかり, 列挙した必要条件が必要十分条件であることもわかる.

メモ

閃きゲーかと思ったけど,実際に考察ができて見るとただの論理的帰着な気もする..
構築ゲーに関しては最小単位で数合わせ+2冪を考えてみるのがテンプレかな.
今回からけんちょんさんのブログの書き方(タグ付けとか)がわかりやすいので真似していくことにした.

kurarrr's memooo

主に競プロ備忘録

square869120Contest #3 D - お土産購入計画2 / Souvenirs (600)

解法

メモ

コード

AGC 026 C - String Coloring

解法

メモ

コード

AGC 026 B - rng_10s

解法

メモ

コード

codeFlyer 2018 final D - 数列 XOR(600)

解法

メモ

コード

Mujin Programming Challenge 2018 F - チーム分け(600)

解法

メモ

コード

ARC 103 D - Robot Arms (600)

解法

メモ

コード

ARC 103 E - Tr/ee (700)

解法

メモ

コード