絞り込み

最新の投稿

プログラミング Polygon
プログラミング

4200000000Hzでゴリ押す!!!(1)

何でもかんでもアルゴリズムとマシンパワー(主にCPU)でゴリ押します。そういう企画です。 「AtCoder水下位競プロerである私ならこういう思考をするぞ」っていうのを書きます(個人の意見ですが)。 2021年 東京大学(理系) 数学 問4(4)初回は東大の入試問題をやります。この問題をパワーでゴリ押すのは \(O(1)\) 番煎じになりますが、気にしないことにします。 実はこれ春休みの帰省中に数人で集まって解いた問題の一つで、僕だけパワーで解決しようとしてました。 問題\({}_{2021}C_{37}\bmod 4\) を求めよ。 本来はいろいろと前置きがあって、それを利用して引数を落として計算するんですが、そんなの私には分かりません。 さて、この問題をどうやって解いてやりましょうか。 解法1\({}_{2021}C_{37}\) を求める で、問題は \({}_{2021}C_{37}\) がでかすぎることです。どの程度か簡単に見積もってみましょう。 $$ \begin{aligned}  {}_{2021}C_{37}  &=\frac{2021 \times \dots \times 1985}{37 \times \dots \times 1} \\  &>\left(\frac{1985}{37}\right)^{37} \\  &>2^{212.58} \end{aligned} $$ 困りました。これでは128ビット符号付き整数(→GCCの__int128、C++ Boostのint128_t、Rustのi128など)でも収まらず、直接計算するのは厳しいです。 十分な長さの固定長整数型や多倍長整数を利用すれば出来ないこともないので一応やってみましょう。 Pythonのint型は多倍長なので何食わぬ顔で書けば実装できます。 n = 2021 r = 37 MOD = 4 ans = 1 for i in range(min(r, n - r)):   ans = ans * (n - i) // (1 + i) print(f'{n}C{r} = {ans}') print(f'{n}C{r} % {MOD} = {ans % MOD}') 実行結果は次のようになりました。 2021C37 = 10549453167137272405699426118445044729600037976073052501105621045645733312800275 2021C37 % 4 = 3 な、成程……! $${}_{2021}C_{37}=10549453167137272405699426118445044729600037976073052501105621045645733312800275$$ なんだ……!そして \(10549453167137272405699426118445044729600037976073052501105621045645733312800275\) を \(4\) で割ったあまりは \(3\) なんだ……! 多倍長整数での \(N \times M\) および \(N / M\) \((N\gg M)\) が \(O(\log N \log\log N)\) で計算できる(例えばFFTとNewton-Raphson法で実装)という仮定のもとで、 この方法による \({}_{n}C_{r} (r \leq n/2)\) の計算量は大きめに見積もると、 $$ \begin{aligned}&  O(\log {}_{n}C_{1} \log\log {}_{n}C_{1})   + \dots + O(\log {}_{n}C_{r} \log\log {}_{n}C_{r}) \\  =& O(\log n \log\log n) + \dots + O(\log n^r \log\log n^r) \\  =& O(r^2 \log n \log\log n) \end{aligned} $$ となります(この評価は割とガバガバですが)。 解法2\({}_{n}C_{r}=\dfrac{{}_{n}P_{r}}{r!}\) とオイラーの定理を利用する \({}_{2021}C_{37} \bmod 4\) を計算しようと思ったらこの方法が一番に思いつきました。 オイラーの定理は、競技プログラミング界隈では常識であるところのフェルマーの小定理の一般化です。 この定理は次のようなものです。 \(m\) 以下の正の整数のうち \(m\) に互いに素であるものの個数を \(\varphi(m)\) とする(言い換えれば、\(\varphi(m)=|\{n ; \gcd(m,n)=1, 1 \leq n \leq m\}|\))。 \(a\) と \(m\) が互いに素であるとき、 $$a^{\varphi(m)} \equiv 1 \pmod{m}$$ これの何が嬉しいって、分子 \(a\) と分母 \(b\) を \(\bmod m\) で別々に計算できるので、オーバーフローさせずに固定長整数型で計算できます。 そして分子に \(\bmod m\) における分母の逆元 \(b^{-1}\) を掛ける事によって求めることが出来ます。できるはずでした。 しかしよーく考えてみましょう。\({}_{2021}P_{37},37! \pmod{4}\) っていくつになるでしょうか? ……そうです。\(0\) になります。\(0\) に何掛けたって \(4\) で割ったあまりが \(1\) になることはありません。 すなわち、\(b \equiv 0\) の逆元 \(b^{-1}\) なんてものは存在しないので、この方法は使えません。 \({}_{2021}C_{37} \bmod (10^9+7)\) であれば求められるんですけどね…… 解法2'ただこれを回避する方法があります。 $${}_{n}C_{r}=\frac{a}{b},a={}_{n}P_{r},b=r!$$ とします。ここで、 $$ \begin{aligned}  a &=2^{\alpha_0} \times 3^{\alpha_1}   \times 5^{\alpha_2} \times 7^{\alpha_3} \times \dots \\  b &=2^{\beta_0} \times 3^{\beta_1}   \times 5^{\beta_2} \times 7^{\beta_3} \times \dots \end{aligned} $$ のように素因数分解し、約分することで $$ {}_{n}C_{r}=\frac{a}{b} =2^{\alpha_0-\beta_0} \times 3^{\alpha_1-\beta_1}  \times 5^{\alpha_2-\beta_2} \times 7^{\alpha_3-\beta_3} \times \dots $$ として計算することができます(\({}_{n}C_{r}\) は整数であるから、任意の \(i\) について \(\alpha_i \geq \beta_i\) が成り立つ)。 実際にこれを実装してみました。 from collections import defaultdict n = 2021 r = 37 MOD = 4 spf = list(range(n + 1)) for i in range(2, n + 1):   if spf[i] != i:     continue   for j in range(i * 2, n + 1, i):     if spf[j] == j:       spf[j] = i pf = defaultdict(lambda:0) for i in range(min(r, n - r)):   m = n - i   while m > 1:     pf[spf[m]] += 1     m //= spf[m]   m = 1 + i   while m > 1:     pf[spf[m]] -= 1     m //= spf[m] ans = 1 for p, v in pf.items():   ans *= pow(p, v, MOD)   ans %= MOD print(f'{n}C{r} % {MOD} = {ans}') 結果は当然解法1と同じく3です。 各自然数を \(O(\sqrt{n})\) で素因数分解して全体 \(O(r \sqrt{n})\) で求める方法もありますが、\(r \fallingdotseq n/2\) の場合も想定して、エラトステネスの篩と同様の前計算 \(O(n \log\log n)\) でSPF(Smallest Prime Factor)配列を求め、一つの自然数の素因数分解は \(O(\log n)\) で、全体 \(O(n \log\log n + r \log n)\) でできるようにしました。 全体の計算量は、\(O(n \log\log n + r \log n)\) です。 東大の問題の場合 \(r\) が小さいので微妙ですが、\(r \fallingdotseq n/2\) の場合はこちらのほうが早そうです。 解法3パスカルの三角形を使う 今回の大本命です。 解法2では計算途中で \(4 \equiv 0\) で掛けたり割ったりするから計算できなかったのが悪いので、いっそのこと足し算だけで求めてしまおうという考え。 $$ {}_{n}C_{r}=\begin{cases}  0 &(n<r) \\  1 &(r=0) \\  {}_{n-1}C_{r} + {}_{n-1}C_{r-1} &(\text{otherwise}) \end{cases} $$ この漸化式を使えば解けます。軽く証明してみましょう。 $$ \begin{aligned}  {}_{n-1}C_{r} + {}_{n-1}C_{r-1}  &=\frac{(n-1)!}{(n-r-1)!r!}+\frac{(n-1)!}{(n-r)!(r-1)!} \\  &=\frac{n-r}{n-r}\frac{(n-1)!}{(n-r-1)!r!}   +\frac{r}{r}\frac{(n-1)!}{(n-r)!(r-1)!} \\  &=(n-r)\frac{(n-1)!}{(n-r)!r!}+r\frac{(n-1)!}{(n-r)!r!} \\  &=\frac{n!}{(n-r)!r!}={}_{n}C_{r} \\ \end{aligned} $$ ではこれを実装します。 実装1: 再帰関数 漸化式と言えば再帰ですよね。見たまんま実装できるので良いと思います。 n = 2021 r = 37 MOD = 4 def comb(n, r, mod):   if n < r:     return 0   elif r == 0:     return 1   else:     return (comb(n - 1, r, mod) + comb(n - 1, r - 1, mod)) % mod print(f'{n}C{r} % {MOD} = {comb(n, r, MOD)}') でもちょっと待ってください。これ、comb関数の呼び出し回数どうなると思います? $$ \operatorname{call}(n,r)=\begin{cases}  1 &(n<r) \\  1 &(r=0) \\  \operatorname{call}(n-1,r) + \operatorname{call}(n-1,r-1) + 1 &(\text{otherwise}) \end{cases} $$ として定義した \(\operatorname{call}(n, r)\) 回になるんですよ。つまり少なくとも \({}_{n}C_{r}\) より大きい回数呼び出されます。 大きく見積もれば \(O(2^n)\)。\(n=2021\) で、実行していい計算量ではありません。 実装2: メモ化再帰 上の実装の問題点は、\({}_{n}C_{r}\) を計算するために、\({}_{n-x}C_{r-y}\) の計算を \({}_{x}C_{y}\) 回もしてしまっているということです。 ここで、メモ化という手法を取ることによって、各 \((x,y)\) に対して \({}_{n-x}C_{r-y}\) を \(1\) 回のみ計算すれば良いようにすることができます。 from sys import setrecursionlimit setrecursionlimit(3000) n = 2021 r = 37 MOD = 4 memo = [[None] * (r + 1) for _ in range(n + 1)] def comb(n, r, mod):   if n < r:     return 0   elif r == 0:     return 1   elif memo[n][r] != None:     return memo[n][r]   else:     memo[n][r] = (comb(n - 1, r, mod) + comb(n - 1, r - 1, mod)) % mod     return memo[n][r] print(f'{n}C{r} % {MOD} = {comb(n, r, MOD)}') コードを見ればそう難しい話ではないですね。単に二次元配列に計算済みの値を保存して、計算済みならば保存した値を返すようにしているだけです。 計算量は \(O(nr)\) ですが、空間計算量も \(O(nr)\) なのが痛いところです。 実装3: 動的計画法 動的計画法とは、問題を部分問題に分割し、自明な部分問題から遷移していって元の問題を解く手法です。 メモ化再帰もこれに含まれますが、単純再帰は含まれません(動的計画法の要件に計算結果の記録が含まれるため)。 ここでは、ボトムアップに(すなわち、自明な部分問題から順に)求める方法を指します。 パスカルの三角形の \(0\) 行目から \(n\) 行目まで順番に埋めていくイメージですね。 n = 2021 r = 37 MOD = 4 dp = [[0] * (r + 1) for _ in range(n + 1)] dp[0][0] = 1 for i in range(1, n + 1):   dp[i][0] = 1   for j in range(1, r + 1):     dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD print(f'{n}C{r} % {MOD} = {dp[n][r]}') これもやはり \(O(nr)\) です。 実装3': SIMD 普通に順次計算すると1クロックで1命令で、計算が終わってまた1命令出すんですが、その1命令に複数のオペランドに対する同一の演算を詰め込むことができます。これがSIMDです。 ベクトルの足し算や内積などが一番よく利用されている例だと思います。 さて、PythonでもSIMDをすることができます。 Numpyというライブラリを利用することで、配列同士の和を取ったりでき、自動でSIMDを使うようになります。内部的に PADDB 命令とかを出してるんでしょうね。 import numpy as np n = 2021 r = 37 MOD = 4 dp = np.zeros((n + 1, r + 1), np.int8) dp[0, 0] = 1 for i in range(1, n + 1):   dp[i, 0] = 1   dp[i, 1:] = (dp[i - 1, 1:r + 1] + dp[i - 1, 0:r]) % MOD print(f'{n}C{r} % {MOD} = {dp[n, r]}') 定数倍の高速化なので、計算量は変わらず \(O(nr)\) です。なお、この条件 \((n,r)=(2021,37)\) だとこっちのほうが遅くなりましたが、\((n,r)=(20000,1000)\) とかにするとめちゃめちゃ高速化できます。 まとめ答えは \(3\) です。 \(n,r\) がともに大きくなった場合は解法2'が最も高速で、\(O(n \log\log n + r \log n)\) で解けます。 高速素因数分解は覚えとけ。

