2021-01-17

キーエンスプログラミングコンテスト 2021参加記（～C問題）

競プロ解説参加記

300-400(1)-500-0(1)-0-0で1ペナ3完1200点。

A - Two Sequences 2

全ての組を見ると $O(N^2)$ かかりTLEする。
$c_n$ を求めるには、 $a_n, b_n$ までの要素を見ればよい。さらに $c_n$ を求める際、数列 $b$ から $b_n$ を選ぶか選ばないかで2通りに場合分けできる。

$b_n$ を選ばない場合

このとき、 $i\le j$ という制約から、 $a_n$ も選ぶことができない。つまりどちらの数列からも $n-1$ 番目までの要素から選ぶことになり、この答えは $c_{n-1}$ に一致する。

$b_n$ を選ぶ場合

このとき、 $a_1$ から $a_n$ までの要素のどれを選んでもよい。正の数同士の乗算なので、貪欲に最大値を選ぶのが最適である。

まとめると、 $a_1$ から $a_n$ までの要素の最大値を $a_{\max}$ とおいて、
$c_n=\max(a_{\max}\times b_n, \ c_{n-1})$
が答えとなる。一つ前の答えが必要なので前から順に計算していく。

計算量は、 $O(N)$ 。

数列 $a$ の中に、 $\{0, 1, 2, \dots , P\}$ があるときこれらをすべて使って $P+1$ 点を得られる。この時、 $P+1$ も $a$ の中に含まれているなら、 $\{0, 1, 2, \dots , P, P+1\}$ とすることで $P+2$ 点得られる。一般に、 $P$ 点得るには $P$ 個の数が必要なので、最高で $P$ 点得ることが可能なら貪欲に $P$ 個の数を使って $P$ 点得た方が良い。
あとは、数列 $a$ のなかにそれぞれの数が何個含まれているかをカウントし、数が大きい方から見て貪欲に作っていく。最高で $K$ 回までしか得点を得られないことに気を付ける（1WA）。

計算量は、 $O(N\log N)$ 。

C - Robot on Grid

全てのマスに文字が書き込まれているなら、 $O(HW)$ のDPで解くことができる。配るDPで書くと、
dp[i][j]:=(マス(i, j)に行く経路の数)
と定義して、マス(i, j)が右方向に進めるならdp[i][j+1]+=dp[i][j]とすればよい。下方向も同じくdp[i+1][j]+=dp[i][j]となる。最初のマス(1, 1)にいるロボットは $1$ 体なので、dp[1][1]=1である。

ここで、 $C=HW-K$ とおく（何も書かれていないマスの数を表す）。マスへの書き込み方は $3^C$ 通りあるので、マス(1, 1)に $3^C$ 体のロボットをおいて、すべてのロボットが異なる動きをすると仮定して考える。このとき、何も書かれていないマスに到達したロボットのうち、 $\dfrac{1}{3}$ は「R」、 $\dfrac{1}{3}$ は「D」、 $\dfrac{1}{3}$ は「X」であり、右に進めるのはマスに「R」か「X」が書かれていた場合のみである。よって、動的計画法の遷移は
dp[i][j+1]+=dp[i][j] * 2 / 3
となる。下に進む場合も同様である。計算時は、常にMODを取って計算することを忘れないようにする。また、割り算のMODは逆元を用いて計算できる。

計算量は、 $O(HW)$ 。

感想

パァン！

👺＜実装が遅い！

2021-01-11

AtCoder Beginner Contest 188参加記（～D問題）

競プロ解説参加記

100-200-300-0(2)-0(1)-0で0ペナ3完600点。

A - Three-Point Shot

$X$ と $Y$ のうち小さい方に $3$ を足して比較すると良い。もともとどちらが小さかったかを工夫して持つ必要がある。自分は、必ず $X>Y$ となるように適切にswapしてから問題を解いた。こうすると、もともと小さかった方は必ず $Y$ である、といえる。

計算量は、 $O(1)$ 。

B - Orthogonality

ベクトルとか内積とか、その辺の言葉を知らなくても問題文に定義が書いてあるのでそれをやるだけ。ただし、判定すべき式の左辺に「 $\dots$ 」が含まれているので、その辺の処理を工夫する必要がある。総和記号を使って書くと、
$\displaystyle \sum_{i=1}^N A_i\times B_i = 0$
の真偽を調べればよい。これは、for文などで実装できる。

足し算や掛け算が出てきたときは、数値のオーバーフローに気を付ける（最大値を考える）。今回の場合、最大値は $10^9$ なので、32bitのint型でも収まる。優しい…（伏線）

計算量は、 $O(N)$ 。

C - ABC Tournament

問題文が難しいシリーズ。要するに番号の小さい順に $2$ 人ずつマッチさせて戦わせ、勝ったほうだけ残せということ（最後の $2$ 人だけは負けた方を出力しなければならないが、勝った方の逆を出力するという解釈をすればよい）。これを愚直にシミュレーションしたときの計算量を考える。

$i(1\le i\le N)$ 回戦目では、 $j(1\le j\le 2^{N-i})$ ペアが試合を行う。一方が勝ってもう一方が負けるので、 $i+1$ 回戦目に出場する人数は $i$ 回戦目の $\dfrac{1}{2}$ となる。このとき、シミュレーションするために必要なメモリへの参照回数を計算すると
$\displaystyle \sum_{i=1}^N 2^{N-i} = 2^{N-1} + 2^{N-2} + \dots + 2^0 = 2N-1$
となる。よって、シミュレーションにかかる計算量は $O(N)$ であるので、シミュレーションするだけで時間内に答えが得られる。

ちなみに、公式解説の解法2には「選手の集合を前半と後半で2つに分けたとき、一番レートが高い選手と逆の集合にいる選手のうち一番レートが高い選手が答え」と書いてあった。トーナメント表を実際に書いてみると理解できる。こちらも、計算量は $O(N)$ と変わらないが、実装はかなり楽である。

