Elimination , Extension

代数閉体,ここでは特に\mathbb{C}係数とする.

 

連立方程式x^2+2y^2 - 3 = 0 \\ x^2 + x y + y^2 - 3 = 0

を考える.イデアルI = \langle x^2+2y^2 - 3 ,x^2 + x y + y^2 - 3 \rangle \in \mathbb{C}[x,y]の零点集合を考えれば良い.

多項式の並べる順序はxの次数が大きい順,同じときはyの次数が大きい順に並べる(辞書式).

これのGrobner基底Gをコンピュータくんに計算させて得る.Grobner基底は,ある多項式をその基底で割り算したときの余りが一意になるもので,

 f \in I \iff f\text{を}G\text{で割った余りが}0

が成り立つ.

 

そうすると,Grobner基底 G = \{g_1,g_2,g_3\}は,

g_1 = x^2 + y^2 - 3\\ g_2 = xy-y^2\\ g_3 = y^3 - y

 つまりI=\langle x^2+y^2-3,xy-y^2 , y^3 - y\rangle

と考えて良い.

 

こうすると,最後のy^3 - yxによらないy多項式の元,すなわち,I \cap \mathbb{C}[y ]の元になっている(Elimination of x)が,実はイデアルI \cap \mathbb{C}[y ]のGrobner基底が,\langle y^3 - y \rangleとなっている.

 

このy^3-yを解くとy = 0,1,-1になる.連立方程式を解くときはこれを他の式に代入してxを得ればよい.

すると,(x,y)=(-1,-1),(1,1),(\sqrt{3},0),(-\sqrt{3},0)が得られる.

すべてのy=0,1,-1に対して解がきちんと得られた.

 

うまくいかないやつ.

xy-1=0 \\ xz-1 = 0

Grobner基底を計算すると,

\langle xy-1,xz-1 \rangle = \langle xz-1, y-z \rangle

なので,解けているところy-zからy=zである.これをaと置く.

このaa=0のときは, az - 1 = -1になってしまってxz-1 = 0の解がなくなってしまう.a=0でなければx = 1/aで良い.

 

操作自体は人間が普通に解くように,適当に変形してy-zみたいなわかりやすい形にしてそこで関係式を得て,残りの式に代入して他の変数も得る,これと同じことを行っている.

 

Grobner基底の計算で行っているのは,出てくる変数の一部を消去しようとしている.人間が普通に連立方程式を解くときも変数を減らそうとするのが普通なので,それと対応していると考えられる.

(ただしこれはlex orderにおけるelimination idealを考えている場合に限られる,パラメータとして変数を与えていて,残りの実際の変数よりも大きくなるような順序を与えることでパラメータ消去と見ることもできる.)

 

それでは,一部の式から残りの式に代入してうまくいくかどうか,というのは次のような言葉を使って説明できる.

 

今の最後の例だと,一部の式から(y,z)を得て,それを(x,y,z)に延長(Extension)しようとした.a=0だと失敗し,それ以外だと成功した.

実は,既にわかっている(y,z)から(x,y,z)に延長するときは,イデアルの基底それぞれをg_1,\ldots,g_s(ここではy-z,xz-1)に,ここまでの暫定的な解(partial solution)y,zを代入して,xの最高次の係数(すなわち,y,z多項式)がどうなるかを見る.

どのg_iもその代入によってxの最高次係数が0になってしまったら,(x,y,z)に解が延長できない.0にならないものが1つでもあれば解が延長できる.今回の例だと,xz-1zが係数であり,ここがz=a=0だとxの最高次xが0に消えてしまうので解が延長できず,a \neq 0だと係数が消えないので解が延長できる.

 

参考文献

David.A.Cox, John Little, Donal O’Shea, Ideals, Varieties, and Algorithms, Fourth Edition”, Springer, 2015

 

 

 

院試の体験メモ(外部進学)

こういうのは覚えてるうちにまとめた方がいいって.もう忘れかけてるけど.

来年以降似たような人の参考になればいい気がしています.

 その時に起こったこととやった方がよかったことを混ぜるので読みにくかったらすみません.

 

 

●概要

・外部進学

・数学科

・今いるところとだいたいレベル同じぐらい(たぶん.分からない)

・院試問題演習は2ヶ月かけたけどたぶんこんないらない

 

●半年前〜2ヶ月前ぐらい

その内容で院進みたいならうちより外部進学かな〜と言われる.えーってなる.