> 内容を見る

電子工作 Polygon
電子工作

SDカードの耐久試験レポート

※この記事で行ったことは真似をしないように!!!何かあっても責任は取りません!!! ・・・ あらすじ 記憶媒体としてよく使うSDカード。HDDや磁気テープとは違い、これはフラッシュメモリを使用しているから磁気を近づけても問題はないらしい。 なんだかそう言われると、電気系としては限界を知りたいという気持ちが湧き上がってくる。 というわけで、どこまで無茶をするとダメなのかを知るためにも各種耐久試験を行ってみよう。 今回試験に用いるのは2GBのSDカード。確か初代3DSに付属してきたやつ。 ・・・ 定常磁界を印加してみる まずは定常磁界。これは単純にネオジム磁石でSDカードを挟むだけ。 一応、この磁石は公称値で磁束密度が260mTらしい。2600ガウスとも言える。 ここで、ふと昔に作った空芯コイルの存在を思い出したので、それも使ってみた。 結果は問題なし。普通に読み込めてしまった。 ・・・ 変動磁界を印加してみる 今度は変動磁界を印加して、誘起電圧による影響を見る。 変動磁界は適当に巻いたコイルを適当なコンデンサで共振させて発生させる。駆動回路は過去にも示したハーフブリッジ回路を使用した。 結果は問題なし。普通に読み込めてしまった。 ・・・ 冷凍してみる 今度はペルチェ素子とラジエーターを用いた水冷式冷却機で、一気にSDカードの温度を氷点下まで持っていく。ここで急激に温度を変化させるので、内部に結露とかが生じて何か影響が出るのかな?って予想。電気冷却だと冷凍庫とかじゃできないくらいの温度変化を起こせるのがポイント(数分で氷点下まで持っていける)。 結果は問題なし。氷の膜が張ったのにも関わらず、解凍すれば普通に読み込めてしまった。 ・・・ 変動電界に晒してみる 今度は変動電界にSDカードを晒す。ここで用いるのは少し前に自作した電界結合式ワイヤレス給電装置。極板間にSDカードを入れた状態で電力伝送を行う感じだけど、電界の影響は果たして・・・。 結果は問題なし。普通に読み込めてしまった。 ・・・ まとめ というわけで、なんとSDカードは無傷だった。頑丈過ぎやしないか・・・。 正直言って、コイルの上に置いたときに負荷電流が変化したから、こりゃ壊れたかなとか思ったが全然そんなことはなかった。というか、氷点下14度まで下げたのに普通に動いてるし。 もう、これを電気的に壊すには電子レンジに投げ込むしか無いんじゃないかなと思う。それか実験装置の大出力化(今で入力はMax10W)。 まあそういうわけで、よほどの環境に置かない限り電気的にはSDカードは破壊されないことがわかった。 というわけでSDカードの耐久レポートでした。 思ったよりも頑丈なことがわかったので、これからは物理的に破壊されない程度には雑に使っていこうと思う。 ちなみに、上記と同じことを磁気カードにやったら即データ消失すると思うから気をつけるように。