D - Snuke Prime

問題文に明記されていないが、制約より $1$ 日目から $10^9$ 日目まで考えればよい（無限ではない）。

また、それぞれの日に関して、 $N$ 個あるサービスのうちどれを使うかはすでに決められていて、選べるのは「利用するすべてのサービスの利用料を普通に支払うか」「すぬけプライムで支払うか」の2択である。この選択は日ごとに独立で、最終的な支払金額を最小化したいので、この2択のうち安い方を貪欲に選べばよい。利用するすべてのサービスの利用料を普通に支払った場合の金額は、いもす法を使って効率的に求められる。

ただし1日ずつ考えていると時間が足りない。与えられる情報は高々 $N=2\times 10^5$ 個であることから、座標圧縮を用いることで計算量を $O(N)$ に落とすことができる。ただし、オーバーフローに注意する（「日数×サービス数×利用料」の最大値が $10^{23}$ となってしまう）。どちらの支払い方法でも、支払う日数は変わらないので、1日当たりの支払い金額で比較してから日数を掛ければよい。オーバーフローに気付かず、2WA。

計算量は、 $O(N)$ ではなく、座標圧縮するときにソートしているので $O(N\log N)$ ！！！

E - Peddler

町を頂点、道を辺としたグラフで考えると良さそう。あとはわからん。

F - +1-1x2

AGCで見た

感想

オーバーフローには気を付けよう！

2021-01-03

AtCoder Beginner Contest 187参加記（～E問題）

競プロ解説参加記

100-200-300-400(2)-0-0で2ペナ4完1000点。茶パフォ。
ちなみに、コンテスト後15分くらいでE問題を通した。コンテスト中に通せよ！！！

A - Large Digits

$A$ も $B$ も $3$ 桁であるので、 $3$ 桁の数としてではなく $3$ つの数字として入力を受け取ると処理が楽に書ける。各桁の数字を足して、大小比較をすればよい。ちゃっかり出力制約に $S(A)=S(B)$ のときは $S(A)$ を出力せよと書かれているが、 $S(A)$ も $S(B)$ も同じ値なので特に注意しなくてもACできる。（解説書いてて今気づいた）

計算量は、 $A, B$ がともに $N$ 桁の整数だったとして、 $O(N)$ 。

B - Gentle Pairs

とりあえず、 $1\le i\le j\le N$ を満たす整数の組 $(i, j)$ を列挙する。こういう条件が付いてるときの2重for文をスルスル書けるようになると楽。
それぞれの整数の組 $(i, j)$ に対して、「直線の傾き」の値を調べる。直線の傾きは $\dfrac{y_j - y_i}{x_j - x_i}$ で求められるので、この値が $-1$ 以上 $1$ 以下かどうか調べればよい。割り算するときは、

0除算していないか
演算結果は整数で持つのか小数で持つのか

あたりに気を付ければよい。今回は、0除算する可能性があるので、こういう例外は割り算する前に処理しておく。 $x_j - x_i=0$ ならば2点が縦に並んでいるということなので、傾きは無限大となる（条件を満たさない）。また、演算結果は小数で持つべきである。
以上のことに気を付けながら条件を満たす組をカウントする。

計算量は、 $O(N^2)$ 。

C - 1-SAT

不満な文字列 $T$ が存在するとしたら、与えられた $N$ 個の文字列のどれかに一致する。つまり、不満な文字列 $T$ の候補を一つずつ調べていき、実際にその文字列が不満な文字列の条件を満たすか調べればよい。ただし、候補は最大で $2\times 10^5$ 個あるため、判定は効率よく行う必要がある。
不満な文字列の候補 $T'$ に対し、 $T'$ の先頭に!を付けた文字列が、与えられた $N$ 個の文字列の中に含まれていれば、 $T'$ は不満な文字列である。ここで、文字列を辞書順でソートしておくことにより、文字列の集合に対しても二分探索が使えるので、この文字列の検索は一回あたり $O(|S_i|\log N)$ で判定できる。
あとは不満な文字列が見つかるまでループを回せばよい。

計算量は、 $O(|S_i|N\log N)$ 。

D - Choose Me

まず当然の話として、高橋氏が全く演説を行わなかった場合は必ず青木氏に負け、高橋氏がすべての町で演説を行った場合は必ず青木氏に勝つ。さらに、 $P$ 個の町を適切に選んで演説を行ったとき青木氏に勝てるなら、 $P+1$ 個の町で演説を行っても青木氏に勝てる。このことより、解の二分探索で解けそうだと目星を付ける。
問題は $P$ 個の町をどのように選ぶかであるが、これは「演説を行ったときの効率が良い」町から順に貪欲に選んでいけばよい。この、「効率の良さ」をどのように算出するかが重要である。
仮に町 $i$ で演説を行ったとすると、青木氏の得票数は $-A_i$ され、高橋氏の得票数は $+A_i+B_i$ されるので、両者の得票数の差は $2A_i+B_i$ 開くことになる。よって、各町を $2A_i+B_i$ で降順ソートして、先頭から順に演説すれば最善である。
$P$ 個の町で演説したときの実際の得票数を計算するのに、「 $1$ 番目から $P$ 番目までの青木派・高橋派のそれぞれの有権者数」を使うが、これは累積和を使うことで高速に求められる。よって一回の判定は $O(1)$ でできる。

計算量について、ソートに $O(N\log N)$ 、累積和を求めるための前計算に $O(N)$ 、解の二分探索に $O(\log N)$ かかる。よって、全体では $O(N\log N)$ の計算量となる。

ソートするための基準を適当に決めて2WA。罠にまんまと引っかかった。

E - Through Path

