37.50.48

%20 の ブログ

√1+√2+...+√n

\(\displaystyle\lim_{n\to\infty}\left\{\left(\sum_{k=0}^n\sqrt k\right)-\left(\dfrac23n\sqrt n+\dfrac12\sqrt n\right)\right\}=-\dfrac1{\sqrt{e^\pi}}\) の真偽とその証明について知ってる人がいたら教えてほしい。

偽で、\(\zeta\left(-\dfrac12\right)\) になるらしい。

\(-\dfrac1{\sqrt{e^\pi}}=-0.207879\dots,\)

\(\zeta\left(-\dfrac12\right)=-0.207886\dots\)

CODE FESTIVAL 2018 の参加記じゃないやつ

これはたぶん CODE FESTIVAL 2018 の参加記ではないので読まなくていいです。

予選 A

4:58 で 2 完( AB )。C が分からなかったが(本戦ボーダーは ABD だったらしいので)C が解けていたとしても本戦には行けていない。
一方で、ネット上で交流があり会いたいと思っていた 2 人は本戦に行けることが確定していたので、もし予選 B で THANKS だったら辞退するかもしれないという感じだった。

予選 A があまりに酷かったので解いてない問題を点数の低い順に解いていこうと思った。
400 点埋めをした。
500 点埋めをした。
600 点埋めを途中までした。

予選 B

20:15 で 3 完( ABC )。3 完時点で 41 位タイ。D と E を見て D が分からないから E をいじっていたが結局分からず。
D と E がどちらもしばらく解かれず慢心してもよさそうだったので慢心していた。
最終的に 47 位タイだった。予選 A で通った人や社会人などを除いて数えると通っていたっぽかった(実際通っていた)。

前泊と後泊をすることになったのでせっかくだから前日や翌日に誰かに会いたいと思い、そのようなツイートをしたところ kimiyuki さんから「 golf(コードゴルフ)の会をしよう」と声がかかり、 kotatsugame さんと 3 人で集まることになった。
集まるタイミング的にもちょうどよいので食事会もすることになった。

前日

kotatsugame さんが東京に着くのが 19 時頃になるはずだったのでそのつもりで行動していたが、実際には kotatsugame さんは昼には東京に着いていた。
予定通り 19 時頃に合流し、食事をしようとしてサイゼリヤに向かったが、順番待ちの人が多すぎて一度は引き返してしまった。
席が多いので実はそんなに待たないのではという話になり、結局再度サイゼリヤに向かった。
順番待ちの椅子が 1 脚しか空いていなかったのでじゃんけんをして kotatsugame さんが勝ったが、AtCoder じゃんけんでは kimiyuki さんが勝ちなのでは?となったが普通にじゃんけんで勝った kotatsugame さんが座った。

食事が終わりカラオケ屋に行ったが、金曜の夜なので当然混んでいて順番待ちの人がいたが待ち時間は 10 分ぐらいだったのでそれなら待つかということになった。
部屋に入ると、コンセントが無かった。カラオケ用のモニターやら何やらのためのコンセントは使っちゃダメみたいなことが書いてあったので素直に従った。
ゴルフ会をすると言っても具体的に何の問題を解くかを決めていなかったので、ちょうど 1 週間前に yukicoder で出題された、自分が作問した問題である mod数列 を縮めることにした。
この問題は 2 人は既に解いていて、なおかつ 3 人とも縮めていなかったのでちょうどよかった。

自分はパソコンを開かずに 2 人に対して横からあーだこーだ言う感じで動いていた。
最短コードが Crystal によるものだったので、 kimiyuki さんが Crystal の環境を構築して言語内で縮むかどうかを試していた。
Perl に移植するだけで縮みそうだったので kotatsugame さんが移植したら縮んだ。
やっぱり Perl だよねという話になり、 kimiyuki さんも Perl で縮めたりした。
時間が 1 時間半しかなかったので 1 曲も歌うことなくゴルフも途中で終わってしまった。

ゴルフ会が終わり、少し駄弁った。
自分( x20 )は賞金を獲れるはずがないので kimiyuki さんに賞金は獲れそうですかと訊いたところ、赤もいるしまぁ無理でしょうみたいな応答があった。

解散してホテルに向かおうとして秋葉原駅から神田駅まで移動し、南口から出たかったが東口から出てしまった。
独り言で「分からない」などと言いながら歩いていると、道案内をしてくれそうに話しかけてくれる人がいたので、その人に南口までの道を訊いてホテルまで辿り着いた。