> 内容を見る

プログラミング Polygon
プログラミング

アプリ版 Minecraft サーバ制御ツールの制作

前回の「情クラ!」サイトの Android アプリ制作記です。(※この記事はブログからの転用です。) やっぱアプリ化、したいよね!!Webベースのツールを作ると、そのアプリ版を作りたくなる、ここまでがテンプレですよね。 今回は、ストアにリリースが手軽な Android アプリを制作したいと思います。 Android Studio 使いやすい...この時、プログラミングというものに触れてまだ半年もたっていませんでした。 なので初心者でも使いやすい Visual Studio Code を当時愛用していました。(今でも時々使っています) しかし今回アプリ開発というのもあり、デバッグのしやすいエディタを使うことにしました。 まぁもちろん Android Studio 一択になるわけですが。 JetBrains 社が開発したソフトウェアを初めて触ったのですが、 これがまた使いやすいソフトウェアで感動したのを覚えています。 (私が JetBrains 教徒になる話はまたいつか) さぁ開発だ!の前に、デザインを作っていきます。 スマホによってサイズが異なるので、対応できるデザインを意識して作成しました。 コーディング すべしぬべし今回の技術的な部分です。サーバの様子を取得するのとリクエストを送る機能をつけます!(大したことはしてませんが) まず、オンラインプレイヤーの取得部分です。 ホーム画面の上半分には、オンラインのメンバーが一覧でわかるようにしています。 今回、Minecraftの画像を取得するAPIを自作しました。 そこからAndroidに画像を取得するようにしています。 APIからの画像取得には、Picasso というライブラリを使用しました。 Picasso(公式サイト) https://square.github.io/picasso/ 具体的には、以下のような書き方でさくっとインターネットから画像取得ができちゃうものです!Picasso.get()   .load("https://jokura.net/api/getSkin?id=minecraft_id") // 今回作成したAPI   .into(face1);face1というのは ImageView の id で、APIから取得した画像を流し込んでくれます! また、プレイヤーがオンラインかどうかは、用意したAPIから返ってきた情報を元に表示を切り替えます。 APIからのGET・POSTメソッドには、便利な OkHttp3 などの便利なライブラリがありますが、この時(約2年前)は初心者だったこともあり、Java通信(HttpUrlConnection)で実装しました(笑) var connection: HttpURLConnection? = null var reader: BufferedReader? = null val buffer: StringBuffer try {   val url = URL( /* 通信するAPI */ )   connection = url.openConnection() as HttpURLConnection   connection.connect() // ここで指定したAPIを叩いています。   // 取得したデータを処理していきます。とりあえず取得した文字をbufferに。   val stream = connection.inputStream   reader = BufferedReader(InputStreamReader(stream))   buffer = StringBuffer()   var line: String?   while (true) {     line = reader.readLine()     if (line == null) break     buffer.append(line)   }   // ここからJSONに変換していきます。   val jsonText = buffer.toString()   val parentJsonObj = JSONObject(jsonText)       // オンラインメンバーの情報は、JSON内の top というキーの中に格納してあります。   val parentJsonArray = parentJsonObj.getJSONArray("top")   val detailJsonObj = parentJsonArray.getJSONObject(0)   // player1さんのオンライン状況が取得できました!   val player1: Int = detailJsonObj.getInt("player1")   return player1 } catch (e: MalformedURLException) {   e.printStackTrace() } catch (e: IOException) {   e.printStackTrace() } catch (e: JSONException) {   e.printStackTrace() } // 接続を切断してあげましょう。おつかれ! finally {   connection?.disconnect()   try {     reader?.close()   } catch (e: IOException) {     e.printStackTrace()   } } // 失敗した時はnullやエラーコードなどを返しましょう。 return null }一部抜粋・改変していますが、こんな感じでリクエストをかいています。 ちょっと脱線しちゃいましたね他にどんな機能を実装したのかみてみましょう!たぶんこちらの方が興味ありますよね (笑) トップ画面には、「バックアップ」と「再起動」の2つのボタンが用意してあります。 この2つのボタンについては後述します。 また、「稼働状況」を押すとサーバの現在の状況をみることができます。 今思うと、ここのデザインは Web 版と同じなので、 WebView で表示させるとよかったですね (笑) とりあえず、今回は xml ファイルで view を丁寧に記述しました。 今回のメインディッシュ本アプリのメイン機能は、なんといってもこの2つです! トップに設置されている「バックアップ」「再起動」の機能について説明します。 この Activity の開始と同時に、バックエンドと通信して 再起動 または バックアップ が実行できるか確認して、表示を切り分けます。 実行できない例としては、 - サーバが停止している - 他のユーザが現在処理を行っている - 処理実行後のクールタイムにある のいずれかですね。右上の更新ボタンで最新情報を再取得できます。 今回、神経を使ったのは処理部分でしたなんといってもサーバ関連で怖いのが、リクエストが同時に送られることですよね。 今回、サーバを制御できるプラットフォームが複数あるため、他のアプリやWebサイトから同時にリクエストが送られた場合、最初のリクエストのみ通す必要があります。また、再起動やバックアップなどが実行された後は、クールタイムを設ける必要もあります。 そういった、さまざまなリクエストを処理できるように、情クラ!ではバックエンドのAPIを用意し、そこからサーバ処理を行っています。 リクエストが失敗した場合には、その理由をエラーコードで返しユーザに通知しています。 実行可能の状態でボタンを押した場合でも、バックエンドでキャンセルされた場合その旨のトーストが表示されます。 2年の月日を経て...前回の記事 でも述べた通り、情クラ!はサービス終了しました。 今回、"プログラムの整合性" というものを勉強できた、サービス開発だったと思います。 他にも Minecraft 関係で得た知見はかなり大きいものだったので、今後何か一般向けのサービスに繋げていきたいと思います。

