Hack to The Future 2019 Qualifier
マラソンマッチは8時間もあるので、途中で食事をとることになります。 「コンテスト中に休憩をしてごはんを食べるというのはなかなか楽しそうだなあ」と思い、参加しました（謎）
予習もしくは予備知識
ツカモさんの記事を何となく読んでいました。 qiita.com
あと、山登り法とか焼きなまし法そのものは書いたことがなかったのですが、統計力学の勉強でイジング模型のMCMC（マルコフ連鎖モンテカルロ法）を書いたことがあって、あと量子アニーリングなるものについて友達に教わったことがあったりして、お気持ちは少しわかる程度の予備知識がありました。マラソンマッチは初めてだけど、本当に初めてではないみたいな感じです。
競プロしてるけど統計物理知らない（特に若い）競プロer向けに↑の話を紹介すると、統計力学のシミュレーションのMCMCでは温度を固定して、コスト的に損をする状態変化も一定確率で許すようなマルコフ連鎖を作ります。ここでいうコストは物理だとエネルギーに置き換わります（低いほうがコストは得という扱いです）。マラソンの焼きなまし法だとここで温度を下げていくことでエネルギー的に損をする遷移を許さないようにしていくことで最適解を目指します。一方、統計力学では温度T>0のときの分布そのものにも興味があります。どういうことかというと、Tを固定して変化していく状態に沿って物理量の平均や分散を計算することで比熱だとか磁化率だとかが計算出来ちゃったりします。そして温度を変えながらそれらを繰り返すことで、強磁性・常磁性相転移、つまり温度の低い鉄は磁石になるけどある温度を超えると磁石じゃなくなるという現象（の本質的モデル）をシミュレーションで再現できちゃいます。しかも実装は簡単ですから、興味のある方はやってみるとよいとおもいます。以上は知ってることだけざっくり書いたけど、ほかにもいろいろ競プロerのみなさまにとっても興味を惹かれることがあるはずです（適当）
最初の一歩
First ACを狙って問題文をろくに読まずに全部.で出すなどしました。壁がないのでWA。
制約を読んでからいったんPython3で80000なんちゃら点の壁＋.を提出。 最後はJavaで書こうと思っていたので後々直すことを想定しつつ、やはりツカモさんブログのコード例を参考にしながら...だけの解を出すコードをJavaで書く。 参考にするといいつつちゃんと参考にできておらず、static変数を無数に使うことになる。マラソンの場合何度も書き直したりモジュールの一部を置き換えたりすることがあるから、短時間のアルゴよりは書き方を考えないといけないですね。
拙速編
次にシミュレーターを書く。愚直にロボットを動かし、カウントを増やし、最後に数えるというもの。けっこう重い処理なのはわかっていたけど改善しようとするのは後回しにした、というか考えたくなかった。自分の実力では4時間かけてようやくテストできるようになりそしてバグるというのがとてもありそうです。
そこでまず愚直に書いた。書いた後、自分の書いたシミュレーターにバグはないという信念のもと（謎）山登り法を実装する。スコアが下がる。いや、下がるわけないでしょ。シミュレーターをなぜすぐにテストしなかったのか？山登り法を一刻も早く書いてみたかったからですね。今回1度書いて満足したので次からは一歩一歩テストしながら進むことができるでしょう。
この時点でそこそこ疲れ始めており、シミュレーターのデバッグか、嫌だなあ。。。などと思い始めていた。まあやるしかないのですが。このあたりでビジュアライザーの存在を思い出す。最初よくわからずビジュアライザーにコードをサブミットし、WA。このへんで2時間経っており、デバッグ嫌だなあなどと思っている時点で休憩のしどきであることにようやく気付き、コンビニに出かけてココアとオレンジジュースを買ってくる。往復10分ほど歩けたので帰ってからやることを整理することができた。
シミュレータデバッグ編
ビジュアライザーの使い方を理解してビジュアライズするとまずロボットのカウントからして間違っている（やはりね）。そもそもLマスRマスの仕様が自分の理解とあっているか不安になった（S命令だったら実行しないという解釈もあり得るのでは？みたいな。）。質問投げようかとも思ったんだけど、ビジュアライザーのページのJavaScriptにシミュレーターが書いてあって、それを読んだ結果自分の理解があってるってわかりました。
そこがクリアできたので気を取り直して自分のコードを読み直していたのですがどこも間違っておらず（だからまちがってるんだって）、書き直したほうが早いという結論になった。書き直しにあたってはせっかくなのでビジュアライザーのJavaScriptを参考にさせていただいた。ビジュアライザーのコード読みやすかったです、ありがとうございます（読んだ人どれくらいいるんでしょう）。
そんなこんなで再実装が終わり、ビジュアライザーを使ってシミュレータが正しそうなことを確認できたので、すでに拙速実装していた山登り法を実行すると、その時点で11万点を超えることができ、満足した。この時点で18時を回っており、夕食を取ることにした。
焼きなましからの撤退編
夕食後は焼きなまし法を実装した。そうすべきだと思ったからではなくて、書いてみたかっただけですね。実際、シミュレーターが愚直であるため山登りのループ回数が1300回程度しかなく、そもそも局所最適に至れているかも怪しいわけで、焼きなましを試す段階ではなかったのでしょう。でもまあ、書いてみたかったので。。。
次回同じ状況でやろうと思うのは、ローカルで実行時間を30秒とかにして山登りの解が改善するかどうかの実験です。（これはうさぎさんのブログで学んだことです）改善しなければ少なくとも局所最適になっているので、そこを脱出するために焼きなます価値がありますが、今回の僕の場合は山登りしきれていない（と思う）ので、シミュレーターの最適化をすべきだったということだとおもいます。
これくらい論理的に考えて何をすべきかわかっていればさすがにシミュレーター高速化を試みたと思うのですが、状況がよくわかっていないとなんとなく自分が楽にやれそうなことややってみたいことをやってしまいますね。
というわけで、焼きなまし法で目立った改善はできず、時間をギリギリまで伸ばすなどして数千点の改善にとどまりました。この辺でやれることが尽きたので、風呂に入って撤退しました。撤退って決めても何か集中できることをしないと気持ちが撤退しきれないので、ゲームをして解説放送を待つことにしました。
まとめ
- 山登り、登り切っていますか？
- 今書いたところ、テストしましたか？
- 今すぐ休憩すべきじゃないですか？
ABC094: D - Binomial Coefficients
ABC094: D - Binomial Coefficients
問題概要
- 相異なるN個の正の整数から2つを選んで(a,b)とする。
- aCbが最大になるようなa,bを求めよ。
- N <= 100000
思考プロセス
- N ~ 106なのでO(N)もしくはO(NlogN)までしか許されないだろう。
- 2つ選ぶ組み合わせを全部試すだけでNC2 ~ N2となってしまうので、工夫を要する。
- というか、組み合わせの計算自体もO(1)ではできない。しかしコンビネーションの値は要求されておらず、最大を与えるa,bを求めれば十分である。（ヒント）
- aCbにおいてaを固定すれば、bはa/2にできるだけ近いものが最大値を与える。
- aを決め打ち（特定の値に決める）ときに最適なbを高速に求めることができれば、N通りのaを試すことで問題が解ける。
- aを固定したときのbは、あらかじめソートしておけば2分探索でO(logN)で求めることができそう。しかし少し面倒。
- よく考えると、bを固定したときにはaは大きければ大きいほどaCbが大きくなるじゃないか。
- ということはaは最大のものだけ取ればよく、その後a/2にできるだけ近いbを選べばよい。どちらもO(N)でできる。
提出コード
https://beta.atcoder.jp/contests/abc094/tasks/arc095_b
振り返り
- 「決め打ち」に気づいた時点で、aとbの両方の決め打ちを幅優先的に検討すれば、bの決め打ちというより決定的なポイントに早く気づくことができた。
- 「決め打ち」とは何か。1つまたは2つ以上の変数を固定することである。
- この問題は、要するに、2変数関数の最大値を求めよという問題である。そういう言い方をすれば、1つの変数を固定するということは自分にとっても「典型」だといえる。滑らかな多変数関数の最大値問題であれば、受験数学の微積分でもやっているし、大学でも何度もやっている。
- にもかかわらず、その点に気づかなかったのは、2項変数という整数引数関数かつ「組み合わせ」という意味を持つ関数であることに惑わされて、「2変数関数の最大値問題」であるという当たり前の視点が持てなかったからだ。
- 滑らかな関数の最大値問題と離散的な関数のそれとでは、1変数を固定した後の最大値の求め方が異なっている。しかし、1変数を固定するという考え方の有用性自体は共通している。
Summer Festival Contest 2018 (Division 2)
Summer Festival Contest 2018 (Division 2) - AtCoder
A - 夏祭り会議 (Summer Festival Meeting)
- 2番目以降3数の和はゼロに保たれる x[k] + y[k] + z[k] = 0 for k >= 2
- この式を使うと、if K>=2: x[k+2] = 0 ==> x[k] == 0が成立することが示せる。
- 制約よりi=1は解にならない
X,Y,Z = map(int,input().split()) x2=Y-Z y2=Z-X z2=X-Y if x2*y2*z2==0: print(2) else: x3=y2-z2 y3=z2-x2 z3=x2-y2 if x3*y3*z3==0: print(3) else: print(-1)
1 2 3
3
B - 太鼓の名人 (Taiko Expert)
- 最後のDの位置xと最初のKの位置yを比べればよい
- x>yならば0でx<yのときxとyの間にある?の数をzとするとz=y-x-1
- zのなかにDが何個あるかで場合分け出来るのでans = z+1
- 結局ans = y-x
L = int(input()) S=input() x = -1 y = L for i in range(L): if S[i] == "D": x = i if S[i] == "K" and y == L: y = i if x > y: ans = 0 else: ans = y-x print(ans)
C - 整数占い (Uranai Integer)
- f(x,y) = 2 + xy + 2x + 2yが結合律を満たす
- 同様に交換法則も満たす
- よって最終結果は順序によらないので1通り計算すればよい
- fにmodをつけても同じことがいえる
import Control.Applicative main = do getLine a <- map read . words <$> getLine print $ solve a modulo = 10^9 + 7 :: Integer solve :: [Integer] -> Integer solve = foldl1 (\x y->mod (2+x*y+2*x+2*y) modulo)
E - 石積み (Pyramid Piling)
- 実験する！
- 各次元について題意を満たす最小のsの組を全探索で求めてみる
- 実験コード↓
S=55 a = [i for i in range(1,S+1)] print(a) b=[] b.append(a) N=15 for i in range(1,N): x = 0 b.append([0 for _ in range(S)]) for j in range(S): x += b[i-1][j] b[i][j] = x #print(b[i]) ans=[] left=[] right=[] for k in range(N-1): flag = False for i in range(S): if flag: break for j in range(S): if flag: break if b[k][i] == b[k+1][j] and i*j !=0: print(k+1,i+1,j+1,b[k][i]) ans.append(b[k][i]) left.append(i+1) right.append(j+1) flag = True print(left) print(right)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55] 1 3 2 3 2 4 3 10 3 5 4 35 4 6 5 126 5 7 6 462 6 8 7 1716 7 9 8 6435 8 10 9 24310 9 11 10 92378 10 12 11 352716 11 13 12 1352078 12 14 13 5200300 13 15 14 20058300 14 16 15 77558760 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
これによりたぶん次のコードで通るであろうことがわかる。
N=int(input()) print(N,N+1)
AtCoderのPython3で許されるループ回数
ループが何回くらいだと間に合うのか、10**10を超えるとダメそうなのはさすがにわかるのですが、ボーダーがどのへんなのかしょっちゅうわからなくなります。そこで軽く確認して覚えておくことにしました。
まずはローカル環境で次のテストを実行します。
n回の単純ループで、ループ内は加算を1回するだけの、およそO(n)の中でもっとも早く終わる部類であろうコードです。
def loop(n): ans=0 for i in range(n): ans+=i return(ans) for i in range(10): print("Testing for n = 10 ^", i) %timeit loop(10**i)
Testing for n = 10 ^ 0
350 ns ± 0.911 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Testing for n = 10 ^ 1
814 ns ± 1.11 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Testing for n = 10 ^ 2
3.73 µs ± 30.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Testing for n = 10 ^ 3
39 µs ± 103 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Testing for n = 10 ^ 4
404 µs ± 643 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Testing for n = 10 ^ 5
4.14 ms ± 5.28 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Testing for n = 10 ^ 6
42.2 ms ± 90.2 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Testing for n = 10 ^ 7
427 ms ± 860 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
Testing for n = 10 ^ 8
4.24 s ± 23.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Testing for n = 10 ^ 9
43.2 s ± 411 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
108時点で2000msを超えていました。 AtCoderのコードテストに次のコードを投げ、上記の時間と大差ないかどうかを確認してみます。
def loop(n): ans=0 for i in range(n): ans+=i return(ans) loop(10**7)
- 終了コード 0
- 実行時間 609 ms
- メモリ使用量 5484 kb
ローカルだと427 msだったので、3割くらい厳しくなりましたが、大きくは違わないですね。
結論
107はきわどい、108はアウト。106以下は少し余裕アリ。
AtCoder Beginner Contest 105
AtCoder Beginner Contest 105に出ました。最近競プロの精進ができていなくて不安でしたが、4完できてうれしいのでブログを書きます。解法ではなく考えのプロセスを書くようにしてみます。
A - AtCoder Crackers
トランプのカードを全部配るようなものを想像すれば、差は0か1かのどちらかであり、差が0になるのはNがKで割り切れるときのみです。
提出コード
N,K=map(int,input().split()) if N%K == 0: print(0) else: print(1)
B - Cakes and Donuts
ちょっと数学をしたくなりますが、誘惑をこらえて制約をチェックし、4ドルの数と7ドルの数についての全探索をします。その際両方0であるようなものに対してNoを出力することに気を付けます…と書いているときに制約でNが0でないことに気づきました。
数学の経験値がプログラミングの経験値よりも多い人は、数学をする誘惑に負けずに全探索でできないか考えることが大切だとおもいます。 また、最初から全探索を考えるだけでなく、いったん数学的な考察をして何か面白い事実に気づいた時点で、その面白い事実を踏まえた別な全探索ができないかを考えることも大切だと思います。ぼくはこの後者を忘れがちです。
提出コード
N=int(input()) if N<4: print("No") exit() for i in range (26): for j in range(15): if N == 4*i + 7*j: print("Yes") exit() print("No")
C - Base -2 Number
問題文が難しくなりました。まずは問題文を理解し、サンプルを紙に書いて理解します。
どんな数でもこの方法で表現できるのはなぜだろう？と考えて、紙に手書きで1桁で表現できる数、2桁で表現できる数、...を列挙することで糸口をつかむことができます。ここで図を掲載すべきところでしょうが大変なので、文章で書きます。1桁で表現できるのは0と1のみです。2桁ではこの2つに-2をした数が増えるので、-2, -1が仲間に加わります。3桁までつかうとこれらの仲間に4を足した数である2,3,4,5が新たに仲間に加わります。ここまで手で紙に書いてみると、証明はともかくすべての整数がいつか仲間になることが腑に落ちるはずです。
具体的に表示を求めるには、以上のプロセスを逆にたどっていけばよいです。 まず、元の数が初めて仲間に入った時の桁は1でなければいけません。次に、元の数から、今用いた(-2)の累乗数を除いた残りの部分を、残りの桁で表現するということを考えます。そのためには、「第n桁目ではじめて表現できるようになった数にその数が含まれているか」を判定して、結果に応じてその桁を1か0にする、桁数を減らして繰り返す、というような再帰的な手順になります。日本語が下手ですが推敲はしません。ごめんなさい。
提出コード
N=int(input()) left,right=0,1 parity=1 interval=[] ansList=[] digit = -1 for i in range(40): if parity == 1: interval.append((right-2**i+1,right)) else: interval.append((left,left+2**i-1)) if left <= N and N <= right: digit = i break else: if parity==1: left -= 2**(i+1) parity=-1 else: right += 2**(i+1) parity=1 #for (x,y) in interval: # print(x,y,y-x+1) while digit >= 0: left,right = interval[digit] #print(N) if left <= N and N<= right: ansList.append('1') N -= parity*(2**digit) else: ansList.append('0') digit -= 1 parity = -parity ans = "".join(ansList) print(ans)
D - Candy Distribution
区間の和がMで割り切れる区間が題意を満たします。区間の和ということから累積和を連想すべきです。そして今回はmodだけが問題なので、mod Mの累積和を使うとよいのではないかと思えます。
最初のサンプルで累積和の配列を手で書いてみると、何も足さないという場合を含めて0, 0, 1, 0という累積和の列になります。区間の和のmodが0であるというのは、この累積和の列において始点と終点の値が等しいという言い換えができます。ここでは0が3つあるので、1->2, 1->3, 2->3の合わせて3通りが解になるのだ、と考えるとつじつまが合います。
これを一般化すると、累積和を計算しながら、modの値ごとにそれが何個あらわれるかを記録しておいて、その個数をnとするときにn*(n-1)/2通りの解が存在することがわかります。それをすべてのmod値について加えたものが答えです。
提出コード
N,M=map(int,input().split()) A=list(map(int,input().split())) cumMods = {} cummod = 0 cumMods[cummod] = 1 cList = [0] for a in A: cummod += a cummod = cummod%M cList.append(cummod) if cummod in cumMods: cumMods[cummod] += 1 else: cumMods[cummod] = 1 #print(cList) import math ans = 0 for key in cumMods: #print(key,cumMods[key]) ans += (cumMods[key]*(cumMods[key]-1))//2 print(ans)
感想
modに慣れている人にとってはDが易しいのではないかとおもいました。Dの解き方は比較的すぐ気づけたものの、なぜかΣnを考えるべきところでfactorial(n)と書いてしまい、答えが合わずしばらく時間を浪費してしまいました。紙に色々書いてたら気づきましたが・・・。 Cの実装方針が少し悪かったのか、DよりもCに苦戦した気がします。解説をみたらよりスマートにできるでしょうか。
A - Cookie Exchanges
問題
思考過程
- 愚直にシミュレーションしてループを検出したら-1を出力する
- 初項を含まずにループする可能性があるので出てきた組み合わせをsetに入れていくのが確実か
- ループすることと無限に続くことが同値であるのは可能な組み合わせが有限個であることからわかる
- ループするか停止するまでの計算量は評価できるか？→できる。X+Y+Z=Sとすると自由度は2しかなく、109の2乗で抑えられる→この評価だと緩すぎる
- もう少し賢くやれるだろうか？
- 賢くとは→①上の方法をより賢く評価して間に合うことを示す②より賢い方法を考える
- 勘だけど②がよさそうなのでまず②から
- 手を動かす
- しばらくやってよくわからず
- よく考えると3数のMAX-MINは指数的に減少するのではないか→①の方針に切り替える
- 大きい順にMAX,MID,MINとすると、MIDがMAX,MINの平均に近い場合はMAX-MIDとMID-MINがおよそ半分になり、MIDがMINに近い場合にもMAX-MIDがおよそ半分になると考えられる
- 証明してから当初方針で実装するか証明なしで実装するか
- 証明できそう。3数の大きい順にL,M,Sとおくと、一回交換したあとのL',M',S'は、
よって、
となり、交換回数に対して指数的に減少する。よって、シミュレーション＋ループ検出による方法で、対数時間で解くことができると考えられる。
実装 Python3
#一回の交換をするための関数 def exchangeOne(x,y,z): return(((y+z)//2,(z+x)//2,(x+y)//2)) #全部偶数であるときにTrueを返す def isAllEven(x,y,z): return(x%2==0 and y%2==0 and z%2==0) A,B,C=map(int,input().split()) appeared=set() #一度現れた組み合わせを記録しておくための集合 appeared.add((A,B,C)) ans = 0 while isAllEven(A,B,C): A,B,C = exchangeOne(A,B,C) #ループを検出したら-1にしてシミュレーション終了 if (A,B,C) in appeared: ans = -1 break appeared.add((A,B,C)) ans += 1 print(ans)
Submission #2825945 - AtCoder Grand Contest 014 18msでACです。
実装2 C++
Pythonで書けるものをC++でも書けるようにするために練習。
#include<iostream> #include<algorithm> #include <tuple> #include <set> using namespace std; std::tuple<int,int,int> exchange(int x,int y,int z) { return std::make_tuple((y+z)/2, (z+x)/2, (x+y)/2); } bool isAlleven(int x,int y,int z) { return (x%2==0)&&(y%2==0)&&(z%2==0); } int main() { int A,B,C; cin >> A >> B >> C; std::set<std::tuple<int,int,int>> appeared; appeared.insert(std::make_tuple(A,B,C)); int ans=0; while(isAlleven(A,B,C)) { std::tuple<int,int,int> tuple = exchange(A,B,C); A=std::get<0>(tuple); B=std::get<1>(tuple); C=std::get<2>(tuple); tuple = std::make_tuple(A,B,C); if (appeared.find(tuple) != appeared.end()) { ans=-1; break; } appeared.insert(tuple); ans++; } cout << ans << endl; return 0; }
tupleとかsetの存在確認とかに苦戦しつつ何とか書きあがると、なんと1msで終了。やっぱり速いんですねえ。 Submission #2826138 - AtCoder Grand Contest 014