ホテルに着くと、部屋の照明の点け方が分からなかった。分からないのでフロントに戻って訊くと、説明があった(実はルームキーの裏側に同様のことが書かれていることに後から気付いた)。
照明を点けてパソコンを開いてここでようやくツイッターを見ることができた。
靴下の替えを持ってくるのを忘れていることに気付いた。

当日

起床はできたものの、眠すぎて何も分からなかった。
時間がなく、ホテルに付いているらしい朝食も摂れなかった。

道に迷わずに会場に着いた。
座席番号が 057(グロタンディーク素数)だったので当たりじゃんなどと思った。
交通費清算が去年の THANKS ではスマホを持っていないからという理由で紙での申請になったがパソコンじゃダメなのかと訊いたらパソコンでいいと言われたのでパソコンで申請した。

本戦

パーカーは 1400 点以上(配点は 300 300 300 500 600 600 700 900 1000 1200 )なので前から順に 4 完すればいいらしい。
去年は実質参加賞だったと聞いていたので思ったよりボーダーが高い印象を受けた。
無線 LAN が怪しかったので有線 LAN を繋いだがそれでも不安定だった。

A

いきなり分からなくなった。時間をかけて落ち着いてやったら通った。

B

log をとるだけなのだけどなんかうまくいかなかったので紙に書いて落ち着いてやったら通った。

C

折れ線グラフがどうなるかは問題文を読めば分かるので紙に書いてやった。実装でなんか変な感じになった気がするけど落ち着いてやったら通った。

D

何も分からない。順位表を見ると D を解いた人数が極端に少なく、E の方が簡単らしいので E を解くことにした。

E

この問題が一番簡単に感じた。
K が無ければ蟻本(の第 2 版の p.73 )に載っているプライオリティキューを用いる問題とほぼ同じなので K があってもプライオリティキューを用いると解ける。
解けたのでパーカーを得た。

F,G

サンプルが合わない。

H,I,J

開いていない。

順位表凍結時、kimiyuki さんが 2 位になっててすごいと思った。
kotatsugame さんも一時的に賞金圏内になっていてすごかった。
自分( x20 )の最終順位は 59 位で、目標は「 80 位とか 70 位とかをとれれば嬉しい」ぐらいだったのでだいぶ良かった。

昼~夕方

弁当を食べている途中で移動することになり、眠い時に食事を中断させられてパニックになった。夜は夜で食べ物が出るので結局弁当はゴミ箱に捨てた。
ルービックキューブタイムアタック」の入賞タイムが自己ベストよりも遅かったので挑戦した。何度か挑戦して 2 分は切れたが結局入賞はしなかった。
kimiyuki さんと話した。
「りんごの挑戦状」を適当に眺めた。

リレー

本来 1 チーム 10 人だが 9 人のチームだった。本戦順位のチーム内順位の「 9 位と 5 位」「 8 位と 4 位」「 7 位と 3 位」「 6 位と 2 位」がそれぞれ「 A 」「 B 」「 C 」「 D 」をペアで考察し、順位の低い方の人が実装するという作戦になった。
チーム内 6 位だったのでチーム内 2 位の leign さんとペアになって D に挑んだ。解法の理解に苦しんでいたので sugim48 さんにも教えてもらって理解できた。実装を始めてから分からなくなって一度戻ったがすぐに分かって一発 AC できた。
チーム全体の順位は最下位だったが楽しかった(食べ物に対する興味が低いのでもし上位になって肉がもらえてもあまり嬉しくない)。

ほとんどの時間で kimiyuki さんと kotatsugame さんと話していた。
そういえば chokudai さんと話していなかったなぁという感じで話した。AtCoder ステッカーをもらった。

終了後

会場を出てからもやはり kimiyuki さんと kotatsugame さんと話していた。
kotatsugame さんは CHUNITHM をしに行くということでここで別れ、 kimiyuki さんと共に行動することになった。

コンセントのあるマクドナルドに行き、そういえば AtGolfer の開発(改良)はどうなったのという話になり、pull request を送ったことがないので(しょうもない)pull request を送ってみようという流れになり操作してもらって送った。
マクドナルドが閉店時刻になったので店外に出て、その後も長い時間話していた。
kimiyuki さんは翌日には別の予定があるがそれは夕方からなので昼過ぎぐらいまでなら予定が空いてるということで翌日にも会うことになった。

神田駅の南口から出ることには成功したが、歩く方向を間違えて東口に辿り着いてしまったので引き返してホテルに向かった。
片言の日本語を喋ってくる客引きらしき人がいた。

翌日