> 内容を見る

プログラミング Polygon
プログラミング

Minecraftサーバ リモート制御サイトの制作

プログラミングを始めた頃に構築した、Minecraftサーバのリモート制御ツールの開発体験記です。(※この記事はブログからの転用です。)Minecraft っていいよねMinecraft って、複数人でプレイすると沼ですよね。 今や大陸内には高速道路が広がり、複数の大陸間には水上橋が建築されています。(やばすぎ) ある日、Minecraft のサーバ管理者になった最初はローカルでサーバを建ててプレイしていましたが、 プレイヤーがどんどん増えてきたため、Google Cloud Platform(GCP)でサーバを立てることにしました。 これが、「情クラ!」という Minecraft サーバの誕生のきっかけです。 いつどこでも Minecraft サーバで遊べる環境が完成しましたが、しかし1つ大きな問題が発生しました。 Google Cloud Platform(GCP)が、まだ365日無料トライアルだった頃の話です。 当時は n1-standard-1 プラン(仮想 CPU 数: 1, メモリ: 3.75 GB)を使用していたため、大人数が長時間プレイしていると動作がもっさりしてくるのです。 サーバ管理者だった私は、毎度 SSH 接続してサーバを再起動していました。 ですがここは、ぜひ技術の力で課題解決をしよう!ということで、Minecraftサーバを誰でも簡単に制御できる、Webアプリケーションを作成することになりました。まずは完成品をどうぞ 最初に実装したのは、「ホーム」のお知らせ機能と「サーバ状況」の機能です。 モバイルファーストのデザインですが、レスポンシブ対応させています。 ホーム: プレイヤーが自由に建築報告を投稿することができますサーバ状況: サーバの起動・停止状況やオンラインメンバーを確認できますここで、少し技術的な話をしましょう一応そういうブログ( ?)なので、今回 Minecraft サーバと連携したノウハウについて記述しておきます。 Minecraft サーバでは、ある特定のパケットを受け取ると、現在のサーバのステータスを返す機能が搭載されています。 これは、Minecraft のマルチサーバ 一覧画面などで使用されています。 まず、クライアント側が Handshake パケットを送信します。(以下 wiki の情報) さらに続けてリクエストパケットを送信します。その応答パケットとして、サーバが以下のようなJSONを返します。{ "version": { "name": "1.16.1", "protocol": 47 }, "players": { "max": 12, "online": 5, "sample": [ { "name": "minecraft_name", "id": "4566e69f-c907-48ee-8d71-d7ba5aa00d20" } ] }, "description": { "text": "Hello world" }, "favicon": "data:image/png;base64,<data>" }また、このパケットを送信するためのライブラリとして、今回は以下のPHPライブラリを使用しました。 PHP-Minecraft-Query https://github.com/xPaw/PHP-Minecraft-Query実装した機能あまり技術的な話をすると長くなっちゃいそうなので、次に行きます。 他に実装した機能も紹介します。 ピクチャ: プレイヤーが自由に画像を投稿することができますオンラインユーザ: ホワイトリストに登録されたプレイヤーが表示され、サーバに入っているかどうかがわかります起動・停止: サーバをしばらく利用しない場合は、GCP課金対策のためにサーバを切ることができます再起動: Minecraft サーバを再起動させることができますバックアップ実行: Minecraft サーバのバックアップを作成します(毎日5:00に定期実行されます)バックアップ履歴: バックアップ履歴の一覧を表示します情クラマップ: 情クラワールドの建築物紹介が載っています情クラ!公式アプリ: 公式アプリへのリンクですみんなログインしよう今回サーバのコントロール機能が Web に公開されるので、ログイン機能を実装する必要があります。全員 Google アカウントを持っていたので、Firebase Authentication を使って Google ログインを実装します。 以下の公式ドキュメントを読むとよくわかりますよ(雑) Firebase Authentication(Google) https://firebase.google.com/docs/auth/web/start?hl=jaマイクラサーバのバックエンドはどうなってるの?Minecraft サーバでは、Node.js + TypeScript でAPIを構築しています。 以下は Minecraft を起動するルーティングの一部抜粋です。// --- Start Server ------------------------------------------------------------ router.post('/api/run/start', (req: express.Request, res: express.Response) => { const schema = Joi.object({ user: Joi.string().required(), }) const validation = schema.validate(req.body) if (validation.error) { post("不正なリクエストを拒否しました", "ユーザ固有IDが設定されていないリクエストが送信されました", 3) res.status(400).send('Bad request') return } statusAsync(req.body.user) .then(() => { startAsync(req.body.user) .then(() => { res.send('Success') }) .catch((err) => { if (err == 'failed due to run interval') post("起動コマンドを拒否しました", "前回の処理の実行から" + process.env.WAIT_SECONDS_FROM_LAST_PROCESS + "秒経過していないため、コマンドを拒否しました。", 2) else post("起動コマンドを拒否しました", "サーバが既に起動しているため、起動コマンドを拒否しました。サーバとの同期ができていない恐れがあります。[Err: startAsync()]", 2) res.status(400).send('Bad request') }) }) .catch(() => { post("起動コマンドを拒否しました", "既に起動しているため、起動コマンドを拒否しました。サーバとの同期ができていない恐れがあります。[Err: statusAsync()]", 2) res.status(400).send('Bad request') }) }) // -----------------------------------------------------------------------------軽く説明していきます。 まず、Joi という npm パッケージを利用して、送信されたクエリパラメータなどのバリデーションを行います。 そして、post( ) という関数がありますが、これはサーバのエラーなどを Discord のサーバに通知するための関数として用意してあります。 server.jar は screen 上で走らせているのですが、screen の二重起動にならないように初めに起動してもよいかのチェックも行っています。 また、実行系はシェルにまとめてあります。#!/bin/bash JARFILE=/home/jokura_server/minecraft/server.jar MEM=15000M cd `dirname $0` screen -UAmdS minecraft java -server -Xms${MEM} -Xmx${MEM} -jar ${JARFILE} nogui上記のファイルは、起動用のシェルです。 他にも再起動用やバックアップ用などのシェルも用意してあります。(下記は 再起動用)#!/bin/bash WAIT=30 STARTSCRIPT=/home/jokura_server/minecraft/start.sh SCREEN_NAME='minecraft' screen -p 0 -S ${SCREEN_NAME} -X eval 'stuff "say '${WAIT}'秒後にサーバを再起動します\015"' screen -p 0 -S ${SCREEN_NAME} -X eval 'stuff "say すぐに再接続可能になるので、しばらくお待ち下さい\015"' sleep $WAIT screen -p 0 -S ${SCREEN_NAME} -X eval 'stuff "stop\015"' while [ -n "$(screen -list | grep -o "${SCREEN_NAME}")" ] do sleep 1 done $STARTSCRIPT今現在の 情クラ!今は残念ながら、Webサービスを終了しています。 (Minecraft の活動自体はしています!) 2021年4月から、Minecraft サーバを別のメンバーが自宅サーバで建ててくれることになりました。 やはり GCP などの従量課金制のサーバで運用するには、かなり気を使ってしまうので正直解放されました。 かといって、情クラ!での活動はまだまだ続けていく予定なので、ぜひこのブログでも活動を共有していけたらなと思います!

