すゅん/Суюнのメモ帳/裏紙

またの名をゴミ捨て場

MMA Contest015に参加してきた話

自己紹介

はじめまして、電気通信大学Ⅲ類機械システムプログラム所属、とりあえずで決めた名前を引きずっていたらとうとう最近同じ発音の名前の人が後輩に現れてしまってそろそろ改名を考えているしゅん/Сюнという者です。

いろいろやらかして留年してしまい、システム上は4年生ですがまだ研究室に入っていません。頑張らないとですね。

AtCoderではstunniitaとして参加しています。現在は茶色です。

atcoder.jp

電通大をあまり知らない人向けの情報:電通大のⅢ類というのは理工系で、一見プログラミングとは何の縁もなさそうに見えますが、実は数値計算や深層学習をやっている研究室もあったりします*1

MMA Contestとは

電通大のサークル、MMA*2がときどき開催しているオンラインのコンテストで、自分も何回か参加したことがあります。

詳しい説明は以下のリンクに丸投げします。

mma-contest.connpass.com

今回、電通大の教室で開催するとのことで、久々に参加してみることにしました。

当日までの話(自分語りなのでスキップ推奨)

去年の8月頃に一度レート570くらいで停滞してこの辺が自分の限界かなと思ったのと、留年した原因の一つとして勉強以外のこと(つまり競プロとか)に集中してしまったというのがあり、しばらく中断していました。

それからしばらくして、AtCoderで言語アップデートが行われてJuliaがちょっと速くなるらしい*3という話を聞き、ちょっとJuliaの練習がてら春休みにunratedで参加してみたりしました。

(Juliaが数値計算とか実験レポートに使えそうというのと、あと文法が自分好みなのが理由)

とはいえ新学期が始まってからは学業に集中するため再び中断することに…といったところにオンサイトコンテストの話がTwitterで流れてきたのです。

が、ここで問題が…。yukicoderではJuliaが使えないのです*4

そこでJuliaの代替品を色々調べていたところ、mypy+型ヒントを使ったPythonが最適という結論に至りました。

そんなわけで本番1ヶ月前くらいから練習のためABCに再び参加し始め…すると運が良かったのかレートが660くらいまで上がりました。

これはもしかして緑まで届いてしまうのでは…?という自信たっぷりの状態で当日を迎えることに。


が、その自信はポッキリと折れることになります。

当日、会場にて

  • なんかひとがいっぱいいる。
  • 運良くコンセントが近くにある席に座れたので、途中で買った延長コードは役に立ちませんでした…。
  • 中にはぬいぐるみを持ち込んでいる人もいました。そういう文化の存在は知らなかったので、もし次の機会があったら何か持っていこうと思います。
  • 問題は全部で12問あり、ABCでは半分のD問題までは解けることを考えると、6完が目標かなぁ…と本番直前で決めました。

結果

まさかの2完で終わりました。こんなの嘘でしょ…何故なんですか…。

以下、各問題についての感想というか解説もどきです。


A

yukicoder.me

これは簡単ですね。S[0] == S[1] and S[0] != S[2]をするだけです。

B

yukicoder.me

繰り上がりをしないということは、各桁について

  • 0+0=0
  • 0+1=1
  • 1+0=1
  • 1+1=0

だけをやればいいとわかります。

つまりXORですね。Pythonでは^で計算できます。

また、Pythonではint(input(),2)とすることで2進数の文字列で整数を受け取ることができます。コンテスト中に知りました。


ここまでは順調だったんですよ…ここまでは…。

C

yukicoder.me

12問あるうちの3問目としては少し凶悪過ぎると思います(微おこ)。 デレステの「We're the friends!」のMasterのレベルが22なのと同じくらいの詐欺です。

writerのイメージ図

まずやるべきことはx \times y \equiv f \ (mod P)となる yを求めることです。

さて、P素数のときに使える、mod Pでの逆元を求めるときに使う道具、皆は分かるかな?



そうだね、フェルマーの小定理だね。



 x^{P-1} = x \times x^{P-2} \equiv 1 \ (mod P)より、 x \times (f \times x^{P-2} ) \equiv f \ (mod P)となって、 y = f \times x^{P-2}  mod Pとわかります。

ここで直接y = f * x**(P-2) % PとするとTLEです。繰り返し二乗法というものを使います。

(ざっくり言うと、例えばある数の16乗を求めるのに 16回掛け算を行うのではなく、2乗して2乗して2乗して2乗する、として計算回数を減らす…といったやつのちょっとした応用です)

なんとPythonではpow(x,P-2,P)とするだけで勝手にmod Pをしながら繰り返し二乗法で累乗を計算してくれます。便利ですね。

というわけで yが求まったので、あとは 1以上 M以下の yと合同な整数の個数を求めるだけですね。これは少し計算すると(M-y) // P + 1個であるとわかります。これが答です。やったね






…と、その気になっていた俺の姿はお笑いだったぜ…。

(結局本番中には解けずに終了)






もう一度よく考えてみましょう。求めるのはx \times y \equiv f \ (mod P)となる yと合同な 1以上 M以下の整数の個数です。

