無限直積の双対加群こわい
概要・参考文献
を示します.
https://mathoverflow.net/q/10239 ←これを読み解いたよというような話です.
何がすごいの?
は簡単です.直和の普遍性と,同一視 ですね.こっちは を任意の単位的可換環にしても成り立ちます.一方,直積からの準同型というのは,なんだかよくわからないものです.
また, じゃなくて体 だったら様子が異なってきます.無限次元線型空間の双対をとると次元が真に大きくなることが知られていて, です.
体だったら基底がとれるので双対をとれば単に大きくなるところが, だと直積からの準同型というのが意外ときつい制約で,小さくなってなぜかちょうど直和くらいになってしまう.そんな不思議な定理です.
証明の流れ
準同型 を ( は第 成分だけ で他が のやつ) で定めたとき,
- が単射であること
- であること
を示します.この 1. は当たり前と思いきやそうではなくて,各 に対して を決めたからといって とはできない (有限和になってない!) のが罠です.直積の厄介なところですね.
1. 単射性
,つまり任意の に対して であることを仮定して, を示す.
任意の をとる.各 について, と は互いに素なので, となる がとれる.
任意の に対して, なので,仮定より .よって .
同様に なので,.以上で が示せた.
これは, の「PID だが局所環ではない」という性質を使っています.体でない局所環で反例が作れるかは,よくわかりません…….
2. 像が直和に入ること
任意に をとったとき,,つまり のうち有限個を除いて となることを示す.
を, かつ (整除) かつ任意の で が成り立つようにとれる (順番に,十分大きい倍数をとっていけばよい).
任意の について, なので, とおくと となる.すると三角不等式と のとり方より が成り立つ.ここで,十分大きい では なので である.
なので,十分大きい では となり,示すべきことが得られた.
お気持ちとしては,「めっちゃ増えてくような無限列も有限値に送らないといけないので,それっぽい列をとれば後ろの方の影響があってはならないことが言える」みたいな感じです.
mathoverflow にリンクが貼られている http://www-users.mat.umk.pl/~gregbob/seminars/2008.11.07b.pdf では不等式評価を用いずに,こちらも局所環でない PID について示そうとしているのですが,PDF でいう のところが間違っています ( が ではなく なので). の場合なら とか とか好きに決められるので簡単に直せるのですが,一般にはダメそうです.上手く修正できる気もしますがあまり考えていません.
コメント
無限直和とか無限直積とかはやっぱりこわいですが,好きな定理上位にランクインしました.
間違いを見つけた方は是非教えてください.
Codeforces 1119H: Triple
https://codeforces.com/problemset/problem/1119/H
問題概要
が固定されている. に対して が与えられるので, たちを の指数は XOR で畳み込む,というのを速くやる.
考察
Hadamard 変換すれば畳み込みが掛け算になる (常識) けど,そのままやると長さ の列を 個作らなければいけなくてダメ.
を Hadamard 変換すると 項目は になる ( は ビットの整数を長さ のベクトルと見た内積) (定義).ので,出てくる値は しかない (これは定義に戻ることを忘れていても実験すればわかる).ので, 項目の積は みたいになって ( とかは に依存), とか関係なくて 個の指数が上手く求まればうれしい.例えば は が全部偶数になるような の個数とかそういう.手早く数えられそうでできない (「数える」という考えから抜けられなくてコンテスト中はここで止まった).
「 とか関係なくて」とか言ったんだから特殊な値を代入して何かしてみるべき (極めて一般的な手法).例えば として (これは自然な「特殊な値」), だけど,これすら各 について手早くのは難しそうなうえに得られる情報量が少ない (普通の感想).得られる情報量を多くしようとして指数の底を とか とかじゃないようにしても綺麗になる気配はない (たぶん普通の美的感覚).ということで,代わりに を考えよう (これは,お気持ちはわからなくはないけど,かなり賢いと思う).左辺は Hadamard 変換の線形性を使えるうれしい形をしていて, を一度変換すれば各 について求まる.
同様に と が求まることがわかった.あとどんな関係があれば とかを特定できるか?というと,長さ の Hadamard 変換っぽい見た目をしているので (Hadamard 変換の問題を解いているのだから Hadamard 変換っぽい見た目には気づく), とかそういうやつがほしい.それは とかで,そんなのが求まるかというと,よく見ると なのでうれしい (冷静さが必要).これでできたのでまとめると,
解法
- のそれぞれを Hadamard 変換する.
- 各 に対して, 項目を集めて長さ の列にして Hadamard 逆変換すると, の各指数が得られるので,計算する.
- というのを並べて,Hadamard 逆変換すると答え.
コメント
項しかないというのの は小さいことしか本質ではなくて, 項だったら 時間とかでできますね.
思考の整理のために書いてみたのですが,賢いところが一箇所な割にはすごいことができていて,不思議な感じが残りました.
Xmas Contest 2018
Xmas Contest 2018 にご参加いただいた皆様,どうもありがとうございました!
2015, 2016, 2017 年は元気にしていなくて開催できなかったのですが,その間引き継いでくれていた japlj さんと snuke さんと共に今年は運営しました.とっつきやすい良問を作ってもらったり (A, F, G),雑に提案したのをちゃんと解いてもらったり,クリスマスコンテストっぽくない問題をちゃんと却下してくれたり,いろいろやってもらえて助かりました.
わたしが原案を出した問題の解説をこのブログに載せておきました.変なとこがあったら教えてください.数式多めなので環境によっては見づらいかもしれませんごめんなさい.
Xmas Contest 2018 J: Japanese Exponentation 解説
https://atcoder.jp/contests/xmascon18/tasks/xmascon18_j
問題概要
四の三の二乗乗
みたいなのを で計算せよ.
解法
UTF-8 の文字列を処理する方法は,皆さんお使いのプログラミング言語ごとに調べてください.
冪乗を で計算する方法を考えます.「 のとき 」は正しいですが,「 のとき 」は正しくないので,指数は勝手に をとってはいけません.
とはいえ, での は必ずどこかから周期的になります.最初から周期に入っているとは限りません.例えば のときは となり, から長さ の周期に入ります.どこからどんな長さの周期に入るかについては,以下の事実がよく知られており (補足参照),この問題ではこれで十分です:
- なら, は既に周期に入っている.
- 周期の長さは の約数である.ただし は Euler の φ 関数.
というわけで,指数はおおよそは でもっておけばいいですが,小さい値,雑に 未満くらいは特別に扱う必要があります.実装上は,例えば次のいずれかのような方針がわかりやすいと思います:
- をとる代わりに, 以上の整数は に収めるようにする ( を にする).
- 整数 の計算結果として,) の組をもつ.
以上をふまえると,構文解析パート (再帰下降) を合わせて解答は次のようになります.
Result expr(m): // Result 型は上記のように特殊な mod のとり方をした整数 Result a := number(m) // 整数を読む while 次の文字が "の": "の" を読む Result b := expr(φ(m)) a := a^b // 繰り返し二乗法などで計算 "乗" を読む return a
なお, は 回で になるので,同じ の計算を複数回しないようにすれば実行時間は大丈夫です.
補足
での の様子について,もうちょっとちゃんとした話をします.
中国剰余定理より, としては素冪 だけ考えればよいです.素冪ごとに考えた後で,周期に入る場所は をとればいいし,周期の長さ (の倍数) は最小公倍数をとればいいです.
( は非負整数, は で割れない) と書くと, のとき の部分は累乗していくと途中からずっと になってしまい,これが周期の前の部分を作っている要因です.高々 乗で になるので,周期に入るまでの長さは 以下です.一方 の部分だけ見ると最初から周期に入っていて,その周期は
- かつ のとき
- その他のとき
の約数です.さらに,実際にこれらの周期をとる が存在します (原始根の存在定理など).
ここまで考察すると,この問題で必要な は だけで済むことがわかります.
コメント
この問題は,本当に問題文のストーリー通りの流れで作りました.「 の 乗」の構文は,
になっていて面白いです.
マルチバイト文字は,こういうコンテストだからこその出題という感じですね.いろいろ調べていたら 六
にだけ互換文字があるとかいう知識が増えてしまいました.
数学パートは,「普段なんとなくで をとっていませんか?」というメッセージ (?) です.
Xmas Contest 2018 I: Interesting Equation 解説
https://atcoder.jp/contests/xmascon18/tasks/xmascon18_i
問題概要
実数 が与えられるので, がだいたい になるような整数 を求めよ.
解法 ?
なる解の存在が保証されているので,その範囲の をすべて調べられれば答えが見つかります.
もちろんそれでは遅すぎるので,半分全列挙のようなことを行いたいです. の小数部分たち, の小数部分たちをそれぞれ列挙すると,ソートして尺取法などを行うことによって答えを探せます.これでも片方は 通りほど列挙しなければならないので厳しいですが,何回か提出して の範囲を適当に制限するなどの方法で正解することができるかもしれません (実際,コンテスト中にこのような解法が何件か正解していました).
解法 1
より均等に分けた半分全列挙を行うことができます.例えば (,) と表すことができ, の小数部分たち, の小数部分たちを列挙します.するとどちらも 程度のサイズとなり,十分高速となります.
チーム aadeeggimrsstuw がこの解法で正解していました.
解法 2
を十分大きい値として, の 本のベクトル
を考えます ( は に最も近い整数とします).これらの整数係数線型結合であって長さが十分短いものを見つけられれば,それが答えになります:整数 に対し の長さが短いとき, は小さく, は くらいなのでだいたい ,という気持ちです.
「整数係数線型結合で長さが十分小さいもの」を見つける方法として,LLL Algorithm が知られています.詳しい説明は web にいろいろな資料があるので,ざっくりだけ紹介します.
集合 (格子と呼ばれます) を変えないように を変形していきます.変形の操作は次の 種類からなります:
- いい感じの条件を満たすように を並べ替える.
- に Gram-Schmidt の直交化を行ったものを とする. に対し, を で置き換える.
これをいい感じの順番で行うのが LLL Algorithm で,一般の 次元でも多項式時間で最適解の 倍の長さのベクトルが得られるそうです.すごいですね.一応なぜ直交化したいかの気持ちを説明すると, は生成する格子にしかよらず (格子の体積),これは基底が直交していれば長さの積,ななめっていれば長さの積より小さくなっていくので,体積一定では直交に近いほうが長さが短い,という感じです.
この問題では,がんばって評価をすると, ととれば制約下で正解が保証できることが示せます (ごちゃごちゃしてしんどいだけなので省略します).演算は double 等でも大丈夫だと思いますが,多倍長有理数で時間に余裕を持ちつつ正確に行うこともできます.
omeometo さんの解法は,LLL Algorithm の代わりに, を で置き換えるというのをランダムな を選んでたくさんやっていました.ベクトルが短くなっていく感じはほぼ同じなので,十分な回数回していれば落ちなさそうです.
コメント
コンテスト開始直後,全 ではないという条件が抜けていました.そういうつもりじゃなかったんです,でもクリスマスコンテストならそういうのありえますよね…….ごめんなさい.
想定解は解法 で,無理問だけど強引にも通せるかも?くらいに思いながら出題しました.予想より正解者数が多かったです.特に解法 は全く気付いていなかったのでなるほどという感じでした.
問題文冒頭はさすがにやりすぎですが, 次式の根で を近似すると なんてのが得られたり,LLL Algorithm でいろいろ遊んでみると楽しかったです.
Xmas Contest 2018 H: Hello, Xmas Contest 2018 解説
https://atcoder.jp/contests/xmascon18/tasks/xmascon18_h
問題概要
文字列 が与えられる.グリッドの一部に A
-Z
または *
を書いて,
- 各行の最初の非空白文字を順に繋げて
*
を除いた文字列が - 各列の最初の非空白文字を順に繋げて
*
を除いた文字列が
となるようにする.最低何文字書く必要があるか? (入出力例の図を見るのがわかりやすいです)
解法
ある文字 が に 回, に 回現れたとすると,文字 は少なくとも 個書かなければいけません.これを A
-Z
について足すことで答えの下界が得られます.
この下界はだいたい達成できそうな気がします:
|AAACCB -+------ A|A..... A|.AA... B|.....B C|...CC. B|......
具体的には, と の両方に現れる文字は問題なく配置できます.片方にしか現れない文字がある場合は,
|UNAGI -+----- U|UN... S|S.... A|..A.. G|...G. I|....I
|BAD -+--- A|.AD B|B.. C|C..
のように 行目の文字や 列目の文字で隠してしまえばよいです.隠せないのは,
|AC -+-- W|.. A|AC
のように 行目の文字が に現れない場合,あるいは 列目の文字が に現れない場合,のみです.そのような場合は *
を 個以上書く必要があり,逆に *
を 個左上に書いてしまえば隠したい文字を隠せます (看板を作ることが不可能なケースはありません).
まとめると,
A
-Z
のそれぞれについて, に現れる個数と に現れる個数の をとって足し,- の先頭が に含まれない,あるいは, の先頭が に含まれない,という場合だけ を足す
と答えになります.
コメント
最初は,色のついた積み木を積んだときの見取り図が 方向から与えられる,という設定で解こうとしていて,しかし高さ 以上のときわからなかったので高さ にしたら,無意識に昨年の問題と同じような設定になっていました.
制約は,解法を絞らせないために敢えてゆるくしました.
Xmas Contest 2018 E: Exclusive☆OR 解説
https://atcoder.jp/contests/xmascon18/tasks/xmascon18_e
問題概要
個のブール変数から 個とった XOR たちを,AND と OR と NOT を使って作る.NOT の使用回数を最小化せよ.
N = 1 のとき
何もしなければ正解です.
N = 2 のとき
なので, に NOT を使うと 回でできます.NOT なしでは と しか作れないので, 回ではできません.
N = 3 のとき
NOT 回でできます.下からの評価 ( 回ではできない) は後ほど.
の場合はこちらで手で遊べる.
と書いてあるやつで遊んでみると解けるかもしれません.正解できる NOT 対象はいくつかあるのですが,次の方法が一般の での解法に繋がります:
は「 のうち true のものの個数が のいずれかである」かどうかを表すブール変数になっています.この変数に着目することが以下の解法での鍵となってきます.
N - 1 回解法
次の ステップでできます:
- を求める.これは AND と OR だけでできる.
- を求める. である.ここで 回の NOT を使っている.
- を求める.まず, を「 と 以外のうち true が 個以上」かどうかとする.これは AND と OR だけで求まる.すると,以下が成り立つ:
最後の式が何を意味しているかというと,「 と のうちには true が 個以上」かつ「 と 以外には true が 個以上」かつ「全体では true がちょうど 個」,というのを について OR をとっていますが, なので「以上」が消えて,「 と のうちには true がちょうど 個」,すなわち がもれなく求められている,ということになります.
log N 回解法
上の解法のステップ は実は 回の NOT でできてしまいます. のときの例を示すとこんな感じ:
一般には, に対して,「下から ビット目が である数に を足したもの」たちが の中身に入るような変数に NOT をすると上手くいきます.すごい.
行数制限
ここまで NOT の回数だけを気にしていましたが,この問題では AND, OR, NOT を合わせて 回以下でなければいけないのでした.ステップ とステップ で「true が 個以上」みたいなのを求めるのを愚直にやると について指数回かかってしまいます ( くらいまで正解できて, 点です).これは,DP で の計算でできます:
for i = 0 to N - 1: for x = N - 1 to 1: f(x + 1, ..., N) := f(x + 1, ..., N) OR (f(x, ..., N) AND b_i) f(1, ..., N) := f(1, ..., N) OR b_i
ステップ のほうでは 回 ( たちから 個除いて) これをやるので 回の計算になります.実はこれを にすることもできますが省略します (満点には必要ないです).これで無事に 行に収まるようにできました.
下からの評価
NOT の最小使用回数は です.これ未満ではできないことを示しておきます.
NOT の使用回数が でできるプログラム が存在したとします. の入力に の 通りを入れたとき, なので鳩ノ巣原理より,どれか パターンでは 回の NOT の計算結果が全部一致するはずなのです.それを と () のときとします.
このとき,以下のようなプログラム が作れてしまいます:
- の入力は 変数である.入力 に対して, に入力 を与える.
- の計算途中において, 箇所のNOT を使う部分は,上で計算結果が一致したという値の定数に置き換える.
- の出力 をとってきて の出力とする.
すると の出力は ですが, は AND と OR しか使っていないので NOT ができてしまうのは矛盾です.
コメント
コンテスト開始後はしばらくジャッジが正常に動いておらず申し訳ありませんでした.
満点までの道のりが壮大な感じで,難しい問題だったと思います.でもなんかすごいですよねこれ.
作題のきっかけは,「3-not problem」 (2 NOTs problem だったり呼称は安定していないっぽい) という一部界隈では有名らしい問題を知ったことです. で, を NOT 2 回で作ろうというもの.一般の では最小 回です. たちがあれば XOR は作れるのですが, を考えたらもう少しうまくできるのではと思い, を全探索していろいろ気づいた,という流れでありました.