> 内容を見る

プログラミング Polygon
プログラミング

新歓企画・競プロ部門の裏話

こんにちは。色々右往左往しながら競プロ企画の実施に漕ぎ着けました。 コードゴルフ開催中OUCRCとしての新歓期間は終わりましたが、4月末までコードゴルフを実施中です。せっかく部室に来て競プロをしてくれた人もいたのに、その時点で問題を選べてなかったのは問題でしたが。 GitHub Pagesで公開中です。 バックエンドはFirebase Cloud Firestoreです。無料でクエリ数も多いDBサーバーが使えるとはいい時代になったなあ。 図1:matsu_friends氏しか解いていないLeaderboard 是非問題を解いて、短くコードが書けたら送ってください。私が喜びます。 ※参加にはAtCoderおよびyukicoderのアカウントが必要です。 ボツ案実のところコードゴルフをするつもりではなかったのです。自分で作問した問題をアルゴ形式で出題するつもりでした。 ジャッジサーバーを立てよう最初は部室内にジャッジサーバーを立ててやろうと思っていました。 OnlineJudge 2.0というサーバーシステムを青岛大学が公開しているのでこれを使うつもりでいました。 これを考えている段階では帰省していてノートPCで検証していたわけですが、こいつを導入するとDockerが壊れる壊れる。 さっぱり訳がわからないのでこれは見送られました。 碌なのがないなら自分で作ればいいじゃない次に考えたのが自分でJavaかNode.jsかなどを使ってサーバーごと作ること。しかし3日でそれはどう考えたって無理(出来たとしても実行言語があまり多く用意できない)なのでボツオブボツに過ぎませんでした。 幻のOUCRC Moodleその次にOUCRC Moodleを爆誕させること。部室内の余ってるPCをサーバーにしてなんとMoodleを立てようとしたわけです。これができれば部内ウケはバッチリだったことでしょう。 しかしMoodleが案外曲者で、依存環境をまとめてインストールするような方法は用意されていません。 LAMP環境(Linux-Apache-MySQL-PHPのアクロニム)が要求されるわけですが(Nginx信者の私はLEMP環境にしようとしましたが同じことです)、MySQLの導入で詰まってやめました。 最終的にで、結果的にGoogleスプレッドシートに問題をまとめて手動入力することに……紆余曲折ありすぎる。 この段階でゴルフ形式にすることを決めました。アルゴ形式だと時間による有利不利の差が開きすぎると思ったので、解けることを前提としてそこからどこまで短くできるかというゴルフ形式ならよいと考えました。 そして泣きっ面に蜂で正課外活動の自粛要請(要請なのか禁止なのかは知りませんが同じこと)。 その結果、ソビエトロシアではお粗末なフロントエンドがWWWを公開した、というのが事の顛末です。

