37.50.48

%20 の ブログ

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 した。

yukicoder No.491 10^9+1と回文

この記事は、yukicoder No.491 10^9+1と回文 の解説です。

N の桁数を L とする。
10^9+1 の倍数かつ回文数であるような 1 以上 N 以下の整数のうち最大のものを M とする。
M が求まれば、最終的な答えは簡単に求まる。

例えば、M=543212345543212345 (これを 54321... と表記する) の場合について考える。

10^9+1 の倍数かつ回文数であるような L 桁の整数のうち、

  • 5432x... のものは 54320... から 54321... までで 2 個
  • 上記以外で、543xx... のものは 54300... から 54319... までで 20 個
  • 上記以外で、54xxx... のものは 54000... から 54299... までで 300 個
  • 上記以外で、5xxxx... のものは 50000... から 53999... までで 4000 個
  • 上記以外で、xxxxx... のものは 10000... から 49999... までで 40000 個

であり、これらを合計すると 44322 個である。

10^9+1 の倍数かつ回文数であるような L 桁未満の整数のうち、

  • 10 桁未満のものは 0 個
  • 10 桁または 11 桁のものは 1... から 9... までで 9 個
  • 12 桁または 13 桁のものは 10... から 99... までで 90 個
  • 14 桁または 15 桁のものは 100... から 999... までで 900 個
  • 16 桁または 17 桁のものは 1000... から 9999... までで 9000 個

であり、これらを合計すると 19998 個である。

以上より、求める個数は 44322+19998=64320 である。

M を求めるには、M 候補を最初は (L 桁の) 0 にしておいて、上位の桁から順に floor((L-8)/2) 桁について、回文数になるように M を変更しつつ、M≦N を満たすように決めていけばよい。

10^9+1 の倍数かつ回文数であるような L 桁の整数の個数は、M の最上位の桁の値から 1 を引いたうえで、M の上位 floor((L-8)/2) 桁の値に 1 を足したものである。

10^9+1 の倍数かつ回文数であるような L 桁未満の整数の個数は、9*10^floor((i-10)/2) (i=10, 11, ..., L-1) の総和である。

これらの和が求める個数である。M が L 桁にならない場合、L 桁未満の数についてだけ考えればよい。

コード

$"='';
@M=(0)x(@N=<>=~/./g);
for($k=0;2*$k<=@N-10;++$k){
	@M[$k,$k+9,$#N-$k,@N-10-$k]=($|?9:$N[$k])x4;
	@M[$k,$k+9,$#N-$k,@N-10-$k]=($N[$k]-1)x4,$|=1if"@M">"@N"
}
$%="@M[0..(@N-10)/2]"+1if$M[0]--;
$%+=9*10**($_>>1)for 0..@N-11;
print$%,$/

正規表現の積

誰か解いて

追記ここから

時間制限: 2秒 / メモリ制限: 512MB

追記ここまで

問題文

[a-z.] のみから成る2つの正規表現 A, B が与えられる。
A, B に共にマッチするような文字列の集合全体を、[a-z.*|] のみから成る正規表現 C で表したい。
このとき、C に含まれる | の個数の最小値を答えよ。

入力
A
B

入力は以下の制約を満たす。

  • 1 ≦ |A|, |B| ≦ 10
  • A, B には、[a-z.] 以外の文字は含まれない。
サンプル

入力1

a
b

出力1

1

C を例えば a.*b|b.*a と表した場合、| の個数は1で、これが最小値である。

入力2

a.a
.b.

出力2

2

例えば aba|a.a.*b.|.b.*a.a と表せる。

入力3

.a.b
a.b.

出力3

2

例えば aabb|.a.b.|a.b.*a.b と表せる。

入力4

b.a.
.a.b

出力4

5

例えば baab|.abba.|b.a.b|.a.b.a.|b.a.*a.b|.a.b.*b.a. と表せる。
追記:赤で示した部分が抜けていたので追加した。それに伴い出力4を修正した。

入力5

confused
sed

出力5

0

例えば confused と表せる。