メモ

yukicoderでゆるふわgolf

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

yukicoder No.706 多眼生物の調査

問題はこちら
No.706 多眼生物の調査 - yukicoder

strlen(s)-2の最頻値を見るだけ

int a[1010];
int main(){
	int n;
	scanf("%d\n",&n);
	for(int i=0;i<n;i++){
		char s[1010];
		gets(s);
		a[strlen(s)-2]++;
	}
	
	int ans=2;
	for(int i=2;i<=1000;i++)if(a[i]>=a[ans])ans=i;
	printf("%d",ans);
}

ぐっと睨んでループをまとめる。文字列を読み込む変数をごまかしたり、端の処理をごまかしても通る

k,a[999],i;
main(m){
	for(;gets(&k)?++a[strlen(&k)]:i++<998?m=a[i]<a[m]?m:i:0;);
	printf("%d",m-2);
}

95B
これは996までしかチェックしていないので997や998が答えになるときWAになる

yukicoder No.701 ひとりしりとり

問題はこちら
No.701 ひとりしりとり - yukicoder

まずn個の相異なる文字列を生成しよう。これは前にやった。
yukicoder No.327 アルファベット列 - メモ
こうしてできた文字列の前後に'a'を付け、最後の単語にはさらに'n'をつければよい

//No327の使い回し
void f(int n){
	~n?f(n/26-1),putchar(97+n%26):0;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		printf("a");
		f(i);
		printf("a%c",i==n-1?'n':' ');
	}
}

ループを逆にまわして変数を省略、関数化せずにループする、2回あるprintfをまとめる

x;
main(n){
	for(scanf("%d",&n);x=--n;)for(printf("a a");putchar(x%9+97),x/=9;);
	puts("n");
}

88B