初めに少しだけ愚痴。問題文に書かれているクエリの説明が簡素すぎだと思う。せめて $e_i$ が辺番号を示しているということは明記してほしかった。
愚直に毎クエリごとに木を走査して頂点を更新していくと間に合わないので、最後に木の根から走査して動的計画法で更新することを考える。
クエリを読み解くと、スタート地点となる頂点と通ってはいけない頂点は必ず1本の辺で繋がっていることがわかる。よって、木の根を適当に決めたとき、スタート地点から到達できる部分木に根が含まれているパターンと含まれていないパターンの2つに分類できる。
木の根が部分木に含まれるとき、木の根に $+x_i$ する。ただし、走査しているときに辺 $i$ を通過したら $-x_i$ して打ち消す。
木の根が部分木に含まれないとき、はじめは木の根に何も足さない。操作しているときに辺 $i$ を通過したら、そこからスタート地点となる頂点を含む部分木なので、 $+x_i$ する。
こうすることで、1回の走査だけですべての頂点の値を更新することができる。

計算量は、 $O(N)$ 。

F - Close Group

読んでない

感想

成績は散々だったけど、考察の大まかな方針は間違えていなかったのでそこは評価したい。もっと考察力を上げるにはやっぱり精進するしかないのかな…。

2020-12-20

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）参加記（～E問題）

競プロ解説参加記

100-200-300(1)-400-500-0で1ペナ5完1500点。

A - Brick

割り算の問題で、 $\dfrac{N}{W}$ の商が答えとなる。余りは切り捨ててよい。

計算量は、 $O(1)$ 。

B - Blocks on Grid

ブロックに対してできる操作は、「ブロックを取り除く」のみである。この操作でブロックの個数が増えることはないので、操作後のブロックの個数はすべてのマスの中で一番少ないものに合わせる必要がある。
よって、マス目を全探索してブロックの個数の最小値 $A_{min}$ を保持し、各マスにあるブロックの個数 $A_{i, j}$ と $A_{min}$ の差の総和を求めればよい。

計算量は、 $O(HW)$ 。

C - Unlucky 7

公式解説とは違うオーバーキル気味な方法で通した。

前計算として、「 $10$ 進数で表すと $7$ を含む」「 $8$ 進数で表すと $7$ を含む」数を列挙する。再帰関数で幅優先探索を実装し、 $7$ が含まれる数のみを配列に放り込んでsort->unique->eraseすると、 $7$ を含む数が昇順で並ぶ。あとは与えられた $N$ 以下の数の個数を、配列の二分探索を用いて求めればよい。

計算量ってどれくらいなんだろう？幅優先探索で生成されるノードの数は $10$ 進数の場合 $111111$ 個なんだけど、これを数式で $N$ を使ってきれいに書けないな…。 $O(N)$ くらいということにしておく。
[追記]ソートしているので計算量は $O(N\log N)$ でした。ソートの存在忘れがち

A進数をB進数に変換する関数を暇なときに組もうと思った（暇なときにやる気が起きるはずがないので永遠に実装されない）。

D - Sum of difference

絶対値記号が邪魔なので配列をソートして考える。さらに引かれる数と引く数ごとにわけて考えると、それぞれの整数が足される回数は配列の添え字番号に依存していることがわかる。
具体的には、
$\displaystyle \sum_{i=1}^n \{A_i\times i\} - \displaystyle \sum_{i=1}^n \{A_i\times (N-i)\}$
が答え。

計算量は、 $O(N)$ 。

E - Throne

拡張ユークリッドの互除法で解いた。

玉座を $0$ 番目の椅子と考えると、
$S+Ki \equiv 0 \pmod N$
を満たす最小の $i$ が解となる。少し変形すると
$Ki \equiv N-S \pmod N$
となる。これは、拡張ユークリッドの互除法を用いて
$Kx+Ny=N-S$
を満たす $x$ を求める問題に落とせる。

計算量は、 $O(T\log N)$ 。

F - Rook on Grid

解けなかった。縦→横と動くパターンと、横→縦と動くパターンで分けて考えた後重複するマスを引く方針で考えたが、上手くいかずタイムアップ。もっと形式的にできるっぽい。

感想

C問題とE問題を解くのが遅かった。特にC問題は単純実装でも通る問題だったので、オーバーキル解法をゴリゴリ実装する前にもっと簡単に記述できる解法はないか考えるべきだった。

2020-12-10

積の魔方陣は構成できるか？

※この記事は苫小牧高専アドベントカレンダー2020 10日目の記事です。

adventar.org

9日目の記事はまだ上がっていないようです。高専という感じがして好きですよ。

というわけで10日目はみみねこが担当します。Twitterをやっているので是非フォローしてください。
→みみねこ (@3_3_nk) | Twitter

高専といえば勉強ですね！勉強といえば数学！というわけで今日は数学の話をします。

はじめに：魔方陣とは
積魔方陣を定義する
和魔方陣から積魔方陣を構成する
サイズの小さい積魔方陣を構成したい
素因数が2つ存在する積魔方陣
ラテン方陣とオイラー方陣について
各要素が互いに素な集合を探す
他の次元の積魔方陣も構成してみる
結論
課題

はじめに：魔方陣とは

魔方陣って知ってますか？知らない人はWikipediaを読んでください。

魔方陣 - Wikipedia

簡単に言うと、異なる数字を正方形状に並べたとき、その各行・各列（・各対角線）の和がそれぞれ等しくなるようなものを魔方陣といいます。縦横にそれぞれ $N$ 個の正整数が並んでいる魔方陣を $N$ 次魔方陣と呼ぶことにします。
$3$ 次魔方陣は次のようなものが考えられます。縦横に並ぶ数の合計はどこも $15$ となっていますね。