朝食を摂る時間をとれなかったので食べずにゲーセンに向かった。
maimai が( 4 曲を期待していたが) 3 曲設定だった。
2 クレ目の途中で、初プレイの人が間違えて同じ筐体の隣側に来て Aime カードを当てて反応しなくて困惑しているようだったので隣(の筐体)が空いてますよと案内した。
ちょうど 2 クレ目が終わった辺りで kimiyuki さんが来たのでせっかくだから一緒にやってく?という感じで 1 クレ一緒にやった。

昨日とは別のマクドナルドに行ったらコンセントが無かった。まぁパソコン開かなくても話はできるしという感じで話していた。
「 staff only 」と書いてある扉がある方向に向かう一般客が多かったのが面白かった。
混雑時は食べ終わった人はとっとと出て行ってみたいなアナウンスがあったので店外に出た。

無印良品に行ったら「テレビで紹介されました」とかいう雑なポップがあった。

その後も話をしていたが kimiyuki さんがそろそろ時間だというので駅に向かった。一人で散策するつもりもあったが改札を通ってしまったので(眠かったので帰るべきではあるし)そのまま帰ることにした。

総括

話の通じる人と話すのは楽しい。

yukicoder No.673 カブトムシ

この記事は yukicoder No.673 カブトムシ の解説です。

\(n\) 年目の大晦日のカブトムシの匹数を \(X_n\)(ただし \(X_0=0\))とすると、$$\begin{eqnarray}X_n&=&(X_{n-1}+B)×C\\&=&C\cdot X_{n-1}+BC\cdot 1\end{eqnarray}$$となる。この遷移を行列で表すと、$$\begin{pmatrix}X_n\\1\end{pmatrix}=\begin{pmatrix}C&BC\\0&1\end{pmatrix}\begin{pmatrix}X_{n-1}\\1\end{pmatrix}$$であるので、\(X_D\) については、$$\begin{pmatrix}X_D\\1\end{pmatrix}=\begin{pmatrix}C&BC\\0&1\end{pmatrix}^D\begin{pmatrix}X_0\\1\end{pmatrix}$$で求まる。

あとは mod をとりながら繰り返し2乗法で行列累乗するだけ。

yukicoder No.638 Sum of "not power of 2"

この記事は yukicoder No.638 Sum of "not power of 2" の解説です。

a をなるべく小さくしたいので、可能なら a=3 にしたい。
b のとりうる最小値も a と同じく 3 なので、6=3+3 よりも小さい N は N=a+b で表せない。

以下、N≧6 について考える。

a=3 としたときに b=N-3 が 2 の整数乗でないという条件を満たしていれば、求める (a, b) の組は (3, N-3) である。
そうでないとき、a=5 とすると b=N-5 が条件を満たさないことはほとんどない。
なぜならば、N-3 と N-5(という、差が 2 であるような 2 数の組)がともに 2 の整数乗であるので、これを満たすような 2 数の組は (N-3, N-5) = (4, 2) 以外に存在しないからである。
つまり、N=7 のときは a=3 も a=5 もダメで、N≠7 のとき、求める (a, b) の組は (5, N-5) である。

まとめると、

  • N<6 または N=7 のとき -1
  • そうでないとき a=3 が OK なら (a, b) = (3, N-3)
  • そうでないとき (a, b) = (5, N-5)

となる。

「正の整数 x が 2 の整数乗である」は (x & x-1) == 0 で判定できる。

#232871

ll N;
{
	rd(N);
	if(N<6||N==7)
		wt(-1);
	else if(N-3&N-4)
		wt(3,N-3);
	else
		wt(5,N-5);
}

yukicoder No.619 CardShuffle

この記事は yukicoder No.619 CardShuffle の解説です。

考え方

問題を見ればセグ木を使えば解けることは予想できる。

セグ木に載せるべき「部分的な計算結果」どうしをつなげて掛け算をしたときの掛け算の影響範囲を考えると、「部分的な計算結果」は a+b+c の形をしていると都合がよいことが分かる。

セグ木の各ノードに a+b+c の形をした式の「 a, b, c の値」と「 + または * の演算子」を載せる。

数字カードはセグ木の葉ノードに対応し、演算子カードは葉でないノードに対応する。

数字カードは a+b+c の形にならず、値を 1 つだけもつ。また、値を 1 つだけもつものどうしを * でつないだ場合も値を 1 つだけもつ。

値を 1 つだけもつ場合は x-x+x のようにしておくと都合がよい。a+b+c の形になる場合は b は負になり得ないので、b が負であるならば値を 1 つだけもっていると判定できる。0-0+0 の場合は b が負にならないが、辻褄は合う。