> 内容を見る

ガジェット/ハードウェア Polygon
ガジェット/ハードウェア

部室のキーボード掃除をしました

キーボードってトイレの便座より汚いらしいですね... そんな話を聞いてから大学の クソ汚い キーボードに触るときに一瞬躊躇するようになったぷらなりあです. ともかく,もうすぐ新歓ということで部室のキーボードを掃除しました. 【注意】 以下では一部汚い写真がありますので注意してください清掃手順1.まずキーキャップを外します. 頑張れば素手でもどうにかなりますが,専用の器具があると便利です. あと,キー配列が特殊なキーボードの場合,最初に写真を撮っておかないと元に戻すときに詰みます. 2.キーキャップを水に漬け込みます. 水には中性洗剤を溶かしておくとギトギトの油なんかも良く落ちます. 3.ボードの汚れを落とします. エアダスターや綿棒,ウエットティッシュなどを駆使して頑固な汚れと格闘します.(何気にここが一番大変な作業です) ちなみに,基板などが外せる場合は丸洗いしてしまうのも手です. 基盤やネジなどのパーツは失くさないようにします. 4.十分に乾かします. 水洗いしたパーツはよく水気を切って乾燥させます. 5.後は復元するだけです. 一応,各キーが正常に動作するかツールなどを使って確認しておきます.感想実際に掃除をしてみると,想像よりもはるかにキーボードが汚くて驚きました. 普段はキーキャップを外して本格的に掃除をすることはないと思いますが,定期的にやった方が良さそうです.(今のご時世だと感染症対策にもなりますしね) ということで,4月に見学に来てくれる新入生の皆さんはきれいなキーボードが使えます!(ぜひ見学に来てね)

> 内容を見る

ガジェット/ハードウェア Polygon
ガジェット/ハードウェア

~Windows 10を最低限使えるOSにする方法~危ない高速スタートアップ編

*この記事に書いてあることを実施した結果,生じた損害などに関して一切責任を負いかねます.自己責任で実施してください.高速スタートアップって何?高速スタートアップは,Windows 8.1から搭載されるようになったWindowsをより高速に起動するための機能です.HDDドライブが起動ドライブに設定されている場合に,OS起動が高速化される機能で,起動を速くするためにシャットダウン時にメモリやCPUなどの状態を保存しています.高速で起動できる代わりに規格の古い周辺機器が認識されなかったり,BIOSなどの設定変更を行ったあとにパソコンが正常に起動しなかったりする場合があります(参考:NEC LAVIE公式サイトより). 特にSSDドライブを起動ドライブにしている場合は効果が薄くなるため,わざわざ利用するほどの価値はありません.むしろトラブルの温床で,急にOSがクラッシュする原因になることがあります. SurfaceなどはSSDドライブを搭載しているので,あらかじめこの機能を無効化して,トラブルを避けましょう.もちろん,安定性より高速起動を重視したい方は,有効のままでもいいと思います. ちなみに,シャットダウンは遅くなります(画面が暗転してシャットダウンしているように見えますが,ハードウェアが動作し続けています). 高速スタートアップの無効化まずWindowsキーとRキーを同時押しします.すると ファイル名を指定して実行という項目が表示されるので,「control」と入力して実行します. コントロールパネルが開きます. 右上の検索ボックスに「電源」と入力して検索します. 「コンピューターを閉じるときの動作の変更」を開きます. 「現在利用可能ではない設定を変更します」をクリックします. 「高速スタートアップを有効にする(推奨)」のチェックを外します. 変更を保存して閉じます.これで適用完了です. 以上,安定性を脅かす高速スタートアップに関する話でした~.

> 内容を見る

プログラミング Polygon
プログラミング

競プロ環境構築#2 C/C++編

