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

 

AtCoder Grand Contest 025に出ました

実は競技プログラミングを(ある程度真面目に)やり始めました.

はじめの頃はHaskellでやってたんですが,競プロと相性が悪すぎるのと,実装が難しくなりがちなのと,ググってもライブラリ等の情報が出てこないので諦めて冬ぐらいからC++にスイッチしました.

 

AtCoder Grand Contest 025

AtCoder Grand Contest 025 - AtCoder Grand Contest 025 | AtCoder

 

f:id:lilies_lit:20180604001042p:plain

f:id:lilies_lit:20180604001043p:plain

 

f:id:lilies_lit:20180604001456p:plain

(めちゃくちゃ古い記録も残ってますが)だいたいこんな感じなので,水色になるためにうんぬんといったブログも参考にしながら水色を目標に頑張ってます.

 

AGCはAを8分で通して虚無ってたんですが,これでも水色パフォ出るんですね.

B,C通したかったけど,普段500がまず通せない()

院試の勉強の合間にちょくちょくARC/ABC過去問埋めしますかね

テキサスホールデム

ポーカーやってます,テキサスホールデム

普段はオンラインか,つくば市のポーカーサークル 「つくぽか」

1周年記念のフリーロールがあったので出ました.

ポイント多めに稼げてたので10000点に5000点アドオンがあったけど,おかまいなくガリガリ削られました.

 

f:id:lilies_lit:20180527005158j:plain

f:id:lilies_lit:20180527005201j:plain

なぜかぎりぎり4位インマネしました.(エントリー20人)

フロップクアッズを引きました.びびった

 

やっぱりああいうシチュエーションだとpushレンジ狭くなりますよね,結構後半はアジャストできた気がするんですけど,だいぶもうESが小さかったのであんまり有効には効いてなかったかもしれません.ここ最近オンラインも長いことできてないので,久しぶりにカリッカリにバブルファクターが効いてる状況が楽しめましたw

 

院試が近いのでしばらくできなさそうなので,いいところで勝ててよかったです.

 

k[V]の性質と幾何的な対応

22歳になりました,あんまり嬉しくありません.誰かTwitterのアイコンください()

 

前回定義したk[V]は可換環にはなりますが,一般には整域にはなりません.例えば,

V = \boldsymbol{V}(x^3+xy^2-xz,yx^2+y^3-yz)

f = x^2 + y^2 -zと,g = 2x^2 - 3y^4zで,これに対応するpolynomial mappingをそれぞれ\phi,\psiとすると,これらはV上では0ではありません.((0,0,5) \in V , \phi(0,0,5) \neq 0(1,1,2) \in V, \psi(1,1,2) \neq 0)しかし,fg = \langle x^3+xy^2-xz,yx^2+y^3-yz \rangleであるので,Vの元を代入するとfg=0となります.ゆえに\phi\psi = 0となります.

 

ところで,affine varietyの性質として既約性というものがあります.V = V_1 \cup V_2 \rightarrow V = V_1 \ or \  V=V_2が成り立つとき,variety Vは既約であるといいます.

affine varietyとイデアルの間には,

あるイデアルの零点集合をとる\boldsymbol{V}と,あるvarietyによる多項式全てを0とするイデアルをとる\boldsymbol{I}による対応です.(代数閉体上ではradical idealとaffine varietyの間に全単射が存在します.)

特に\boldsymbol{I}(V)が素イデアルであるということと,varietyが既約であることが同値になります.

k[V]が整域である,という同値条件はこの中に入ります.

 

 

今までのイデアルとvarietyとの関係を使うことでは得られないメリットとしてどのようなことがあるのかをちょうど勉強しています...が当分院試勉強で進みそうになくてしんどい.

 

 

参考文献

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

 

polynomial mappingの表し方

あんまり体調がよくないのもあるんですが,院試の勉強が進みません.

 

前回は,polynomial mappingを定めるところまでいきました.

しかし,あるpolynomial mappingを表現する多項式(の組)は1通りでないことがわかります.

例えば,前回の例 variety V,W \subset k^3について,

 

 V = \boldsymbol{V}(y-z,z-x^3) \in k^3

 W = \boldsymbol{V}(y^3 - z^2) \in k^2

\pi_1(x,y,z) = (y,z)

 

では,多項式の組 (y,z)\pi_1を表現していました.

しかし,代わりに(y + (z-x^3),z + (z-x^3))という多項式たちを考えても,やはり同様に\pi_1を表現する,すなわちWの方程式y^3-z^2に代入すると成り立ちます.

(Vの点は\{(a,a^2,a^3) | a \in \boldsymbol{R} \}と書けるので,y+(z-x^3)は,a^2 + a^3 - a^2で,もう一方も同様に,z + z - x^3a^3となるので,y^3-x^2に代入するとa^6 - a^6 = 0Vの像はすべてWに含まれる. )