a+b+c と d+e+f の掛け算については 4 通り考える必要があり、

  • b≧0 かつ e≧0 のとき a+(b+cd+e)+f
  • b≧0 かつ e<0 のとき a+(b)+cd
  • b<0 かつ e≧0 のとき cd+(e)+f
  • b<0 かつ e<0 のとき cd+(-cd)+cd

のようになる。一方、足し算については x-x+x のようにしておいたことにより場合分けが不要になり、

  • a+(b+c+d+e)+f

のようになる。

交換クエリにおいて、演算子カードの交換が発生し得るので、「カード列のインデックス→セグ木のインデックス」の変換ができると楽。

交換後の再計算の際に、値の入っていないノードとの計算をする場合がある。その場合は 0 との足し算をするようにすると楽。

入力の読み込み方

セグ木上を通りがけ順で移動しながらその場所に入力の値を載せていく。

入力を読み込む毎にインデックス変換用の配列にインデックスを入れる。

前処理としての計算も入力を読み込むついでにやってしまう(左側で再帰、真ん中で演算子を読み込む、右側で再帰、左右の計算結果どうしで演算、の順でやる)。

カード列のインデックス
               8
       4              12
   2       6      10      14
 1   3   5   7   9  11  13  15

 
セグ木のインデックス
               1
       2               3
   4       5       6       7
 8   9  10  11  12  13  14  15

交換クエリ

数字カードの交換の場合は交換したカードの親ノードから根に向かって再計算する。

演算子カードの交換の場合はそのノードから根に向かって再計算する。

質問クエリ

計算範囲の左端と右端から同時に根に向かって親ノードが一致するまで演算していき、それぞれの計算結果どうしで演算する。

実装例

#226631 一応この記事を書いている段階では最速らしい。

3の倍数を正規表現で

leading zero を許容しない十進非負整数は、

/^(0|[1-9][0-9]*)$/

と表現できる。これは、

/^(0|([1-9]0*)+)$/

と表現することもできる。

 

以下では、「数」は「 leading zero を許容しない十進非負整数」と同じ意味で扱う。

 

「 x が 3 の倍数である」と「 x の各桁の数字の和が 3 の倍数である」が同値であることは知られている。
ということは、「 3 の倍数の後ろに 3 の倍数の繋げたもの」も 3 の倍数である。
ということは、3 の倍数全体の集合を正規表現で表現できるはずである。

できた。

/^(0|(([147][0369]*([147][0369]*[258][0369]*)*([147][0369]*[147]|[258])|[258][0369]*([258][0369]*[147][0369]*)*([147]|[258][0369]*[258])|[369])0*)+)$/

 

いきなり結果だけ見せられても分からないので、単純なところから考える。

1 または 2 のみからなる数について考える。

  • 111 は 3 の倍数である。
  • 12 は 3 の倍数である。
  • 21 は 3 の倍数である。
  • 222 は 3 の倍数である。

よって、これらを 1 回以上繰り返したものは 3 の倍数である。

/^(111|12|21|222)+$/

少し変形しておく。

/^(1(11|2)|2(1|22))+$/

3 の倍数であるが上記に該当しないものについて考える。

/^(1(【A】)*(11|2)|2(【B】)*(1|22))+$/

【A】が 3 の倍数ならば、1【A】11 は 3 の倍数である。

  • 【A】が 111 のとき、1【A】11111111 となり、先頭から見て 111111 に分けることができるので考えなくて良い。
  • 【A】が 12 のとき、1【A】1111211 となり、先頭から見て分けられないのでこれについて考えれば良い。
  • 【A】が 21 のとき、1【A】1112111 となり、先頭から見て 12111 に分けることができるので考えなくて良い。
  • 【A】が 222 のとき、1【A】11122211 となり、先頭から見て 122211 に分けることができるので考えなくて良い。

【A】は 12、同様にして【B】は 21 と分かる。

よって、1 または 2 のみからなる数で、3 の倍数であるもの全体は、

/^(1(12)*(11|2)|2(21)*(1|22))+$/

と表現できる。

ここに 3 を加えると、

/^(13*(13*23*)*(13*1|2)|23*(23*13*)*(1|23*2)|3)+$/

ここに 0 を加えると、

/^(0|((1[03]*(1[03]*2[03]*)*(1[03]*1|2)|2[03]*(2[03]*1[03]*)*(1|2[03]*2)|3)0*)+)$/

ここに 4, 5, 6, 7, 8, 9 を加えると、

/^(0|(([147][0369]*([147][0369]*[258][0369]*)*([147][0369]*[147]|[258])|[258][0369]*([258][0369]*[147][0369]*)*([147]|[258][0369]*[258])|[369])0*)+)$/

となる。