共通編の続きです。 WSLを導入したWindows10、またはMac OSやLinuxなどのUNIX系OSを前提にしています。 Ubuntuなどの仮想マシンが使えるならばこの限りではありません。 C++はどのような言語かC言語は説明するまでもないかと思うのでC++だけ。 C++は実行速度が速く、開発でも比較的よく使われる言語です。 イテレータや参照[1]によりポインタの操作がユーザーから秘匿されたり、クラスやテンプレートなどオブジェクト指向のパラダイムが持ち込まれたりして、C言語と比べて書きやすくなっています。 C言語との互換性が非常に高く、ポインタを直接操作することもでき、低級言語として扱うこともできます。 [1] int&型などのことです。関数にint*型で渡して関数内部で間接参照する、などとしなくても良くなっています。 2021年現在の競技プログラミング界隈では、事実上C++が標準語のようになっています。 AtCoderでは多くの言語を使うことができますが、他のコンテストサイトではあまり言語が多くなかったりします。 その中でもC++とJavaは標準的で、C++のほうが速いからか情報も多いです。 [独自研究?] そのため、競技プログラミングをするならC++は初心者におすすめの言語といえます。 C言語の環境構築もほぼ同じなので一緒に解説しますが、おまけ程度にしておきます。私は初心者がC言語を使うことはおすすめしません。 これはC言語しか習っていないうちの学生にも当てはまることなので、ぜひC++を使ってください。 一部の文法はC言語と似てるけど、便利機能モリモリで書きやすくて良いですよ。 はっきり言って、公式ガイドで環境構築できないくらいのスキルしか無いのであればC++に移行すべきだと思っています。 コンパイラ選びC++のコンパイラには主に以下の3つがあります。GCC(GNU C++ Compiler)ClangVisual C++GCCGNU Compiler Collectionの一部、GNU C++ Compiler。そのコマンド名g++からそのままg++と通称されます。 大抵のLinux OSは多くのGNUソフトウェアを標準インストールしており(GNU/Linuxの思想)、 GCC(ただしここではGNU C Compilerのこと)もそのうちに含まれています。 多くのLinuxユーザーはGNU C Compilerに馴染みがあるはずであり、GNU C++ Compilerはそれとほとんど同じオプションを利用することができます。 競プロer的に嬉しいのが、libstdc++のすべてのヘッダを読み込むbits/stdc++.hヘッダがあることです。 関数ごとにいちいちincludeディレクティブを書かなくていいことは記述速度最優先の競プロではプラスに働きます。 ただし実務で使うとブチ切れられることがあるらしいので気をつけてください。 多くの競プロerがGCCを使っており、なんやかんや一番おすすめです。ClangLLVMコンパイラ基盤の一部で、C、C++、Objective-C、Objective-C++の4言語のコンパイラ群です。 Macでは標準がClangらしいですね。他のことは何も知りません。 自分のPCにすでにClangが入っているか、GNUが嫌いでなければ特に使う理由はないと思います。VC++Microsoftが開発しているC++コンパイラですが、簡単に探した限りネイティブLinuxで使えるという情報は一切見つかりませんでした。当然ながらAtCoderでも対応はなし。その他Intel C++ CompilerやAMD Optimizing C++ Compiler、NVIDIA HPC SDK Compilersなどのプロセッサに最適化されたコンパイラ。当然競プロで使われることはまずない。 コンパイラのインストールWSL Ubuntu 20.04では必要ありません。gccもg++もGCC 9が標準搭載。やったぜ。 今後AtCoderで言語アップデートが入ってGCC 10になったときのためにインストール手順を書いておきます。 完璧にAtCoderと同じ環境にしたい場合はBoostが必要になりますが、私は使っていないのでここでは紹介しません。C++忙しい人向けsudo apt install g++-9複数バージョンの管理もしたい人向け# パッケージのインストール sudo apt install g++-9 # ここから蛇足 # シンボリックリンクの書き換え # 今回はalternativesというバージョン切り替えツールを利用する # g++が設定済みでないことをチェック update-alternatives --config g++ # update-alternatives: error: no alternatives for g++ # とか出ればOK # そうでないものが出たらそのままEnterを押す # g++にalternativesの設定を追加 # これをすると/usr/bin/g++ -> /etc/alternatives/g++ -> /usr/bin/g++-9のようなシンボリックリンクが張られる sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-9 5 g++ --version # g++10をインストール sudo apt install g++-10 # 優先度10なので、こちらのほうが優先度が高くなる sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-10 10 g++ --version # マニュアルモードでバージョンを戻しておく sudo update-alternatives --config g++C言語alternativesの部分はg++を全部gccに書き換えればいいだけなので省略します。sudo apt install gcc-9 コンパイラの使い方AtCoderのコンテストのルールのページを見ればコマンドが書いてあります。 https://atcoder.jp/contests/abc194/rules より引用。g++ -std=gnu++17 -Wall -Wextra -O2 -DONLINE_JUDGE -I/opt/boost/gcc/include -L/opt/boost/gcc/lib -I/opt/ac-library -o ./a.out ./Main.cppオプションの説明g++:コンパイラ本体です-std=gnu++17:C++のバージョンを指定します-Wall:標準的な警告をすべて出します-Wextra:その他の警告をいっぱい出します-O2:レベル2でコンパイル時最適化します-DONLINE_JUDGE:ちょっとややこしいので後述-I/opt/boost/gcc/include:Boostを#include<>の検索対象に含めます-L/opt/boost/gcc/lib:よくわからん-I/opt/ac-library:AtCoder Libraryを#include<>の検索対象に含めます-o ./a.out:出力ファイル名を./a.outにします./Main.cpp:入力ファイル名ですDオプション-DHOGE=FUGAは入力ファイルの先頭に#define HOGE FUGAとするのと同じ効果を持ちます。 FUGAが省略され-DHOGEと書かれた場合、#define HOGE "1"とするのと同じ効果を持ちます。 Includeガードでよくやるやつですね。 AtCoder Libraryを導入するAtCoder Libraryは AtCoderのジャッジで利用することができるオープンソースなC++ライブラリです (つまりC言語は対象外、移植は様々な言語にあります。 C言語版はここ。 アクティブなプロジェクトで、C++ STLのデータ構造(setやmap等)も移植対象とするようなので、 C言語使いの皆さん、是非プルリク出してあげてください)。 一般的な開発にはあまり使われない、しかし競技プログラミングでは重宝されるような機能が多数備わっています。 具体的にはmodintUnionFindSegtreeLazySegtreemaxflowmincostflowなどが含まれます(その他にも多数あります)。ダウンロードとインストールここのGitHubリポジトリからダウンロードしてきます。 zipファイルをダウンロードして解凍してもよいのですが、 WSL Ubuntuにはunzipはデフォルトで入っていないようなのでgit cloneでダウンロードすることにします。なぜgitはデフォルトで入ってるんだろう。使うからええんやけどさ# /opt下にダウンロード cd /opt sudo git clone https://github.com/atcoder/ac-library.git # インクルードできるかチェック g++ -I/opt/ac-library ./acl_include.cppacl_include.cppの中身#include <atcoder/all> int main() { return 0; }以上。 毎回-Iオプションを付けるのが面倒な方は、環境変数CPLUS_INCLUDE_PATHにパスを付け足せばよいです。 .bash_profileexport CPLUS_INCLUDE_PATH="$CPLUS_INCLUDE_PATH:/opt/ac-library" # .bash_profileを書くと.bashrcが読まれなくなるので、こっちから読み込むように指示 source ~/.bashrc適用できたか確認source ~/.bash_profile g++ acl_include.cpp エイリアスを設定する-Iオプションを付けるのが面倒な方は~、なんて言いましたが、どちらにせよ-std=gnu++17などのオプションはつけるべきです。 しかし面倒くさい。そのためのエイリアス。 .bash_aliasesにでも次のように付け足しましょうalias g++-ac='g++ -std=gnu++17 -Wall -Wextra -O2'とりあえずこれだけあれば十分かなと思いますが、好みに応じて増やしたり減らしたりしてください。 テンプレートの作成atcoder-cliのテンプレートに設定しておくとよいです。 私はこれで十分だと思っていますが、extgcdやdijkstraなど、ライブラリを付けたい方は付けてください。#include <bits/stdc++.h> #include <atcoder/all> using namespace std; // using namespace atcoder; using ll = long long; const ll MOD = 1000000007LL; // const ll MOD = 998244353LL; const vector<pair<int, int>> dpos4 = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; // const vector<pair<int, int>> dpos8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); return 0; } stdc++.hのプリコンパイルbits/stdc++.hを使うとコンパイル速度はかなり落ちます。 何度もテストする場合、それぞれの機能ごとに逐一includeしたほうが良いかもしれません。 少なくとも、手元環境で使う場合はプリコンパイルしておきましょう。# sudoをエイリアスで書き換えるというヤバいことをするので新しいシェルに入る bash # エイリアスの末尾がホワイトスペースのとき、次のトークンがエイリアスかチェックするらしい # g++-acエイリアスを使わない場合はこれをする必要はない # CPLUS_INCLUDE_PATHを設定済みの場合-Eオプション(環境変数を引き継ぐ)は必須 # 参考:https://qiita.com/homines22/items/ba1a6d03df85e65fc85a alias sudo='sudo -E ' # 本体部分 for header in `find /usr -type f -name 'stdc++.h'`; do sudo g++-ac $header done # 立ち上げたシェルから抜ける exit # PCHが生成されたことを確認 find /usr -type f -name 'stdc++.h.gch' 次回予告次回はPythonです。こちらで検証に成功すればnumbaの導入までやりたいですね。

