メモ

yukicoderでゆるふわgolf

atcoder橙になるまでにやったこと

少し前に橙になったのでポエムを書きます
青になるまで:atcoder青になるまでにやったこと - メモ
黄色になるまで:atcoder黄色になるまでにやったこと - メモ

黄色から橙になるまでにしたこと
・コンテストに10回くらい出た
・800点を半分くらい埋めた
・銀パフォを出した(!?)

なぜか最近AtCoderが数学コンテストサイトになったおかげでめちゃくちゃ伸びた。
対800点問題の戦績が6勝2敗と好調だったことが大きな要因であるように思う。
(青~黄色の間には800点は1度も通したことがなかったのに)

橙のラインはこんな感じ
・600以下を確実に解く。可能なら早解き
(600早解きに成功すればその時点でパフォ2000-2200がほぼ確定するので大事故がなくなる)
・700をだいたい解く
・800に勝ち越す
・900以上も問題を読んで解けそうなら解く

やはり蟻本は読んだことがないです。
読まなくても橙にすらなれます、と胸を張って言いたいところですが、多分読んだほうがいいと思います。
次回「atcoder赤になるまでにやったこと」は10^18+9年後の予定です。お楽しみに

位数Xのアーベル群

出典

この問題は「互いに区別できるX要素の集合に、アーベル群の構造を入れる方法は何通りあるか?」と同じになる。
これはOEISで検索すると見つかる。
A034382 - OEIS
項の数が少なく、求め方も乗っていないので、最初のツイートの制約で解くにはまだ足りない。導出を考えてみよう。

以下、単に群といえばアーベル群を指すものとする。
各記号を次の通り定める。
pは素数とする
C_n 位数nの巡回群 \mathbb{Z}/n\mathbb{Z}のこと
S(X) 位数Xの群の同型類の集合(各同型類とその代表元を同一視する) これはここだけの記号であり一般的なものではない
Aut(G) Gの自己同型群
GL(k,R) 可換環Rのk×k行列で可逆なものの集合
単に「元gの位数がn」といった場合は「ちょうどn」とは限らないものとする。(例えばC4の元は全て位数4である)