候補が2,3見つかったので,各大学のHPとか,先生の名前で論文とかを調べて具体的にどの辺の分野なのかを(自分のわかるレベルで)調べる.

 

受ける大学が決まったあたりでやることは,

・向こうの先生にアポをとり,実際に募集が行われているかを確認する(実質取ってないとか言われたら終わりなので).

 

・過去問を手に入れる.数学はだいたい公開されているので良いとして,英語が手に入るかを確認する.(私は手に入らなくてぶっつけ本番だった).

 

 

●研究室訪問

→研究したい内容と,そこの学生がやってることと,院試について,ゼミについてとかを一通り聞いておくと良さそう.事前に絶対メモを用意したほうがいい(それはそう)

 

→訪問と言っても,ある程度やりたい内容をできる限り細かいところまで詰めておいた方がよくて,そうしないと,なんか勉強進んでなくて何があるかわかってないねとなる.ごめんなさいする.

 

非自明なこととして,

→院試の合格点というか最低点あたりを確認しておくと多くの場合心が穏やかになります.

→外部受験の受かり具合を確認します.特に倍率が○倍に対して,事前に引かれた合格ラインを越えれば合格なのか,学部入試のように競争的に上から拾われるのかを確認しておいた方がいいような気がします.後者はどう考えてもしんどいです.

 

あと,過去問が手に入ったあとに,院試勉強にかかる時間を確認するために,数年分を見て出題範囲を確認する.特に何問とかないと行けないかを確認して+1問分の分野を勉強すると良さそう.本番よう分からん問題が出たら詰むので.

 

私の場合は,代数と位相空間論以外,解ける気がしなかったので,代数に絞ったところGalois理論をB2の春に自主ゼミでかじったぐらいしかなかったので,問題演習しながら復習しました(後述).

 

それで2ヶ月前までは院試勉強の準備みたいな感じで普通にB4ゼミの本とかを読んでました.

 

●2ヶ月前〜1週間前

ひとまず過去問を見て,1問あたり何分かけていいかを確認して,その時間いっぱいまで考えて,埋まらなかったら,参考書をひっくり返してそれっぽい解答を作る.を繰り返した.

 

微積は計算間違えまくるわ,線形は微妙に覚えてないことが多いわで辛い. 代数はなんか分からん.位相空間論は忘れた.ひどい.

とりあえず,これで本番解こうとしている分野で,解けた問題と,参考書見て解けた問題と,一生解けない問題を分けた.

特に,テキストを見て分からないやつは演習で類題をあたるしかなく,

www.kyoritsu-pub.co.jp

 

株式会社サイエンス社 株式会社新世社 株式会社数理工学社

 

微積は何でやったか忘れた.

 

あたりを見るとだいたいなんとかなりました.(強い大学は知りません).

 

そうすると,1ヶ月半前ぐらいに過去問が1週終わったので,あとは解けずにそのまま未解決の問題をひたすら考えるか,典型的な計算の練習(Jordan標準形とか,重積分のやつとか)と,過去問2週目を順番にやっていく.初めて過去問を回すという行為をした気がする.不真面目なので.

 

受験テク的には時間を測って全体で〜〜分とかやるんでしょうけど,めんどいのでやりませんでした.

本番は時間を問題数でn等分すればいいやという感じ.

 

さらに過去問以外の問題演習として, 

テキストを漁っても,院試っぽい問題って以外とあんまりなくて,(複合的っていうのかな)

 

株式会社サイエンス社 株式会社新世社 株式会社数理工学社

 

株式会社サイエンス社 株式会社新世社 株式会社数理工学社

 

どちらも数学科向けではないんだけど,後者の方がまだ練習になった気がする.きゅーてーとかは知らんけど,それ以外はなんやかんや普通の計算は出るので,ひたすらJordan標準形の計算をしてた.出なかった.悲しい.

 

●1週間前〜前日

たくさん食べてよく寝ます.

このあたりで,今の先生にごめんなさいをします.

前日のホテルでは一睡もできませんでした.

 

●筆記試験

起床チャレンジをACする必要があります.時計とか忘れないようにします.上着は暑いので脱ぎます.

 

雰囲気は学部試験の時よりも,もっとこう身内感のあるゆるい感じでした.いやもちろん手続き上のことはきっちりしてるけどなんというのかなあの雰囲気.内部生ばっかりだったらしい.やっぱりかあ.

 

外部なので周りにプレッシャーをかけますが,あとで無駄だったことを知ります.理由は前にあげたとおり.

 