さて、 tについての1次方程式 at = bを解くときにやらないといけないこと、皆は分かるかな?



そうだね、 a = 0での場合分けだね。



当たり前ですが、0には何をかけても0になるので、 a=0, b = 0であれば t 全ての実数 b \neq 0なら解なしとなります。

これと同じことをやらないといけません。

ついでにいうと、 y \gt Mとなる可能性もあります。この場合は当然ながら答は0です。

結局、まとめると以下のようになります。

if x % P == 0:
        if f == 0:
            print(M)
        else:
            print(0)
elif y > M:
        print(0)
else:
        print((M-y)//P + 1)


教訓:コーナーケースには気をつけよう!


D

yukicoder.me

なぁにこれぇ


解説によれば、これはグラフの問題なのだそうです。

…グラフってABCのEからしか出ないやや難しめの問題というイメージだったんですけど…。


ともかく、グラフはそろそろ練習しようと思ってたところなので、これは今後の課題ということで。

E

yukicoder.me

ウワーッ!!!!…となるけど、よく見たら P 素数と書いてあります。これならなんとかなるかな…

困難は分割しましょう。 N!  P の因数の個数さえわかってしまえば、それの N!^{N!} 倍が答です。

さて、 N!  P の因数の個数の求め方、皆は分かるかな?



わからなかったら調べましょう。ルジャンドルの定理というそうです。

要するに 1 以上 N 以下の整数のうち、 P の倍数の個数+ P^ 2 の倍数の個数+ P ^3 の倍数の個数+...で、式で表すと \sum_{i = i}^{\infty} floor(N / P^ i) となります。

無限級数ではありますが、 N \lt P^ i となる項は0になるのでどこかしらで収束します。

While文でやるのが良いでしょう。


次は、 N!^{N!} \ (mod 10^ 9 + 7 ) の部分です。こちらもやはり分けて考えます。 N! \ (mod 10^ 9 + 7 ) を求めてから {N!} 乗しましょう。

前者についてはmodをとりながらfor文でやる以外に方法はないと思います。たぶん…。後者はさっきも使った繰り返し二乗法ですね。再びpowの出番です。こちらもfor文でやってもよし、math.factorial(N)で一気にやるのもよしです(自分はこっちでやりました)。


あとは最初のやつと掛け算してmodとって、終わりっ!

制約は N \lt 10^ 5 なので、これくらい雑にやってもまぁ間に合います。やったね。*5



本番中はなぜか mod P していてACできませんでした。そんなことしてたら答が0になるに決まってるだろ!バカ!

F

yukicoder.me

ウワーーーーーーッ!!!!!!!!!転倒数!!!!わかりません!!!!!パス!!!!!!!!

G

yukicoder.me

左端から右端までDPか何かするのかなーと思っていたらなんとダイクストラ法なんだそうで…。

こういう2次元のやつからグラフにするタイプの問題*6のやり方がわかりません…。今後の課題その2。

H

yukicoder.me

二分探索で今引けるカードのうち最大のものを引くってやったらWA。そりゃそうか。

正解は半分全列挙。なんかやけにKが小さいと思ったら…。

I, J, K, L

見てすらいません。


乾燥した感想

コンテスト終了直後は問題と解けなかった自分に内心バチクソにキレかかっており、怒りのあまり爆速帰宅をしてしまいましたが、よくよく考えるとちゃんと真面目にやっていれば普通に解けていたと思います…。これは反省しないといけませんね…。

…競プロ力というよりむしろ数学力での敗北なのでは…?



いつもは自宅で参加している競プロのコンテストをリアルでやるというのは自分にとっては初めての経験でしたが、やっぱりみんなで集まってワイワイするというのは楽しいですね。自分はコミュニケーションに精神力を消費するタイプの人間なのであまりその恩恵を受けられないのですが…。

また、こういった競プロのイベントが電通大で行われるというのは、電通大生に競プロを広めたり、逆にプログラミングが好きな人たちに電通大を知ってもらうという点で、プラスに作用しそうな気がします。「電通大といえば?」に「競プロのイベントをやってる」が挙がる日が来る…かもしれません。そうなったらいいなぁ…。



もし次回があったらリベンジしたいです。(なんか夏頃にまたやるらしいという噂を聞いていますが…?)


脚注

*1:つい先日研究室見学の機会があって、そのときに知りました

*2:Microcomputer Making Association、だそうです。総合格闘技ではない。

*3:JuliaはJITコンパイルを採用しており、何回も繰り返すやつだと有利に働く反面、一回きりなど単純なやつの場合はあんまり役に立たず、AtCoderでは激遅と言われるPythonよりも実行時間が長くなることも日常茶飯事だった… だが、今は違う(ギュッ) Julia1.9では先にパッケージをコンパイルしておくことで初回実行時のタイムロスを減らすことに成功したのだ! …ていう解釈で合ってますかね?

*4:厳密に言えば使えるには使えるのだが遅すぎて使い物にならないらしい

*5:真面目に考えると、ルジャンドル部分がO(log N)で、残りの部分も合わせておそらくO(N + log N)になるはずです。間違ってたら教えてください。

*6:迷路をDFS/BFSするとかのやつです。