| |
A |
B |
C |
D |
E |
F |
| 問題文 |
■ |
■ |
■ |
■ |
■ |
■ |
| 自分の提出 |
■ |
■ |
■ |
■ |
■ |
■ |
| 結果 |
AC |
AC |
AC |
AC |
AC |
AC |
全体感想
睡眠を選んだため、0完でした。
コンテスト後に一通り改めて解きました。
最近、易化が続いていたような気がしていましたが、今回は最近の中ではやりごたえがありました。
とはいえ飛躍的も発想はほとんど必要なくて、 しっかり基礎力が問われているという印象。
問題C – HonestOrUnkind2
ABC-Cにしては入力の与えられ方がややこしくて、まずここがひとつの難所ですね。
全探索します。入力が、i → (x_i,y_i) の形になっていますが、結局、処理内容は全ての3つ組 $(i,x,y)$ に同じことをやっていくだけです。処理すべき条件は、1つの $(i,x,y)$ に対して
・「i が正直者ならば x は yである」
の形です。「$A\implies B$」の文書はプログラミング言語で表現しにくくて、「(not $A$) or $B$」つまり
・「(i は不親切) or (x は y)」
の形で扱うと簡潔です。各人の属性「正直 / 不親切」の組を全て探索する方法としては、
・itertools.product([0,1], repeat = N)
・itertools.combinations(range(N), K) （人数を決め打つ場合）
・range(2 ** N) （[0,1]の列を2進法表記により自然数としてエンコード）
などの方法があると思います。競プロで「bit〇〇」と呼ばれる手法と遭遇した場合、それはアルゴリズム手法というよりも、実装手法を指していることが多いです。bit演算が苦手ならば、まずはより分かりやすい方法で実装してみるのもよいのではないでしょうか。
問題D – Xor Sum 4
xor をとる組合せは $\binom{N}{2}$ 通りもあるので、何らかの形で計算をまとめる必要がありそうです。
ビット演算 and, or, xor, not の類はビット毎に独立の操作です。よって、ビットごとの問題に分割できます。特定桁のビットに注目した場合、数列 $A_1,A_2,\ldots$ は $0$ または $1$ の2値しかありません。
「0 または 1 の 2値が並んでいる数列 $A$ に対して、並び順に依らない計算を何かやってください」という問題が残っているだけなので、0 と 1 の個数という情報だけから答が出るはずで、あとはそれに基づく立式を出来ればよいです。
計算のボトルネックは、特定ビットの度数分布集計です。配列の全要素に対して、同様の並列処理を行うような場合は、numpyで簡潔に実装できることが期待できます。結構 numpy を使った提出数、多めでしょうか？こういう簡単なところから慣らしていくの、良いと思います。
問題E – Balanced Path
まず (赤の和) – (青の和) ですが、(赤 – 青) の和と同じことです。よって、AとBの差分だけ持っておけばよいです（パラメータが減ると、一般には考察も実装も楽になる）。
この問題はだいたい
「各地に落ちている $x$ を、$1$ 倍または $-1$ 倍の重みをつけて拾っていく。$0$ に近い和を作れ」
というものです。これに近い有名問題に、次があります。
ナップサック問題（？）の変種（？）
「自然数からなる $\{x_1,\ldots,x_n\}$ がある．部分集合で、$S$ に近い和を作れ．」
（※ ナップサックに分類されますかこれ？問題と命名の結びつきに関する理解が弱い…。）
自然数に 0 or 1倍の重みをつけて拾っていくとこうなりますね。この手の問題は上手く設定しないとNP完全問題になったりして、解ける場合には何らかの小さい範囲をとるパラメータに注目して探索するというのが典型手法です。具体的には、$x_i$ のとりうる値が小さいならば、どのような和集合を作れるかを dp 更新します（選べる部分集合の数は指数的に増えていくのに対して和のとりうるが 1 次式なので、これだけで探索空間の多くをまとめられていて、指数オーダーから多項式オーダーへ落ちる）。
例えば今回の問題が、2次元グリッドでなく1次元グリッドだったとすると、上述の問題とほぼ同様（実際には完全に対応がつく）なので、やはりどのような和が作れるかを dp 更新していくことが真っ先に思い浮かべるべき解決手段になるでしょう。
（※ 易しい場合を考えることで、どのような解法が妥当かどうかを推測できることがある）
というわけで、本問題は2次元グリッドの各セルに対して (作れる数の集合) を管理していく問題。
PythonだろうがC++だろうが、あとは典型問題をちゃんと勉強していればACを得ます。
※ ロジックは正しいのに TLE した人 → 過去問を埋めていって、TLEしなかったときでも自分より実行速度の良い人のコードを普段から見ていくだけで上達していくと思います。伸びしろ。
今回の問題で、bool 値の配列を用意して dp 更新をする場合、
・new_dp[n] |= old_dp[n-a] （ただし n = a, a+1, …, N-a-1）
というタイプの遷移を行うことになります。Pythonでこれを実装する場合には、
(1) bool値のnumpy.darrayを使って、
new_dp[a:N] |= old_dp[0:N-a] （提出：
■）
(2) bool値の列を多倍長整数にエンコードして、
new_dp |= (old_dp << a)というような方法が簡潔です。多倍長整数をビット列を見なすよりも、numpyの方が分かりやすいかと思います。
また、負のインデックスは上手く扱えないこともあり、適当にインデックスを水増ししておくとよいです。
問題F – Sum Difference
差分 $S-T$ を考えるのですが、$S$ だけでよいです（これはスルーしても解ける考察ですが、言い換えた方が楽になりますね）。これはむしろ逆の言い換えを用いることが多いと思います。
※ 「先手後手の2人ゲームをやる。各プレイヤは自身のスコアを最大化する。」ようなときに、差分を管理することで、先手と後手の戦略を共通化できることがある。
$N$ 項からなる数列で部分集合が $2^N$ 通りあり、大変です。しかし 2値 $X, D$ だけで書ける数列なので、そこに構造を見出していきましょう。
「$A_1,A_2,A_3,A_4,\ldots,A_N$」 と思うのではなく、「$X, X+D, X+2D, \ldots, X+(N-1)D$」と思った方が良さそうです。すると、部分和は自然と $aX + bD$ の形に書けると分かります（この時点で探索空間が非自明に小さくなっています）。
$a$ を固定すると、$b$ の候補は「$0,1,\ldots,N-1$ から $a$ 個選んだ和」全体を動きます。これは、$0 + \ldots + (a-1)$ から、$(N-a) + \cdots + (N-1)$ までの連続区間であることが分かります。このことは、（たとえば $N = 6, a=3$ として）
のように、最小の和から最大の和まで、1ずつ増加させながら変形できることから証明できます。（「最大の和」に到達した場合を除き、どれかを1増加させることが可能）。
各 $a$ に対する $b$ の分布が、連番になると分かりました。すると、作れる和の集合は、有限等差数列になると分かります。残タスクを整理すると、次のようになります。
問題：公差が $D$ の有限等差数列たちの和集合の元の個数を求めよ。
残タスクの主要部を定式化する思考法は、個人的に好き。
和集合の要素数を計算したいですが、もちろん重複が厄介です。今回は、公差が共通なので、$\pmod{D}$ で異なる数列同士の衝突はありません。そこで、$\pmod{D}$ で切り分けることで、次の問題に帰着できます。
問題：公差が $1$ の有限等差数列たちの和集合の元の個数を求めよ。
正直この課題だけでも、まだ初心者には厳しいとも思います（D～Eくらいありそう）が、易しい典型を一通り手持ちに出来ていれば、特に困らずに実装できるでしょう。
などにより、重複区間枚数ごとの区間長などを計算できます。
飛び切り難しいステップはなかったものの、正確な考察や典型を数段階積み重ねる形になっており、基礎力を問える良問という印象があります。