●口頭試問

名前と受験番号を噛まずに言えるようにしておきます(←これだいじ!!!!!!)

たぶんありがちな,

・志望動機

・なぜ外部を受けたのか

・今ゼミでやっている内容について

・課程修了後の話

・専門分野の話(↑と重複する)

あたりの答えを準備しておきました.

あとは,筆記で悪かったところを解き直させられるというおきまりのやつがあります(あるらしいです).

 

私の場合は,上4つと筆記試験の手応えを聞かれたあと,「では」と言われたので専門の内容を聞かれるかと思って身構えたら「退室して良いです」と言われたので2秒で退室しました.外部で面接が速攻で受かっても勝ってるパターンがあるらしいです.

 

こればっかりは人によるみたいで,内部生でも長いこと時間がかかってる人は筆記でボーダー付近にいたりして黒板張り付けの刑を受けているみたいです.知り合いの院生に面接でのアドバイスを聞いたら「運ゲー」と言われました.運ゲーらしいです.

 

●まとめ

過去問の入手,分析と入試の情報,研究室訪問は早めに済ませておいて,ぎりぎりまで普通に専門にしたい分野の勉強をしておいて,1,2ヶ月でパパッと院試勉強をした方がだれずに済みます.嘘です2ヶ月ですらダレました.院試勉強が面白くないのはやり始めて6秒で気づきます.

 

ここまでの話は一番上に書いた通りの条件での

話なので,院試のレベルが上がる人はさすがにこうはいかないとは思いますが,なんか参考になったところが1ミクロンでもあればいいなと思います.

 

 

 

久しぶりに120文字以上文字を書いたら,ノートパソコンの熱で,足の皮膚が真っ赤になりました.

 

もっとも最近は,121字以上かけるとこにいるんですが.

@NaruY@mstdn.jp

@NaruY@mathtod.online

ひょろーよろしくお願いします.

 

 

 

Mujin Programming Challenge 2018 - Dのやつ

D - うほょじご

についてなんですけど.

 

想定解は,(x,y) -> (z,w)という遷移をグラフとしてすべて表しておいて,(x,0) or (y,0)に最終的に移るものを変えて,NMから引けばよく,遷移先が一意なので,ループはかならず,(x,0),(y,0)と連結にならない.したがって無向グラフとして考えられる.

 

なので,全部グラフを引いてから,DFSやらUDFSなどを使って数えるというもののようです.

 

TLで「適当に回せるだけ回して判定したら通った」という声を聞いたので考えてみます.

 

具体的に言うと,

言われたとおりにx,yを最大でL回操作する.

L回操作するうちに,(x,0),(0,y)の形にならなかったら,無限に続くと判定する.

 

この方法を取ると,

M=N=999のとき,L=998だと40040回.

M=N=999のとき,L=998だと40032回.

M=N=1000のとき,L=998だと40032回.

十分大きいnに対して,n回でちょうどx,yのどちらかが0になるとき,n-1回でどちらかが0になる組が存在するはずなので,増加が一度止まったらそれ以上増えることがないので,L=999を調べればよく実際これでACする.

Submission #2948200 - Mujin Programming Challenge 2018

 

 

どう見ても想定解じゃないですが,C++14だと通るからこれでいいかとなってたんですが,999回でちょうど条件を満たす,

(1 ,999)
(10 ,999)
(100 ,999)
(899 ,999)
(999 ,1)
(999 ,10)
(999 ,100)
(999 ,899)

はすぐに分かるとして,その他のパターンについて,ループ回数の上界を得ようとしたのですが,全然思いつきませんでした.

本来の互除法であれば,フィボナッチ数列上の連続する2数を与えた時が最もステップ数が大きくなるパターンになるはずですが,各操作で定数倍ですらない,rev(x)という操作が入ることで大小関係が変化して,値をの評価が難しいような気がします.

誰か知ってるか,思いついた方がいらっしゃったらぜひ教えてください.

 

 

いんし受かりました

えー.院試受かりました.

ざっくり言うと,線形代数をえいってやって,微積をがーってやって,多項式をがちゃがちゃしました.

英語は過去問が手に入らなかったので(著作権のアレ),英弱全一のボクは地味にびびってました.なんとかなりました.

 

それでやっと,院試勉強という無から解放されたわけなんですけれど,そうすると逆に大学院入ってからまともにやっていけるかがすごい心配になってくるわけなんですよね.ほんとに受かっただけって感じな気がしてきています.ほとんど試験問題以外の内容は問われなかったので.