yukicoder No.502 階乗を計算するだけ

この記事は、yukicoder No.502 階乗を計算するだけ の解説というより、自分が書いたコードの解説です。

 

作問者による解説にもある通り、この問題は、予め一部の値を計算しておいて、それを埋め込むことで解ける。作問者は「例えば1000個を埋め込む」と解説しているが、速い言語であればそこまでたくさんの値を埋め込む必要はない。

n が 10^9+7 未満の場合について、10^8 毎に区切って 11 個の値(0!, 10^8!, 2*10^8!, ..., 10^9!)を埋め込むと 500ms ほどで AC ということが tails さんの提出したコードから分かっていたので、ほぼ同じようなコードを提出したところ、なぜか TLE だった。

原因を探ったところ、m=1e9+7;s=1e8; という部分に問題があった。

これは何なのかというと、普通にコードを書くと 1000000007, 100000000 という値が 2 回ずつコード中に出現し、それだとコードが長くなるので、グローバル変数(型名を省略すると int 型になる)を初期化して(このとき暗黙の型変換が行われる)、それらの変数を 2 回ずつ使うことでコードを短くしようとした結果生まれたものである。

これを使うと何が悪いのかというと、(実際には初期化した以降で変数の値が書き変わらないものの、)変数で剰余をとると定数で剰余をとるよりも遅いという問題がある。

const を使うとこの問題は解決できる

 

というわけで、ここからコードを縮めるにはどうすれば良いかというと、まず埋め込みを減らしたい。最大で 10^8 回のループを回して 500ms より少し遅いということから、2*10^8 回のループを回すと TLE することが予想される(実際に TLE だった)。

なので、166666668 毎に区切って 6 個の値(0!, 166666668!, 333333336!, ..., 833333340!)を埋め込むことにした(ここでもし 166666667 毎に区切ってしまうと埋め込む値が 7 個(0!, 166666667!, 333333334!, ..., 1000000002!)になってしまい、最後の 1 個が邪魔になる)。

埋め込む値の中に 500000003 という値があったのでそれを 5e8+3 と書くなどして 167B まで縮んだもののまだ長い。

 

そこで、文字定数を使って 156B まで縮めた。文字定数というのは、通常は 'a' のように 1 文字をシングルクォートで囲って使うものだが、複数文字を囲って使うこともできる(コードゴルフでは、1 文字を囲う使い方は基本的にしない。例えば 'a' より 97 の方が短いので 'a' を使う理由が無く、'z'122 では長さが同じなので 'z' を選ぶ必要が無い)。

複数文字を囲った場合、ビッグエンディアンで 4 バイトの値が得られる。例えば、'(.&F' は (((40*256)+46)*256+38)*256+70 = 674113094 となる。

 

文字定数はコードを縮めるには確かに強力だが、'', が何回も出てきて長い。そこで役立つのが、文字列リテラルである。文字列リテラルが持つ値は文字列の先頭のアドレスなので、これを int* 型のポインタ変数に代入すれば、int[] 型の配列と同様の使い方ができる。

int 型の値は、リトルエンディアンで 4 バイトで表されるので、例えば、((int*)"****F&.(****")[1] は 70+256*(38+256*(46+256*40)) = 674113094 となる。

これで 144B まで縮んだが、文字列リテラルの中の \r がウザい(例えばタブは \t という表現を使わずに直に書けるのに対して、\r\n はそういうことができない)ので、166666668 毎に区切っていたものを 166666669 毎に区切るようにして、\r が不要な値を使うようにして 143B

 

繰り返す回数を表すのに使っていた変数 i が必要なかったのでそれを削って 136B

s の初期化は文字定数を使った方が短くて 135B

文字定数を直に使えばそもそも const m,s は必要なかったので 132B

n<mm は文字定数を使うよりも 1e9+7 の方が短くて 131B

xlong 型である必要が無かったので、long ni を削った時に空いた main 第 1 引数に入れて 130B

*a="\x01\x00\x00\x00M\xfb#\x07O\x0f\xed9`\x1d\xe17\xa6\xcbp%?y\x8d\x0e";
x;main(long n){
    scanf("%ld",&n);
    for(n<1e9+7?x=a[n/'\x09\xef!\xad']:0;n%'\x09\xef!\xad';)
        x=x*n--%';\x9a\xca\x07';
    printf("%d",x);
}

赤で示したものは実際には十六進数で表された文字コードの文字そのものであり、コピペでは正しく動かない。例えば \xed99 がエスケープシーケンスの一部と誤解され、\xd9 のような扱いになるからである。

 

この記事の公開後、lpha_z さんが 129B で AC した。