$\begin{bmatrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{bmatrix}$

ところで、 $3$ 次以上の魔方陣は存在することが証明されています。では、魔方陣の積バージョンは存在するでしょうか？

積魔方陣を定義する

$N$ 次の積魔方陣を次のように定義します。

$N$ 次積魔方陣は、縦横にそれぞれ $N$ 個の正整数が並ぶ方陣である
どの2つの数も異なる
各行・各列の積がそれぞれ等しい

これらの条件をすべて満たす積魔方陣を構成してみましょう。

和魔方陣から積魔方陣を構成する

最初に説明した魔方陣を「和魔方陣」と呼ぶことにします。
実は、 $N$ 次の和魔方陣が一つ求まっていれば、そこから $N$ 次の積魔方陣を構成することができます。とりあえず構成アルゴリズムを示します。

元となる和魔方陣の各要素を $a$ としたとき、各要素を $a\to 2^a$ と置き換える

$3$ 次積魔方陣の構成方法を具体的に示すとこうです。

$\begin{bmatrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{bmatrix} \to \begin{bmatrix} 2^8 & 2^1 & 2^6 \\ 2^3 & 2^5 & 2^7 \\ 2^4 & 2^9 & 2^2 \end{bmatrix} = \begin{bmatrix} 256 & 2 & 64 \\ 8 & 32 & 128 \\ 16 & 512 & 4 \end{bmatrix}$

なぜこの方法で積魔方陣が構成できるかは一目瞭然ですね。 $2$ のべき乗の掛け算は、指数部分の足し算として計算できるからです。

以上より、この方法を使えば「 $3$ 次以上の積魔方陣は存在し、実際に和魔方陣から積魔方陣を構成できる」ということが証明できました！「積の魔方陣は構成できるか？」というタイトルは回収したので、これ以降は数学が好きな人だけ見てください。

サイズの小さい積魔方陣を構成したい

先ほどの方法ならいくらでも積の魔方陣を生成できます。しかし $2$ のべき乗しか使えないので、積魔方陣の次数が増えていくほど使われる整数もどんどん大きくなっていきます。もっと"サイズの小さい"積の魔方陣はないか、考えてみましょう。

ここで、魔方陣の大きさを比較するために「積の魔方陣のサイズ」をある一列の数の総積で定義します。たとえば、先ほどの方法で生成した $3$ 次の積魔方陣のサイズは $32768$ となります。このサイズがより小さくなるような積魔方陣を構成したいです。すぐに思いつくのは、すべての要素を $2$ で割る方法です。

$\begin{bmatrix} 256 & 2 & 64 \\ 8 & 32 & 128 \\ 16 & 512 & 4 \end{bmatrix} \to \begin{bmatrix} 128 & 1 & 32 \\ 4 & 16 & 64 \\ 8 & 256 & 2 \end{bmatrix}$

この場合サイズは $4096$ となりますが、まだまだ小さくなりそうです。もっと別のアプローチで積魔方陣を構成できないでしょうか？

素因数が2つ存在する積魔方陣

積魔方陣は整数の掛け算に関する問題なので、各要素を素因数分解して考えるとよさそうです。先ほどまでの方法だと各要素の素因数は $2$ だけでしたが、それ以外の素因数が含まれる場合を考えてみます。

積魔方陣に素因数が2種類含まれる場合、それぞれの素因数は互いに素なので、その素因数ごとに積の魔方陣を分解できます。たとえば、各要素が $2^x\times3^y$ と表せる積の魔方陣が存在すると仮定すると、各要素が $2^x$ である積魔方陣と $3^y$ である積魔方陣に分解して考えることができます。分解した後の積魔方陣は「どの2つの数も異なる」という条件を満たしていなくても構いません（合成した後に条件を満たしていれば十分）。条件が緩いので、分解してできる二つの積魔方陣のことは「準積魔方陣」と呼び分けることにしましょう。

素因数が1種類だけの積魔方陣の生成方法は先ほど説明しました。これを使って、実際に $2^x\times 3^y$ 型の $3$ 次積魔方陣を一つ構成してみましょう。

作成したい積魔方陣には $9$ 種類の相異なる正整数が必要です。 $2^x$ 型の準積魔方陣と $3^y$ 型の準積魔方陣に登場する正整数の種類をそれぞれ $3$ 種類ずつとすると、二つの準積魔方陣をうまく組み合わせることで合成後の積魔方陣に $9$ 種類の相異なる正整数を生成することが可能です。（行列の掛け算と違って、単純に同じ位置にある要素同士を掛け合わせています。）

$\begin{bmatrix} 2^0 & 2^1 & 2^2 \\ 2^1 & 2^2 & 2^0 \\ 2^2 & 2^0 & 2^1 \end{bmatrix} \times \begin{bmatrix} 3^0 & 3^1 & 3^2 \\ 3^2 & 3^0 & 3^1 \\ 3^1 & 3^2 & 3^0 \end{bmatrix} = \begin{bmatrix} 2^0 3^0 & 2^1 3^1 & 2^2 3^3 \\ 2^1 3^2 & 2^2 3^0 & 2^0 3^1 \\ 2^2 3^1 & 2^0 3^2 & 2^1 3^0 \end{bmatrix}$

ちょっと見づらいので、指数部分だけ抜き出して書いてみます。数字の並びがうまくずれているおかげで、合成後の指数の組に重複が無いというところに注目してみてください。

$\begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \\ 1 & 2 & 0 \end{bmatrix} = \begin{bmatrix} (0, 0) & (1, 1) & (2, 2) \\ (1, 2) & (2, 0) & (0, 1) \\ (2, 1) & (0, 2) & (1, 0) \end{bmatrix}$

この方法で生成された積魔方陣は以下の通りで、そのサイズは $216$ となります。

$\begin{bmatrix} 1 & 6 & 36 \\ 18 & 4 & 3 \\ 12 & 9 & 2 \end{bmatrix}$

初めに生成したものと比べると、だいぶサイズが小さくなってきました！見た目もシンプルになってきましたね。ただ、 $2$ のべき乗と $3$ のべき乗しか使用していないので、積魔方陣の次数 $N$ が大きくなるとやはり指数的にサイズが大きくなってしまいます。どうやら、もっとサイズを小さくできそうですので、もう少し議論を続けることにしましょう。

ラテン方陣とオイラー 方陣について

先ほどの方法で出てきた「二つの準積魔方陣を"うまく"組み合わせる」というあいまいな部分を少し詳しく見てみましょう。

合成する前の準積魔方陣のうち、指数部分のみを抜き出してできる方陣のような、「 $0$ から $N-1$ までの整数が各列・各行に重複なく並ぶ」方陣のことをラテン方陣といいます。

ラテン方陣の例： $\begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{bmatrix} , \begin{bmatrix} 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 0 \\ 2 & 3 & 0 & 1 \\ 3 & 0 & 1 & 2 \end{bmatrix}$ など

また、ラテン方陣を二つ合成して、各要素が整数のペアであるような方陣を作ります。このとき、どの $2$ 要素も異なるようなものをオイラー方陣といいます。

オイラー方陣の例： $\begin{bmatrix} (0, 0) & (1, 1) & (2, 2) \\ (1, 2) & (2, 0) & (0, 1) \\ (2, 1) & (0, 2) & (1, 0) \end{bmatrix} , \begin{bmatrix} (0, 0) & (1, 1) & (2, 2) & (3, 3) \\ (1, 2) & (0, 3) & (3, 0) & (2, 1) \\ (2, 3) & (3, 2) & (0, 1) & (1, 0) \\ (3, 1) & (2, 0) & (1, 3) & (0, 2) \end{bmatrix}$ など

ここで、先ほどまでの議論より、ある正整数 $N$ に対して $N$ 次のオイラー方陣が存在すれば、サイズの小さい $N$ 次の積魔方陣を構成できると言えます。

話がそれるので証明や具体的な構成方法は省きますが、 $N=2, 6$ の時を除いて $N$ 次のオイラー方陣が存在することがわかっています。つまり、 $2$ 次と $6$ 次以外の積魔方陣は、オイラー方陣を用いる方法で構成することができるのです*1！

各要素が互いに素な集合を探す

ところで、合成する前の二つの準積魔方陣の各要素は、それぞれ $2^x$ 型と $3^y$ 型でした。このように異なる素因数で分解した理由は、二つの準積魔方陣の要素を掛け合わせた結果がすべて異なるように設定したからでしたね。つまり、二つの準積魔方陣に登場するどの2要素を取ってきても、互いに素になるように設定したということが言えます。

ここで、二つの準積魔方陣を $A, B$ と名付け、それぞれの $N$ 次準積魔方陣に登場する要素の集合を $a, b$ とします。集合 $a, b$ の要素数は $N$ に等しくなります。

例を挙げましょう。 $3$ 次の二つの準積魔方陣 $A, B$ を

$A=\begin{bmatrix} 2^0 & 2^1 & 2^2 \\ 2^1 & 2^2 & 2^0 \\ 2^2 & 2^0 & 2^1 \end{bmatrix}$

$B=\begin{bmatrix} 3^0 & 3^1 & 3^2 \\ 3^2 & 3^0 & 3^1 \\ 3^1 & 3^2 & 3^0 \end{bmatrix}$

と定義すると、準積魔方陣の各要素の集合 $a, b$ は以下のようになります。
$a=\{1, 2, 4\}$
$b=\{1, 3, 9\}$

確かに、集合 $a$ の要素と集合 $b$ の要素は互いに素であることがわかります。さらに、準積魔方陣 $A, B$ を合成してできる積魔方陣のサイズは、集合 $a, b$ の要素の総積と等しくなります（いままでの図を見れば理解できるはずです）。つまり、集合 $a, b$ の要素である正整数の値が小さくなればなるほど、完成する積魔方陣のサイズも小さくなるということです。

ここで、二つの集合の要素を眺めてみると、集合 $b$ の要素のうち $9$ が比較的大きいことに気が付きます。集合 $a$ の全要素と互いに素となる正整数のうち、まだ使われていない最小のものは $5$ です。なんと、集合 $b$ の要素を $9\to 5$ と置換しても、積魔方陣が正しく構成でき、サイズを小さくすることが可能です！

$a=\{1, 2, 4\}$
$b=\{1, 3, 5\}$

$A=\begin{bmatrix} 1 & 2 & 4 \\ 2 & 4 & 1 \\ 4 & 1 & 2 \end{bmatrix}$

$B=\begin{bmatrix} 1 & 3 & 5 \\ 5 & 1 & 3 \\ 3 & 5 & 1 \end{bmatrix}$

この方法で生成された積魔方陣は以下の通りとなります。サイズは $120$ で、先ほどの積魔方陣よりさらにサイズが小さくなっていることがわかります！

$\begin{bmatrix} 1 & 6 & 20 \\ 10 & 4 & 3 \\ 12 & 5 & 2 \end{bmatrix}$

ちなみに、この積魔方陣は $3$ 次積魔方陣のなかでサイズが最小です。美しい…

他の次元の積魔方陣も構成してみる

今までの議論のおさらいとして、他の次元の積魔方陣を構成してみます。

1次の積魔方陣

$1$ 次の方陣とはつまり、整数が $1$ 個しか使われていない方陣です。なので当然、各列・各行の積は等しくなります。よって、すべての $1$ 次方陣は積魔方陣であるといえます！
$1$ 次の最小の積魔方陣は以下の通りで、そのサイズは $1$ です。

$\begin{bmatrix} 1 \end{bmatrix}$

2次の積魔方陣

$2$ 次の積魔方陣は存在しません。証明を記します。

【証明】
$\begin{bmatrix} a & b \\ c & d \end{bmatrix}$
と表せる $2$ 次の積魔方陣が存在すると仮定します。積魔方陣の定義より、以下の等式が成り立ちます。

$a\times b=a\times c$

$a\neq 0$ より両辺を $a$ で割って、 $b=c$ が得られます。しかしこれは、積魔方陣の定義である「どの2つの数も異なる」に矛盾します。よって仮定が誤りで、 $2$ 次の積魔方陣は存在しません。

4次の積魔方陣

オイラー方陣を用いて構成してみます。準積魔方陣 $A, B$ を構成する要素の集合 $a, b$ の値をどう決めるかが重要です。とりあえず、集合 $a$ に $2$ のべき乗を、集合 $b$ に $3$ のべき乗をそれぞれ入れてみましょう。集合 $a, b$ の要素数は $4$ なので、小さい順に並べます。

$a=\{1, 2, 4, 8\}$
$b=\{1, 3, 9, 27\}$

明らかに集合 $b$ の値が大きいですね。集合 $a$ には素因数 $2$ が含まれているので、集合 $b$ には $2$ の倍数を含むことができません。 $2$ の倍数でない正整数、つまり奇数は必ず集合 $a$ の全ての要素と互いに素になります。よって、集合 $a, b$ は最終的に次のようになります。

$a=\{1, 2, 4, 8\}$
$b=\{1, 3, 5, 7\}$

これらの集合の各要素を $4$ 次のオイラー方陣に適用させると、 $4$ 次の積魔方陣が完成します。

$\begin{bmatrix} (0, 0) & (1, 1) & (2, 2) & (3, 3) \\ (1, 2) & (0, 3) & (3, 0) & (2, 1) \\ (2, 3) & (3, 2) & (0, 1) & (1, 0) \\ (3, 1) & (2, 0) & (1, 3) & (0, 2) \end{bmatrix} \to \begin{bmatrix} 1 & 6 & 20 & 56 \\ 10 & 7 & 8 & 12 \\ 28 & 40 & 3 & 2 \\ 24 & 4 & 14 & 5 \end{bmatrix}$

この積魔方陣のサイズは $6720$ です。この積魔方陣が $4$ 次の積魔方陣の中で最小のサイズである証明はできませんでしたが、おそらく最小と思われます。

5次の積魔方陣

先ほどと同様にして、 $5$ 次の積魔方陣を構成してみます。集合 $a$ の要素は $2$ のべき乗、集合 $b$ の要素は奇数、と仮定すると以下のようになります。

$a=\{1, 2, 4, 8, 16\}$
$b=\{1, 3, 5, 7, 9\}$

よくみると、今度は集合 $a$ の要素のうち $16$ が大きく見えます。ここで、「素数は自分自身の倍数を除いてどんな整数とも必ず互いに素となる」という性質を使うと、 $16\to 11$ と置き換えることができますね。よって、最終的な集合 $a, b$ は次のようになります。

$a=\{1, 2, 4, 8, 11\}$
$b=\{1, 3, 5, 7, 9\}$

これらの集合をもとに積魔方陣を構成すると、以下のようになります。

$\begin{bmatrix} (0,0) & (1,1) & (2,2) & (3,3) & (4,4) \\ (3,2) & (4,3) & (0,4) & (1,0) & (2,1) \\ (1,4) & (2,0) & (3,1) & (4,2) & (0,3) \\ (4,1) & (0,2) & (1,3) & (2,4) & (3,0) \\ (2,3) & (3,4) & (4,0) & (0,1) & (1,2) \end{bmatrix} \to \begin{bmatrix} 1 & 6 & 20 & 56 & 99 \\ 40 & 77 & 9 & 2 & 12 \\ 18 & 4 & 24 & 55 & 7 \\ 33 & 5 & 14 & 36 & 8 \\ 28 & 72 & 11 & 3 & 10 \end{bmatrix}$

この積魔方陣のサイズは $665280$ となります。 $5$ 次の積魔方陣が $2$ 桁以下の整数だけで構成されている美しい姿には、もはや感動すら覚えます。素晴らしい…

6次の積魔方陣

先ほど、 $6$ 次のオイラー方陣は存在しないことを書きました。しかし、 $6$ 次の和魔方陣は存在するので、 $6$ 次の積魔方陣も存在するということになります。実際に構成したものを書いてみると以下のようになります。

$\begin{bmatrix} 1 & 2 & 4 & 8589934592 & 17179869184 & 34359738368 \\ 1073741824 & 2147483648 & 16384 & 8 & 4194304 & 32 \\ 536870912 & 268435456 & 134217728 & 256 & 128 & 64 \\ 2048 & 1024 & 512 & 67108864 & 33554432 & 16777216 \\ 8388608 & 524288 & 2097152 & 1048576 & 16 & 262144 \\ 4096 & 65536 & 4294967296 & 32768 & 8192 & 131072 \end{bmatrix}$

いやいや、デカすぎますね！！一番大きい要素は $2^{35}$ で、なんと $11$ 桁もあります。でもこれが $6$ 次の最小サイズの積魔方陣とは考えにくいですよね。もっとサイズが小さくなるような数の組み合わせはあるのでしょうか…。

さらに高次の積魔方陣の構成について

$7$ 次以上の積魔方陣は、オイラー方陣を用いて構成することが可能です。よりサイズの小さな積魔方陣を構成するためには、集合 $a, b$ の要素の選び方が重要になってくることがわかると思います。しかし、最適な数字の選び方はまだわかっていません。素数が絡む問題は、いつも難しくなりがちです。

結論

積の魔方陣は、 $2$ 次のものを除いて存在します。今回は、

和魔方陣から構成する方法
オイラー方陣から構成する方法

の2種類を紹介しました。前者の方法はかなり有名ですが、後者の方法はあまり知られていないと思います。積の魔方陣を作って友達に自慢しましょう！

課題

この中では議論できなかった課題を並べておきます。「これ解けたよ！」ってのがあったら教えてください。

$6$ 次の最小サイズの積魔方陣は求められるでしょうか？
集合 $a, b$ の適切な要素の選び方はあるでしょうか？　もし素数のリストが与えられている場合に、効率よく構成することはできないでしょうか？
さらっと条件から外していましたが、今回の議論では方陣の各対角線の積は考慮しませんでした。各対角線の積も等しくするためには、今回紹介したオイラー方陣を用いる構成方法は使えません。どんな方法が考えられるでしょうか？
今回は数学の問題として手作業で構成することを想定していましたが、もし $N$ 次の最小の積魔方陣を構成するプログラムを組むとしたらどんなアルゴリズムが考えられるでしょうか？　そのアルゴリズムの計算量はどうなるでしょうか？

以上です。ここまでで約10000文字らしいです！400字詰めのレポートが25枚書けます。高専生の皆さんは、ちゃんとレポートを書きましょうね！！！

苫小牧高専アドベントカレンダー、明日はあやさんの担当です。それでは！

adventar.org

*1:オイラー方陣は複数通り考えられますが、どのオイラー方陣を利用しても積魔方陣のサイズは一定になります。

2020-11-29

AtCoder Regular Contest 109参加記（～C問題）

競プロ解説参加記

300-400-500-0(2)-0-0でノーペナ3完1200点。

A - Hands

この問題の構造は、各階→頂点、廊下・階段→辺として重み付きグラフに落とし込める。このグラフの2頂点間の最短路問題を解けばよい。例えば、ダイクストラ法で実装すれば頂点数 $V=200$ 、辺数 $E=397$ より計算量は $O(E\log V)$ となる。

実際に解いた時はなぜかBFSで実装していたがACできた。この辺よくわかってないのだが、最短路問題はDFSやBFSでも正しく解けるのだろうか？（今日はもう疲れたので明日考える）

B - log

長さが $n$ の丸太は、

長さ $n$ の丸太そのまま
長さ $n+1$ の丸太を切る

のどちらかの方法でしか入手できない。さらに、もし長さ $n+1$ の丸太から長さ $n$ の丸太を切り出せば、長さ $n-1$ の丸太に関して同じ議論が続くこととなる。この時、長さが $1$ の丸太が大量発生してもったいないので、基本的には

長さ $L$ の丸太は、長さ $L$ の丸太を買って手に入れる

ことにする。
ただし、これだと長さ $n+1$ の丸太を有効活用できていない。どの丸太も同じ値段なのだから、はじめに長さ $n+1$ の丸太を買って、短い丸太から順に切り出せるだけ切り出すのが最適である。
ここで、長さ $n+1$ の丸太から何本の丸太を切り出せるか？という小問題が出てくる。これは、 $x$ 本切り出せると仮定して二分探索を行う*1ことで $O(\log n)$ で計算可能。 $1$ から $x$ までの整数の総和は $\frac{x\times (x+1)}{2}$ で求められる。
$n$ 本買う予定だったうちの $x$ 本を買わずに、長さが $n+1$ の丸太 $1$ 本で代用するので、答えは $n-x+1$ である。計算量は、 $O(\log n)$ 。

C - Large RPS Tournament

トーナメントの参加者は最大で $2^{100}$ となるため、愚直にシミュレーションしていては当然間に合わない。ここで、各参加者が出す手は周期的であるため、同じ計算をしている箇所があるはずである。トーナメントの1回戦目を考えると、 $2n$ 人ごとに同じ手を出すペアが同じ順番で登場することがわかる。よって、はじめの $2n$ 人分だけ考えてそれを長さ $n$ の配列に保存すれば一回戦目の結果はすべてわかる。
その次の試合結果も、先ほどの議論を再帰的に適用することで、はじめの $2n$ 人分だけ考えればすべての結果がわかる。

f:id:mmnkblog:20201129002836p:plain — k=4, n=3の例。青字の部分を複製し、赤字の部分だけ保存する

これを $k$ 回繰り返したとき、配列の先頭に保存されている手が優勝する手である。

計算量は、 $O(kn)$ 。

D - L

解けなかった。

（諸事情により削除しました）

上記ツイートの数字は、石がそのマスまで移動するのにかかる最小手数を表している。移動したい位置がくの字であることは保証されているので、移動先の3つのマスにそれぞれ移動するまでの最小手数（上記ツイートの数字）を計算し、3つの最小手数の中の最大値に対して

最大値が3つ中1つだけならその最大値を出力
最大値が3つ中2つあるなら最大値＋１を出力

というアルゴリズムで実装したが、WAだった。

感想

3完はできたものの、もう少し早くACできればもっと良かったかなと思う。ただペナルティを出さなかったのはえらい。

*1:オーバーフローを避けるために、実装時は $x=1$ から初めて2倍にしていく方法でやった。

2020-11-23

AtCoder Beginner Contest 184参加記（全問題）

競プロ解説参加記

100-200-300-0-0(1)-600(1)で1ペナ4完1200点。

A - Determinant

行列は丸括弧で与えないとダメなんじゃないの？と思いつつ解いた。ちなみに丸括弧にはいろいろな意味があるので、紛らわしさをなくすために行列は角括弧で表すことがあるらしい。ためになったね～（もう中学生）

問題文に書かれている通り、入力値から行列式の値を計算して出力する。いわゆる「問題文に答えが書いてある」のもっとも基礎的なパターンで、なんと一番早いACは13秒である。おそろしや…

計算量は、 $O(1)$ 。

B - Quizzes

それぞれのクイズが終了した時点での点数がいくつなのかを計算すればよい。持ち点が $0$ 点のときにxが来ても $0$ 点のままで、この辺りに躓くことなく実装できるかがカギとなる。

計算量は、 $O(N)$ 。

C - Super Ryuma

ぱっと見、どこから手を付けていいのか迷ってしまった。この駒の移動方法は、

「対角線上のマスへ移動」
「マンハッタン距離が3以下のマスへ移動」

の2種類の移動が組み合わさっている。ここで、「対角線上のマスへ移動」は距離に制限がないので、この移動を2回繰り返せば、移動したいマスのすぐ近くまでは絶対にいけることがわかる。この辺をしっかり議論していく。

まず、スタート地点とゴール地点が重なっている可能性がある。この場合は $0$ 手で移動できる。

次に、 $1$ 手で移動できる場合を考える。これは、問題文で示された駒の動ける範囲にゴール地点が重なっている場合のみであり、この条件を満たすかは問題文に示されたとおりの式を満たすかどうかでわかる。

よって、これら以外のマスに行くためには最低 $2$ 手必要である。ここで、先ほどの2種類の移動方法の選び方により、 $2$ 手移動する方法は以下の3通り考えられる。

「対角線上のマスへ移動」してから「対角線上のマスへ移動」する
「対角線上のマスへ移動」してから「マンハッタン距離が3以下のマスへ移動」する
「マンハッタン距離が3以下のマスへ移動」してから「マンハッタン距離が3以下のマスへ移動」する

1番の移動方法では、以下に示すように市松模様の同じ色のマスへしか移動できない。逆に、市松模様の同じ色のマス同士なら、必ず2手で移動できる。同じ色のマスであるための条件は、 $x$ 座標と $y$ 座標の和の偶奇が一致していることである。
違う色同士のマスへ移動するには、移動したいマスの1つ隣のマスを選んで2手かけて移動し、3手目に1マス隣に移動することで移動可能である。このことから、最大でも3手以内に移動可能であることがわかった。つまり、これ以外での移動方法に関して議論するとき、2手で移動できないことがわかれば十分である（2手で移動できないならこの方法で3手かけて移動するのが最短だから）。

f:id:mmnkblog:20201123002942p:plain — 1番目の移動の例：(3, 0)→(0, 9)

2番の移動方法について考える。この場合、ゴール地点とのマンハッタン距離が3以下であるようなマスへ1手で移動できるか？ということを考えればよい。斜めに移動するとき、ゴール地点とのマンハッタン距離が最短となるように移動するには、例えばゴール地点の $x$ 座標と移動先の $x$ 座標が等しくなるように移動すればよい。（証明略）
あとは、移動先のマスとゴール地点のマスのマンハッタン距離が3以下かどうか判定すれば移動できるかがわかる。

f:id:mmnkblog:20201123002946p:plain — 2番目の移動の例：(0, 0)→(5, 8)

3番の移動方法についてもしっかり考えないといけない。この移動方法は、「マンハッタン距離が6以下のマスへ移動」することと同じである。よって、スタート地点とゴール地点のマンハッタン距離が4以上6以下なら、2手で移動できる。

f:id:mmnkblog:20201123003517p:plain — 3番目の移動の例：(0, 4)→(5, 4)

ここまでの条件をすべて確認して、ようやくACが得られる。しかし、どうやら3番の移動方法を考慮していない解法でもACが得られてしまうようだ。このテストケースが抜けているのもどうかと思うが、嘘解法で通してしまった人はせめてこの理屈だけでも理解するようにすべきだと思う。

計算量は、 $O(1)$ 。

D - increment of coins

解けなかった。とりあえず、

$dp[i][j][k] =$ 金貨が $i$ 枚、銀貨が $j$ 枚、銅貨が $k$ 枚ある状態へ遷移する確率

というDPを思いつく。制約からも $O(ABC)$ が通るのであってるかなーと思ったが、確率を浮動小数点数型で保存すると誤差がひどすぎて正しい答えが得られず、かといって遷移する通り数を保存するとオーバーフローしてしまう。Pythonで書こうか迷って順位表を見たらE問題よりF問題の方が解かれていて、捨てた。

公式の解説を見る限りでは数値誤差でひっかけるつもりはなさそうなので、単純に考察が間違っていただけかもしれない。たぶんそうだと思う。順位表を見て正解だった。

E - Third Avenue

解けなかった。F問題を解いた後に問題を読んだが、言い訳をすると時間が足りなかった。
問題自体はよくあるグリッド上の迷路の最短距離を求めるもので、テレポーターによる瞬間移動をどう実装するかが肝である。BFSをベースに実装し、テレポーターがあるマスを事前にメモしておくことですぐテレポート先を参照できるようにした。また、同じ種類のテレポーターを2回以上使う必要はないので、1度使った同じ種類のテレポーターは使えないようにした。
これであっていると思って提出したのだが、2ケースだけWAが出ている。原因はわからない。

F - Programming Contest

これはいわゆる「部分和問題」というやつで、集合の中からいくつか整数を取ってきたときの和に関する問題をまとめてこう呼ぶ。解法もいろいろあって、制約から決めることが多い（諸説あり）。

全探索して解いたときの計算量は、 $N$ 個ある整数それぞれに対して、「取る」か「取らない」かを決めていくので、選び方は $2^N$ 通り。このうち $T$ 以下で最大のものを探すだけなので、計算量は $O(2^N)$ となる。今回の制約の最大値 $N=40$ を代入して概算すると、 $2^{40} \fallingdotseq 10^{12}$ となるため実行時間制限に間に合わない。

ここで、半分全列挙と呼ばれるテクを使うことで、計算量を $O(N2^{\frac{N}{2}})$ にすることができる。詳しいやり方はググるべし。
ざっくり方針を述べる。40個の整数を20個ずつに分けてそれぞれの選び方をすべて試す。前半の集合から得られた部分和を $A$ として、後半の集合の部分和の中から $T-A$ 以下のうち最大のものを二分探索で探す。これらの最大値が答えとなる。

計算量は、整数の選び方をすべて試すのに $O(2^{\frac{N}{2}})$ 、二分探索するのに $O(\log(2^{\frac{N}{2}})) = O(N)$ かかるので、全体では $O(N2^{\frac{N}{2}})$ となる。

感想

点数で重みをつけるなら問題間の難易度の勾配はしっかりつけてほしい。もっとACL活用するような問題出してもええんやで…