ひとまずは,

加群,局所化とかその辺と,代数幾何の初歩の初歩,そのあたりに関係する代数的アルゴリズムについて勉強します.QEとかはお話ぐらいは知っておきたいです.

 

どれぐらいできないかっていうと,アティマクを最初から読んで簡単に詰まりそうな感じです.まだ何も読んでないんですけど.

 

なんだかんだいって,最近はこんなんですけれど,一応は前に進んでる気がするので,とりあえずは院入るまでに恥ずかしくないレベルまでは頑張って持っていきたいです.

 

AtCoder Beginner Contest 100に出ました

100回.すごい.

 

AtCoder Beginner Contest 100

100-200-300-400(ペナ5分)

 

198th (in rated 38th)

1000点(46:38)

パフォーマンス1600

1073 -> 1144(+71)

めっちゃがんばった.

 

次こそ水色になりたい...次回必要パフォは1578...ワンチャンあるか・・・?

f:id:lilies_lit:20180616231720p:plain

 

開始(0分).

めっちゃサーバー重い.記念回だからそれはそう.

beta版を使いそこねたのも原因らしい.(betaなら問題閲覧に関してはましだったっぽい).

 

問題が開けなくて2分間地蔵になる.

----------------------------------------------------------------------------------

A - Happy Birthday!

A<=8 and B<=8 でよい.Yay!って出力できなくて1WA出した(4分).

 

更に問題が開けない.大仏になってたらCが先に開けた.

----------------------------------------------------------------------------------

C - *3 or /2

・概要

長さNの数列の値すべてに対して,それぞれ「2で割る」か「3倍する」.ただし全部3倍するのは禁止.2で割ったあとに整数でなければならない.

 1 \leq N \leq 10^4 , 1 \leq a_i \leq 10^9

 

解いたやつ

Submission #2678168 - AtCoder Beginner Contest 100

 

3倍しても2の倍数の数は変わらないので,2の因数をいくつもってるか全部数えたら終わった.(13分+5分)

----------------------------------------------------------------------------------

ジャッジが止まっていて石像になりかける.Bが開けたので解く.

B - Ringo's Favorite Numbers

・概要

D,Nに対して,100でちょうどD回割りきれる正の整数のうち,N番目に小さいものを求める.

N \leq 100 , D=0,1,2

 

解いたやつ

Submission #2679758 - AtCoder Beginner Contest 100

 

全探索しました.CとBで一部プログラムを使い回せるところがあったので,実装が短縮できました.(2,100で何回割れるか,のところ).

どうやら,ここものすごい量のWAが出てみたいですね,あんまり良くわかってないんですが,”ちょうど”っていうところが”D回”と,"割り切れる(整除)"と変な掛かり方がしてややこしいんでしょうか...

(20分+5分)

 

----------------------------------------------------------------------------------

なんかこの辺でCのACがきた.

 

 

 

D - Patisserie ABC

・概要

N種類のケーキには3つのステータスx_i,y_i,z_iがあり,その中からM種類のケーキを選び,|x_1+\cdots+x_M| +|y_1+\cdots+y_M| + |z_1+\cdots+z_M|  が最大となるようにしたときの最大値を求める.

 1 \leq N \leq 10^3 , 0 \leq M \leq N, -10^{10} \leq x_i,y_i,z_i \leq 10^{10}

解いたやつ

Submission #2683185 - AtCoder Beginner Contest 100

 

 DPもあるみたいですが,実戦ではそれぞれ3つの絶対値が+と-のどちらに降ることで最大化するかで8通りすべて試しました.うまくやる方法がよくわからなかったんで...

入力の時点で,x+y+z,x+y-z,x-y+z, ...と8パターンの足し引きの仕方をした結果の和をすべて保存して,そのあと,8パターンすべてに対して,それぞれソートして大きい順に貪欲にM個取ります.8パターンのうちの最大値がansになるはずです.(41+5分)

 

上の入力は,

f:id:lilies_lit:20180617093539j:plain

 の中のどれかがoutputするべき解と一致するので,入力の段階で8パターンすべてに対応するものを考えようとしています.

 

dp解をあるみたいですが,逆に難しそう...i番目までのものが与えられたとき,j個使ったときの最大値をdp[i][j]とすればいい?って思ったんですが,これだと現状各パラメータが(絶対値は最大値になっているにしろ,)正になってるか負になってるかわからないから単純には行かないですよね...?(よく分かってない顔)

