Codeforces Round #17 - simezi

問題むずい……

252位 2AC penalty 108
00:06 / 00:42(3WA)/ - / (2WA 4TLE) / -

1573->1509
うーんうーん。

2以上n以下の整数のうち、「連続する2つの素数の和」+1の形で表される素数がk個以上あるかどうかを答えよ。
n,k≦1000である。

問題読解に手間取る。素数で、かつ2個の隣り合う素数+1とか日本語で言われてもややこしいのに……

2000くらいまで素数を生成して書いた。

社員がn人いる会社において、社員のランクq[i]が与えられる。
また、社員a[i]はb[i]の上司に、コストc[i]でなりうるという関係がm個与えられる。
この関係を満たし、かつq[a[i]]＞q[b[i]]のときa[i]はb[i]の上司になることができる。

このとき、「1人の社員を除く全ての社員に一人だけ上司がいる」状態にするための最小コストを求めよ。不可能な場合は-1を出力せよ。

またまた問題の意味がよくわからない。qualificationって何ぞ。問題文は、ある社員はだれか一人だけのほかの社員の上司になると言っているような感じがするのだけど、サンプルを見るに一人の社員が複数の社員の上司になりうるようだ。

ランクが上の社員で、上司になりうる一番安い社員を上司にしていけばいいかな。
実装。

WA. なんだろう。
最大ランクの社員が複数いる場合に間違っているとかだろうか。
修正。

WA.なんでだ。
最大ランクの社員の判定を変えてみる。

WA.問題読み違えてる可能性ありそうだ。
次の問題行こう。。。

各文字が'a','b',,'c'のいずれかからなるn文字の文字列が与えられる。
この文字列に対して、連続する2文字を選び

という操作を何回でも行うことができる。

操作の結果の文字列において、aの出現回数,bの出現回数,cの出現回数のどの二つの差の絶対値も1以下であるような文字列は何通りできるかを求めよ。

しばらく考えたけど方針たたない。解いてる人少なすぎｗ
Bにもどろう。

スクラッチで全て書き直したら通った。なんで？？？？

b進数で、n桁の数（先頭0のものは含まない）をノートに1ページにc個ずつ書いていく。
このとき最後のページに書かれる数の個数を求めよ。

2≦b≦10^(10^6),
1≦n≦10^(10^6),
1≦c≦10^9である。

うお、入力サイズ凄いｗ
10万桁の数字なのでJavaを使おう……

要は(b-1)*b^(n-1)%cを求めよという問題だよね。
BigIntegerにmodpowメソッドがあったからそれで求めればよいのではないだろうか。
繰り返し2乗法だの使って実装されてるだろうし間に合うんじゃ。

書いた。

TLE(case29)
あれー？

繰り返し二乗法を自分で書いてみたり(更にちょっと前のケースでTLE)、
フェルマーの小定理を使おうとしてみたり（cが素数ではないのでそのままは使えない）
するも通らぬままコンテスト終了。

フェルマーの小定理のa^p≡a (mod p)の形のバージョンってpが素数でなくても成り立つんじゃなかったっけーあれー？