これは,つけたしたz-x^3の部分が多項式としては当然0ではないが,V上で考えると,どのような元を代入しても0になるので当然です.

一般に,多項式f,gが同じpolynomial mappingを表す. \Leftrightarrow f,gの各成分の差が\boldsymbol{I}(V)の元.

が言える.ただし\boldsymbol{I}(V)とは,Vの元を代入すると0になる多項式全体(のイデアル).

 

そして

\phi: V \rightarrow k (polynomial mapping)の集まりをk[V]と書く.

これはkが体であることから,\phi,\psi の和と積を\forall p \in Vに対して,

(\phi + \psi)(p) := \phi(p) + \psi(p)

(\phi \psi)(p) := \phi(p)\psi(p)

と定めると可換環になる.(よくあるやつ)

 

このように対応させるとvarieryの幾何的な様子が,たとえばこれが整域になることと,varieryが既約になることが同値になる,といったような代数的な扱い方ができるようになります.なるみたいです.

投稿テスト

はじめまして.数学科B4のlilies-litです.

はてなブログで数学ぺたぺたする人が最近増えて来たので,LaTeXの練習も兼ねて便乗したいと思います.

一応計算機代数を勉強しています(しようとしてる).周りにやってる人がほとんどいなくて残念....あと最近は競プロとか...

前にちょろちょろ書いたのがこっち.Dropbox - grobner.pdf

ネタらしいネタもないので,ちょうど今勉強している部分をブログにおこしたいと思います.勉強中なので間違っているところとかがあったら教えてください.

 

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

いきなりですが,アフィン多様体を定義します. 

Def. (Affine variety)
体をk,多変数多項式f_1,f_2,\ldots,f_s \in k[x_1,\ldots,x_n]とする.

このときAffine variety V \in k^nを次のように定義する.

V(f_1,\ldots,f_s) = \{(a_1,\ldots,a_n) \in k^n | f_i (a_1,\ldots,a_n) = 0.   (1 \leq i \leq s)\} 

多変数多項式環イデアルは有限生成であることから,ここでは多項式を有限個指定しているが,任意のイデアルを1つ指定しているのと同じことになる.

要するに,多変数多項式連立方程式の解と同じことです.

 

 

今ちょうど,このvariety上の関数について勉強しています.

 

Def. (polynomial mapping)

variety \ V \subset k^m, variety \ W \subset k^nとする.

 関数\phiがpolynomial mappingであるとは, あるf_1,f_2,\ldots,f_n \in k[x_1,\ldots,x_n]があって,すべての(a_1,\ldots,a_m) \in Vにおいて,

\phi(a_1,a_2,\ldots,a_m) = (f_1(a_1,\ldots,a_m),f_2(a_1,\ldots,a_m),\ldots,f_n(a_1,\ldots,a_m))

が成り立つことをいう.

 

つまり,飛ばした先の各成分が多項式の形でかける時をいいます.

 

 例として,

t,u \in \boldsymbol{R}でパラメトライズされた\boldsymbol{R}^3の部分集合であるtwisted cubicの表面を考えます.

V := \boldsymbol{R}^2.

 W := \{ (x,y,z) \in \boldsymbol{R} | \ x=t+u ,\  y = t^2 + 2tu , \ z = t^3 + 3t^2u \}.

このとき,次の\phiはpolynomial mappingになります.

\phi : V \rightarrow W , \ \phi(t,u) = (t+u,t^2+2tu,t^3+3t^2u)

 

このとき,(t+u,t^2+2tu,t^3+3t^2u)は,それぞれ多項式の組で,(この場合は同じ話ではあるが,)k^2 \rightarrow k^3写像とも考えられます.

そして,この多項式の組が\phiを表現するといいます. より一般に,n変数のm個の多項式の組によって得られる写像F : k^m \rightarrow k^nの定義域をVに制限して,その像がすべてWの元に含まれる(Wの方程式を全て満たす)ときにF\phiを表現するといいます.

 

前の例に戻り,例えばV,Wを,

 V = \boldsymbol{V}(y-z,z-x^3) \subset k^3

 W = \boldsymbol{V}(y^3 - z^2) \subset k^2

と取り直し, 写像\pi_1を射影,k^3 \rightarrow k^2 , \pi_1(x,y,z) = (y,z)とする.これはpolynomial mapping  V \rightarrow Wを与えます.

実際,\pi_1の定義域をVに制限すると,像の集合\pi_1(V)\{ (a^2,a^3) | a \in k \}となり,Wの方程式y^3-z^2に代入すると成り立ちます.

 

このようにvariety上の関数は多項式の組によって表現できるが,この表し方は明らかに一意ではなくなります.これについて(やる気が起きれば)次回にしたいと思います.

 

 

参考文献

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