本番は考えると時間食いそうなんで,インプット部分でぺたぺた8個書いちゃいましたが,bitsetとかもろもろ使えばもうちょっときれいにx,-xのパターンを入力できたような気がします.

  1. xyz[1][i] = x+y+z;
  2. xyz[2][i] = x+y-z;
  3. xyz[3][i] = x-y+z;
  4. xyz[4][i] = x-y-z;
  5. xyz[5][i] = -x-y-z;
  6. xyz[6][i] = -x-y+z;
  7. xyz[7][i] = -x+y-z;
  8. xyz[8][i] = -x+y+z;

なにこれ.

 

 

AtCoder Beginner Contest 099に出ました

AtCoder Beginner Contest 099に出ました.とりあえず速報みたいなやつ.

AtCoder Beginner Contest 099 - AtCoder

 

配点は100-200-300-400(100分)

全完を決めたい感じ...

 -----------------------------------------------------------------------------------------------

A - ABD

ACしたコード

https://beta.atcoder.jp/contests/abc099/submissions/2645223

N < 999の場合を忘れて1WA出しました!w

もう6分(ペナ+5分).帰りたい.

 

 -----------------------------------------------------------------------------------------------

B - Stone Monument

ACしたコード

https://beta.atcoder.jp/contests/abc099/submissions/2646080

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

・内容

柱が999本あり,高さが西から順に1,1+2,1+2+3,...,1+...+999メートルである.

そこに雪が降り積もった.ある連続した柱を見たとき,雪の降り積もってない部分が左側の柱がaメートル,右側の柱がbメートルとなった.

雪のふりかたがどこでも等しいとき,雪の積もった高さを求める.

解のない入力は与えられない.

 ○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

 

 

b-aはそのまま柱の差で,b-a=kとすると,答えは(k-1本目の柱の高さ) - a.

なんか集中力がなさすぎて無駄に時間を食った.ここまで10分.

 

 

そこからCを解こうとするけど,Greedyじゃだめで,12~14あたりを避けてGreedyをやろうとして実装をミスって,指数のパターン少ないからバラせばいける(9^x + 6^y + z = Nと勘違い.全然違います)とか考えて,無限に時間を食った.もうさすがにこれは,ぎりぎりでC通してもだめだと思ってやけくそでDに移る.(経過60分ぐらい)

 

 -----------------------------------------------------------------------------------------------

D - Good Grid

Submissionしたコード

Submission #2650007 - AtCoder Beginner Contest 099

Submission #2650461 - AtCoder Beginner Contest 099

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

・内容(ざっくり)

N×NのgridにC色に塗られている.grid (i,j)に対して,(i+j) % 3の値で3色に塗り分ける.

XをYに塗り替えたときのコスト表D_{X,Y}が与えられるので,条件を満たすように3色に塗り分ける最小のコストを求める.

 ○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

 

なんでこいつ最初に愚直解投げてんだ.

とはいえ,色の塗り方は30*29*28通りだから全列挙で良くて,グリッドを読み込むついでに,余りが0,1,2になるものそれぞれに対して,色1~30がいくつずつ含まれてるかを抱えておくことで,色の塗り方1通りに対して,30*30*30で計算できそう.O(N^2 + C^4).無事に通った.と見せかけてN=1のコーナーケースが抜けて1WA.(73分+15分)

 

 -----------------------------------------------------------------------------------------------

C - Strange Bank

Submissionしたコード

Submission #2651464 - AtCoder Beginner Contest 099

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

・内容

銀行からN円を引き出す.

1回の操作で引き出せるお金が,1円,6円,6^2円,6^3円,...,9円,9^2円,9^3円,...である.ちょうどN円引き出すときの最小の操作回数を求める.

 ○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

 

ぜーったい許さんからな.

結局下から整数nに対して最小の回数に関してdp[n]を埋めていけばいけました.

1手で,ある n-x 円 --> n円にするxは,今回の範囲では,S = {1,6,9,36,81,216,729,1296,6561,7776,46656,59049}

しかないので,n-x >= 0になる範囲で,dp[n] = min (x in S)   dp[n-x] + 1.を考えればよさそうです.なんかうまいことやる方法はあるみたいなので(当然),今から解説を読んできます.

 

 -----------------------------------------------------------------------------------------------

374th 1000点(89:54+15:00 = 104:51)

とはいえ,水色パフォでレートはかなり上がりました.よかった.

f:id:lilies_lit:20180610225918p:plain