> 内容を見る

ガジェット/ハードウェア Polygon
ガジェット/ハードウェア

~Windows 10を最低限使えるOSにする方法~Web検索編

*この記事に書いてあることを実施した結果,生じた損害などに関して一切責任を負いかねます.自己責任で実施してください.Web検索って何?インターネットを使って検索すること自体は,皆さん誰もが行うことであり,レポートの参考文献を探しに行くこともあるでしょう.Windows 10では,標準でタスクバーに検索バーが表示されています. この検索バーからコンピュータのアプリ,ファイルなどを検索できますが,Windows 8.1以降Web検索ができるようになっています.しかしこのWeb検索,Bing検索なんです! え?Bing検索に問題があるの?って思う人もいるかもしれませんが,問題大アリです.知りたい情報が出ない知りたい情報が出ません.これが致命的です.プログラミングをする人がプログラミングのための質問や情報を漁るとき,最初の1ページでどれだけの情報に出会えるか.Google検索は7割は役にたちそうな情報を提示してくれますが,Bingは3割も提示してくれません.人前だといつか恥をかく予測候補というものがあります.例えば「安倍●三」と入れると「安倍●三 ホームページ」とかそういうのです.Bing検索は,この予測候補が致命的で,他人を罵ったり,禁止用語が入っていたり,色々悲惨です. 本当?って思う人は「安倍●三」をBing検索に入れてみるといいでしょう.→https://www.bing.com 他にも,二次元のキャラクターを検索しようとしたときの予測候補がアウトです.例えば「渋谷凛」(アイドルマスターのキャラクター)を入れてみるといいでしょう.きっと後悔します. 検索のデモンストレーションとかでリアルタイムに検索しているときにこんな検索候補が出たら,疑われてしまいます.僕たちは紳士なのです! 良い子は黙ってGoogle検索上記の致命的な2つの問題点を抱えない検索エンジンで「Google検索」があります.必要な情報を手軽に手に入れられる検索エンジンです.→https://www.google.co.jp Windows 10のWeb検索で,Google検索を使う方法がありますが,そもそもWeb検索のせいでアプリやファイルの検索が遅くなってしまうので,Web検索はWebブラウザを開いて行うほうが効率的だと思います. 一応,やりたい人もいるかもしれないので,Google検索をWindows 10のWeb検索に導入する方法に関するページへのリンクも置いておきます.→https://www.tipsfound.com/windows10/06011 この記事では,Windows 10のWeb検索自体を無効にし,高速化を図ります.そのため,Google検索したい場合にはWebブラウザ「Google Chrome」を導入することをおすすめします.間違ってもMicrosoft Edgeなんて使わないでください. Web検索の無効化この設定では,Windowsに搭載されている「グループポリシー」機能を使用します.「グループポリシー」は主に企業のPCで使用されている,施設全体のデバイスの設定を統括管理するための機能です.WindowsのProエディション以上で使用できます(Homeエディションではできませんが,情報統括センターからWindows 10 Educationのライセンスを取得できますので,それでアップグレードすれば使用できます.大学構内に行けるようになってから試してみてください.生協からSurfaceを購入した人は元からProエディションなのでその必要はありません). まずWindowsキーとRキーを同時押しします.すると ファイル名を指定して実行という項目が表示されるので,「gpedit.msc」と入力して実行します. この「グループポリシーエディター」が表示されます.コンピューターの構成>管理用テンプレート>Windowsコンポーネント>検索を開きます. 「Webを検索したり[検索]に(以下略)」ポリシーを設定します. ちなみに,Cortanaうぜぇって人は「Cortanaを許可する」ポリシーも設定しておきましょう.永久追放できます. 「Webを検索したり[検索]に(以下略)」ポリシーを 有効 で設定してください. 「Cortanaを許可する」ポリシーを 無効 で設定してください. 設定できたらグループポリシーエディターを閉じます. 先程と同様にWindowsキーとRキーを同時押しして,ファイル名を指定して実行を呼び出し,「gpupdate」を実行します.黒い画面が表示され,少ししたら消えます.これで適用完了です. 以上,検索バーの動作を高速化する方法でした~. 追記正しく設定してもWeb検索が表示されるバグがある模様です.無能.

> 内容を見る