X=\prod p_i^{e_i}とする。
S(X)から群を1つとりGとすると、それと同型になるようにするには、どの元にどれを割り当てるかX!通り。……ではなくX!/#Aut(G)通り。
例えばC_3になるよう{0,1,2}に群構造を入れるとき、0を単位元にしたら、のこりの2つの元のどちらを1,2に割り当てても同じになるので。
ということで、求める答えは
\displaystyle{
\sum_{G \in S(X)} \frac{X!}{\# Aut(G)}
}
ここで、a,bが互いに素ならS(ab)=S(a)×S(b)であること、
GとG'の位数が互いに素ならAut(G×G')=Aut(G)×Aut(G')であることから
\displaystyle{
\sum_{G \in S(X)} \frac{X!}{\# Aut(G)}\\
=X!\prod_i \sum_{G \in S(p_i^{e_i})} \frac{1}{\# Aut(G)}
}
となる。
(これは\sum_{i,j,k}a_i b_j c_k=(\sum_i a_i)(\sum_j b_j)(\sum_k c_k)と同じ式変形)
位数p^eの群は、必ず\prod_i C_{p^{n_i}}^{k_i} の形で書くことができる。ここで\{n_i\}は狭義単調増加するようとるものとする。
位数の条件からe=\sum_i n_i k_iである。
巡回群は生成元の行き先さえ決めれば準同型が定まる。n_iの大きい方から考えることで、準同型が同型であるためには、C_{p^{n_i}}^{k_i}の生成元たちは送った先でもこの部分を生成していなければならないことがわかる。そのような割り当て方は
\displaystyle{
\# GL(k_i,\mathbb{Z}/p^{n_i}\mathbb{Z})=p^{(n_i-1)k_i^2}\prod_{j=0}^{k_i-1} (p^{k_i}-p^{j})
}通りである。
(n_i=1のとき、\mathbb{Z}/p\mathbb{Z}が体であることから「k次元ベクトルk本を一次独立に選ぶ」ことと対応するので総積部分が得られる。n_i \geq 2のときは、"1の位"をそのように決め、"pの位"から上は自由に決められるので残りの部分が得られる)
また各iについて、送った先でC_{p^{n_i}}^{k_i}にあたる部分以外は位数p^{n_i}であれば何を割り当ててもよいので、\displaystyle{
( \prod_{j\neq i} p^{\min(n_i,n_j)k_j} )^{k_i}
}通りとなる。
(例えばC2×C4×C8のとき、C4の生成元はC2の部分は自由に取れ、C8の部分は位数4の元4つの中から自由にとれる)

よって以上より
\displaystyle{
\# Aut(\prod_i C_{p^{n_i}}^{k_i})
=\prod_i \left( (p^{(n_i-1)k_i^2}\prod_{j=0}^{k_i-1} (p^{k_i}-p^{j})) ( \prod_{j\neq i} p^{\min(n_i,n_j)k_j} )^{k_i} \right)
}通りとなる。

ここで\# S(p^e)はeの分割数に等しいことがわかるので、これは対して大きくならず、結局計算のボトルネックになるのはXの素因数分解部分であり、計算量はO(\sqrt{X})である。

……と思ったのだが、プログラムを書いて計算すると、X=16のときがOEISの結果と一致しない。
上の計算式によれば
#Aut(C16)=8
#Aut(C2×C8)=(1×2)×(2×4)=16
#Aut(C4×C4)=(16×3×2)=96
#Aut(C2×C2×C4)=((3×2)×2^2)×(2^2×2)=192
#Aut(C2^4)=(15×14×12×8)=20160
であるから、求める答えは16!×(1/8+1/16+1/96+1/192+1/20160)=4250979532800となる。
一方、OEISでは4248755596800になっている。これは第4項が1/192ではなく1/196なら一致することがわかるが、プログラムを書いてみると、確かにAut(C2×C2×C4)=192であることが確かめられる。そもそも49の倍数になるわけないだろ、なんでだよ


ここまでの議論に誤りを見つけた方、または、OEISの記述が間違っていると確信が持てる方はご一報ください。
なお、上の議論に則って実装したコードはこれです。(mod 10^9+7で出力)
https://wandbox.org/permlink/9RLseRNaHU5CeQiU
自己同型群の位数が計算できてるので実装がバグってることはないはず

atcoder黄色になるまでにやったこと

少し前に黄色になったのでポエムを書きます

青になるまで:
atcoder青になるまでにやったこと - メモ

青になってから黄色になるまでにしたこと
・コンテストに20回くらい出た
・700点以下をだいたい埋めた

精進の際、解説はすぐ読む派です。5分で何も浮かばなければ諦めます。
解説ACしたあとは「どうすれば答えを思いつけたか」を考えます。
実装に無限時間かかった場合は上位のコードを読むこともあります。

なお青~黄色の間でコンテスト中に800点以上を通したことは一度もないです。
それでも黄色にはなれるので希望を持ちましょう。

黄色のラインはだいたいこんなものだと思います。
・400以下を「早解き」できる
・600以下をほぼ解ける
・700をまあまあ解ける
・800以上は解けたらラッキー

蟻本は読んだことがないです。
読まなくても黄色にはなれるので希望を持ちましょう、と言いたいところですが、多分読んだほうがいいと思います。

次回「atcoder橙になるまでにやったこと」は10^9+7年後の予定ですお楽しみに

baby-step giant-step

この記事ではbaby-step giant-stepの「気持ち」を説明します。
アルゴリズムの説明のみであり、実装については一切説明していません。

○baby-step giant-step algorithmとは
巡回群上の離散対数問題を高速に解くアルゴリズム
平方分割でやる

○正確に
巡回群Gの台集合*1に全順序が定まる*2とする。
群の演算と順序の比較がO(1)でできるとする。
a,g\in Gが与えられたとき、a^x=gを満たす最小のx\in \mathbb{Z}_{\geq 0}O(\sqrt{|G|}\log|G|)で求めることができる。

アルゴリズム
N=|G|とおく。
最初に0\leq i < Kなるiに対してペア(i,a^i)を計算しておき、第二要素をキーにしてソートする。
ここで数yを決めたとき、★「a^{y+i}=gとなる0\leq i < Kがあるかどうか(あるなら最小のものを求める)」という問題を考える。
これは「a^i=ga^{-y}となる0\leq i < Kがあるかどうか」なので、最初に計算した配列上で二分探索することでO(\log K)で解くことができる。
yとして0,K,2K,\ldotsを順に考えることで、★の問題をO(N/K)回解くことにより元の問題に答えることができる。(もとの問題の答えはN未満なので)
全体でO(K\log K+(N/K)\log K)であるから、K=O(\sqrt{N})とすることでO(\sqrt{N} \log N)になる。

○例
\mathbb{F}_p^*上の離散対数問題
5^x=12 \mod 17を満たすxを求めよ
\mathbb{F}_{17}^*の元を\{1,\ldots,16\}\subset \mathbb{Z}と同一視して順序を定める。
0\leq i < 4について(i,5^i)を計算する
(0,1),(1,5),(2,8),(3,6)→ソート→(0,1),(1,5),(3,6),(2,8)
2^i=12*5^0となるものを探す→ない
2^i=12*5^{-4}=14となるものを探す→ない
2^i=12*5^{-8}=5となるものを探す→(1,5)が見つかる→答えは1+8=9

*1:Gの群構造を忘れて単なる集合だと思ったもの

*2:この条件は「Gは順序群である」とは異なる。ここでの順序は群構造と整合性がある必要はない

yukicoder No.712 赤旗

問題はこちら
No.712 赤旗 - yukicoder

'W'の数を数えるだけ。

s;
main(c){
	scanf("%*d%*d\n");
	while(c=getchar(),~c)if(c=='W')s++;
	printf("%d",s);
}

2行目以降は'\n'(10),'R'(82),'W'(87)のいずれかしかないので&1で識別可能。1行目の読み飛ばしとうまく噛み合わせる

w,s;main(c){for(;read(0,&c,1);w=c<11?:w)s+=c&w;printf("%d",s);}

63B