競プロ(Python)で巨大な数を扱うときは注意しよう（自戒）
普段競技プログラミングでPythonを使っているのですが、想定解（？）でもTLEになる場合があります。 その時は定数倍で高速化するらしいのですが、ちょっと特殊（？）なパターンに遭遇したので備忘録。
結論
- Pythonのintはデフォルトで28byteだよ
- これを超えるとメモリを再確保するよ
- 毎回やってるとおっそいよ
詳細
やらかした問題はTypical DP ContestのE-数です。 典型的な桁DPで、
dp[i][smaller][mod] := ( i 番目まで選んだ時の答え(Dの倍数) ) ただし、smallerNより小さいかどうかのフラグ、modはDで割ったときの余りを示す。
とすれば解けます。
自分が提出したソースコードはこんな感じ。
MOD = 1000000007
D = int(input())
N = [int(x) for x in list(input())]
dp = [[[ 0 for _ in range(D) ] for _ in range(2) ] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
max_lim = int(N[i])
for l in range(2):
for m in range(D):
lim = 9 if l else N[i]
lim = 9 if l else max_lim
for d in range(lim+1):
if l:
dp[i+1][l][(m+d) % D] += dp[i][l][m]
elif d < lim:
dp[i+1][1][(m+d) % D] += dp[i][l][m]
else:
dp[i+1][l][(m+d) % D] += dp[i][l][m]
print((dp[len(N)][0][0] + dp[len(N)][1][0] -1) % MOD)
オーダー的にはO(nD)(nはNの桁数)になるので、問題ないはずです。
が、制約上限の値を入力するとPyPyで提出してもTLEになってしまいます。
しょうがなくC++で再実装を行っているときに、オーバーフローを考慮した実装を行ったことでようやく気づきました…。
巨大な数値をそのまま扱っているせいだ、と。
Pythonのintはデフォルトで28Byteですが、メモリが許す限り拡張し続けます。 演算するたびに新しくメモリを確保…を繰り返していたらそりゃ遅いです。 なので、dpを更新するたびにmodを取ることにしました。 修正後のコードはこんな感じ（一部抜粋）
(~~略~~)
for d in range(lim+1):
if l:
dp[i+1][l][(m+d) % D] += dp[i][l][m]
dp[i+1][l][(m+d) % D] %= MOD
elif d < lim:
dp[i+1][1][(m+d) % D] += dp[i][l][m]
dp[i+1][l][(m+d) % D] %= MOD
else:
dp[i+1][l][(m+d) % D] += dp[i][l][m]
dp[i+1][l][(m+d) % D] %= MOD
(~~略~~)
TLEだったのが最大300ms強になりAC。ちなみにローカルで実行したら半分くらいの時間になりました。
研究でも競プロでも個人的な開発でもPythonを多用しているので、制限なしintに甘えてましたね……今後気を付けたいと思います。
Fujitsu Primergy Tx1320 M3でおうちESXiを構築した件
こんにちはこんばんは！ しまりすです。
以前から自宅鯖ほじい！！かっこいい！！！！と思っていたのをついに実現しました。 備忘録も兼ねてTx1320を選定した理由とESXiをブートするところまで書きます。
動機
現在研究室内サーバの管理をしており、それを通じてインフラの楽しさに気づきました。
さすがに研究室サーバをいじくりまわすわけにはいかないので、自由にいじれる環境がほしいなぁと思い導入に至りました。
実は研究室ではProxmoxを使っているのですが、どうせなら違う仮想化基盤も触ってみようってことでESXiを使います。
実機購入編
自宅で使うので、低消費電力かつうるさくないものがいいです。 入手性等も考えると、
あたりが候補になるかなと思います。
結局、ヤフオクでハードウェアRAIDカード付きのPrimergy Tx1320 M3が売っていたのでこれにしました。
スペックはこんな感じ。
ネット上にESXiの動作報告記事が見つからなかったので不安でしたが、どうやらカスタムイメージを配布してくれているようなので問題なし。
仮想化基盤を作るにはメモリとストレージが足りないので以下を追加購入しました。
- SAMSUNG M391A2K43BB1‐CTD
- 16GB 2枚
- 東芝 MQ04ABD200 2TB 2.5インチ
- RAID1を組むので2台
- 要るかといわれたら要らんけどロマン
- 2.5インチHDD用ミリねじ
- HDD届いた～！組むぞ～！って時にないことに気づいた
- すぐPC工房に駆け込んで、M3x4mmのミリねじを購入
初期設定
iRMC
富士通PrimergyシリーズにはiRMCと呼ばれるリモートサーバ管理チップが搭載されています。
ブラウザ経由でアクセスできる便利な機能なので、これを設定します。
Tx1320 M3には3つのEthernetポートがあるのですが、このうち1つがiRMC専用ポートです。
下の画像の一番上のRJ-45ポートが専用ポートです。
ここにLANケーブルを差し込んで、BIOS上でIPアドレスを設定したらおｋです。 DHCPも使えますが、今回は静的に設定しました。
RAID
購入したHDDを取り付けたはいいのですが、このままだと2つのHDDとして認識されてしまうのでRAIDを組みます。
PRAID EP400iは5つほど設定方法がありますが、今回はCtrl-R Utilityを使います。
Ctrl-R Utilityを使うには、UEFIではなくLegacy BIOSを使う必要があります。
BIOSを開いて、Advanced -> CSM Configurationの設定を以下のようにします。
ここまで出来たら再起動して、RAIDカードのPOST中にCtrl-Rを連打します。
すると、このような画面が表示されると思います。
起動したら、PRAID EP400iにカーソルを合わせ、F2キーを押下、Create Virtual Driveを選択します。
以降画像が切れていることが多いですが、汚い自室が映ってしまっていたのでご勘弁を…
RAIDレベルを選択し、アレイを組みたいドライブを選択します。
OKを押すと、こんなポップアップが出ますが無視してOK
これでRAIDアレイの作成は終わりです。
Escキーを押してCtrl-R Utilityを終了しましょう。
Esxiのインストール
VmwareからPrimergy製品用にカスタムされたESXiのインストールイメージを用意しましょう。 https://customerconnect.vmware.com/jp/downloads/details?downloadGroup=OEM-ESXI70U2-FUJITSU&productId=974
＊カスタムイメージを使ってインストールすると、ライセンスが評価モードになるので60日以内に無償ライセンスか有償ライセンスを入手して適用してください
USBやCD-ROM等に焼いて、Tx1320に接続します。（詳細は省きます）
あとはインストーラの指示に従ってインストールするだけですが、ここで注意があります。 ESXi 7.0から、新規インストールする場合はOS領域のパーティションを最大128GBも取るようになりました。 個人的に利用するサーバではこんなに領域を持っていかれては死活問題なので、最小サイズでインストールします。 以下の記事の手順でインストールすると、OS領域を8GBに抑えることができます。
確認
設定or DHCPで取得したipアドレスにブラウザでアクセス
できた！！！（実はすでに仮想マシンをいくつか立てていました）
