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

 

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

 

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