ポラード・ロー素因数分解法(Pollard's rho algorithm) PKU 2447とか．
以下は嘘吐いてる可能性が結構あるので気をつけて！！
ρ法は篩などでは見つけられない大きさの素因数を見つけるアルゴリズム．
理論的なことは完全に理解していないので僕が説明するよりwikipedia:ポラード・ロー素因数分解法とかhttp://matsumoto-lab.hp.infoseek.co.jp/chapter02/algo02.htmlとかhttp://idm.s9.xrea.com/factorization/rho.htmlをよんだほうがいいです(´・ω・`)むずい．
ρ法のオーダーは，見つける素因数をpとするとsqrt(p)で50%程度らしい．
また実装の注意点として
- long longの掛け算はオーバーフローする．
- 掛け算を足し算で実装する．
- 確率的なものなので，見つからないこともある．
- Miller-Rabin Testなどで素数でないことを確認した上でρ法を行う．
- f(x) = x^2 + cのcの値を変えて繰り返し試行．
- 帰ってきた結果は素数とは限らない．
- 予め試し割り(篩など)で小さな素数を取り除いておくとよい．
実装は次の通り
typdef long long Int; // a * b % mを返す． Int multMod(Int a,Int b,Int m){ Int res = 0; a %= m; while (b){ if (b & 1){ res = (res + a) % m; } a = (a * 2) % m; b = b / 2; } return res; } // cははじめ1を入れる． // numが素数の場合無限ループしてしまう．判定もするなら適度なcで打ち切る．*/ Int PollardRho(Int num,Int c){ Int x,y,p; x = y = p = 1LL; while (p == 1){ x = (multMod(x,x,num) + c) % num; Int ty = (multMod(y,y,num) + c) % num; y = (multMod(ty,ty,num) + c) % num; if (x == y) return PollardRho(num,c+1); p = gcd(num,llabs(x-y)); } return p; }
1811 Prime Testや2447 RSAで確認．実際にはcの値が1の時点で答えは見つかっているようだ．1811では2^16以下の数で篩を作りためし割りした．
また，Brentの改良を入れると次のようになる．
// Brentの改良 Int PollardRho(Int num,Int c){ Int x,y,p; x = p = 1LL; int next = 2,i=1; while (p == 1){ ++i; if (i == next){ y = x; next *= 2; } x = (multMod(x,x,num) + c) % num; if (y == x) return PollardRho(num,c+1); p = gcd(num,llabs(x-y)); } return p; }
2447では速度上がらなかった．しょんぼり．
今回間違い多そうなので指摘してくだしあ．
ICPC2010 国内予選
興奮覚めやらぬうちに参加記を書く．
チームについて
うちのチームはメインコーダー，電波(アルゴリズマー)，サブコーダーという役割分担をしている，と思う．
メインコーダーが抜群の安定感で重めの実装をこなす．簡単な問題は僕と電波で解く．
メインコーダーが実装するだけっぽい感じなら，完全に任せて僕と電波で解けそうな問題を探しておく．
メインコーダーが考えたら解ける問題も多いので，メインコーダーに考える時間を作れるようにできたら調子が良い．
ペアプログラミングは大事．
開始2週間ぐらい前
学内で練習会．結構余裕でまぁ突破はできるかなーと思った．
開始1週間ぐらい前
模擬国内予選で10以内すら入れず．学内も3位で，今年で引退も見えて焦る．
前日
チームメイトと基本的なことを確認．失敗しなきゃいけるはず…
当日
過去問をたくさんといて，頭をICPC脳にする．開始前にはちょっと昼寝．起きたときに寝ぼけてて，寝過ごしたかとかなり焦った．
本番
- A問題みんなで読む．
- なんか概要が読めた気がする．書き出そうとする．
- 500*500のテーブル作れば通るよなーって感じで始める．Aにしてはむずくねー？って言いながら．
- 別にそんなことしなくても良かったらしい．
- メインコーダーがBの方が簡単じゃね？って言ったのでいったんパスしてBを任せる．
- その間にAを速攻通せるように考えを詰めておく．
- Bをちょっと詰まったみたいなので，プリントしてAをやる．
- 電波に見てもらいながら書いて，一部間違いを直してもらって提出．AC．(16:47)
- Cを電波が読んで，簡単らしい．一緒に問題を読む．
- Bの間違い気づいたみたいで直した．提出．AC．(16:56)
- Cを電波が書き出す．この時点で僕は完全に理解していなかったので，配列の生成などだけ書く．
- 途中から理解．簡単なDP．二人で一緒に書いたり直したり．提出．AC(17:06)
- Dをメインコーダーが書き出す．なんかめんどくさい実装らしい．完全に放置して電波と残りの問題を読み進める．
- 僕がEを読み，電波がFを読む．
- Eはグラフか…すぐには思いつかないなぁ．でもグラフならメインコーダーとか思いつく可能性は高いなぁ．
- 電波がFできるかもって言ってる．Fを読む．まず問題文が難しい…けど，なんとなく理解．よくわからん．
- Gを読む．問題文は超簡単ｗ重めの幾何だろうなぁ．解法は結構簡単に思いつくけど，実装できるかねー？
- (30分ぐらい経過)
- Dをメインコーダーが通した(17:41)．さすがです！僕は問題すら知らない．
- 予選突破はこれでできたと思うので，とりあえず順位を確認．あれ？一位じゃねー？
- このあと京都に抜かれてたらしい．
- で，みんなで次何やるか相談．
- ちょっとEが怪しい解き方を思いついた気がしたので，とりあえず書き出してみた．
- 途中，電波がもっとヨサゲな解法を思いついたのでメインコーダーと相談してバトンタッチ．
- 電波とメインコーダーがペアプログラミング．僕はとりあえずループするサンプルを考える．
- 結構早めに実装終了．適当に作ったサンプルも通った．
- ループ回数を最初多めにとって提出…しようとするもなかなか終わらないので仕方ないからループ回数を終わりそうなぐらいにとって提出AC. まじか！？(18:28)
- 順位を確認．_に続いて2位．
- さて，残り時間を幾何に突っ込むか，謎の文字列に突っ込むかを相談．
- 幾何は実装終わる気がしないという判断で文字列に突っ込む．きっと思いつけば．実装できるさ！
- 文字列を全生成してみる．生成に結構時間かかるからこの方針無理っぽー(19:00ぐらい)
- 残り30分で何もできなくねーって感じになってお菓子食べたりお茶飲んだりし始める．
- 確か上位2チームは海外だからこのまま順位固定しねーかなーなんて考えながら集中できずにFを考える．
- のこり3分ぐらいで東大が6問めを通した！うおおお！
- 終了．
結果は3位．大学別では2位なので，去年と同じ派遣方式だと海外いけるか…？
なんにせよ，これ以上ないような結果だった．自分はチームの中ではたいしたことないので，本当にチームメイトのおかげだと思う．アジア地区予選は更に頑張りたい．
後輩も結構成績よくて，来年引退してからの楽しみも増えた(*´v`*)
TCO Round1
すぐ寝ようかと思ったけど，惜しかったからｲﾗｲﾗっとしてねれないので更新．
250 EqualizeStrings
二つの文字列を同じにする．各文字を1文字進める/戻るコスト(a -> b, a -> z)は1．最小コストでおなじになる文字列を求めよ．複数ある場合は辞書順最初のを．
- とりあえず文字の小さい方に適当に合わせてみよう．
- tとgの場合真ん中のaにした方がいいのか…
- tとgの真ん中あたりってどう求めよう．偶奇で分ける？う〜ん…
- a-z全部やってみるか．a - > zに変換するときに25とかにしないように気をつけよう．
- サンプル通った．出そう．
500 TwoRegisters
レジスタにX=1,Y=1が入っている．可能なオペレーションは X=X+Y,Y=X+Yのみ．命令数最小ででRにする命令列を求めよ．複数ある(ry
- 後半加速しませんかね．X=1,Y=1からキャッシュmap[1000000][1000000]でやってみるか．
- 余裕のTLE
- 適当にノートに書いて考える．
- 発想を逆転させるのよ，ナルホドくん！
- 逆にやってみよう．X=R,Y=1..RをX=1，Y=1に戻すって考え方で．
- 仮にひとつずつ減っていって，R * R / 2ぐらいかなぁ…間に合わなそうだけどやってみよう．
- 500000ぐらいまでなら答えが出そう．
- チューニングすれば通るか？どこ速くなるかな…
- 文字列処理が明らかに遅いけど，早くする方法が上手く思い浮かばない…
- あれ，gcd(R,i) != 1のときって(1,1)にならなくない？
- xの倍数どおしの差はxの倍数だろう．これで刈れる？
- 1000000が通った！これで勝つる！
チャレンジフェイズ
- 500落ちてると仮定すると，ギリギリ通ってない程度．
- 自分がやったような間違いをしているソースが，勇気を出せ…
出せませんでした．誰かに落とされてました．自分と同じ間違いは他の人のを落とすチャンスなので，とても大事．点数的には落としに行くのが最適戦略だよなぁ．
GCJ Round1A-Cを振り返っておく
Round1落ちしてしまった…全体を振り返るに，しょんぼりなミスがいつも以上に多かったと思う．
やはりあの呪いか．
ミスを繰り返さないように，メモっておこう．
Round1A
なんかGCJがお祭りな感じだなーとか思いながら，今回通れないと次回でるの大変だなーとか思いながら参加．
A. Rotates
やるだけ，なんだけど，回転と幅詰めに手間取った．
前も手間取って，意外とでるからライブラリ入りしとこうかな．特にミスなし．
B. Make it Smooth
DPなのはすぐにわかるけど，上手く考えられない．small通そうとしたけど，なんか場合分けができない．
場合分けじゃなくて再帰全探索が良かった．これにこだわったのがこのラウンドの１番の失敗．
C. Number Game
本番中ろくに読まなかった．イクナイ．読んでみたら，smallはmapとかでキャッシュつければ通りそうってことはわかった．
結果
Aのみで1000ちょっと．全体としては戦略的ミスだった．一回目だしいいかっていう油断もあった．
でも全部とけなきゃ．
Round1B
一日二回か．しんどい．って思いながら参加．本番前に呪いのキーワードを吐いてしまった．これが転落の始まりだったのだろうか．
A. File Fix-It
やるだけ．日本人最速だったらしい．っていうのを聞いて，考え方が守りに入った．small通せばいっかなって．
B. Picking Up Chicks
とりあえずsmallを通そうとして，queueでも使ってswap全部試そうと思った．が，答え合わない…
本番後検証したら，queue中のbreakに何故かswapがK回超えたらやめるになってた．Kは最低限の鶏の数だよ…
ひどい凡ミス
途中皆結構点数あげてて，これはlarge通さないと勝てないと思って方針を変えた(たぶん遅かったけど)．
冷静に考えると，largeも貪欲にやっていけばいけそうってすぐ気づいた．けど，なんでか通らない．
本番後に少し条件が抜けてたことが発覚．2,3行足りなかった．
C. Your Rank is Pure
読めない！ていうか素数の話なに？？
本番後に説明聞いたら，とりあえずDPはすぐわかって，理解できたらとけてたかなーと思う．
ググル様は英語できない人に用ないんだなぁ．
結果
1700ぐらい．Bを冷静に通したかった．もしくは読みたかった．
Round1B
A. Rope Intranet
やるだけ．簡単すぎてなんども確認して1分ほどロスした．
B. Load Testing
読めないんですよ．まだ読めてない．皆結構解いてたので，簡単なんだろうなーと思って1時間以上読んだけどよくわからなかった．ゲシュタルト崩壊した．
数字の大きさから，なんとなーくBinary SearchでLargeをとくのかなーって思った．そうだったらしい．読めない．
[追記]バイナリサーチと言うかアドホック．意味を教えてもらって，最初トップダウンに考えていてイミフだったけど，ボトムアップに考えたらすぐわかった．でも，説明を日本語で聞いてもなかなか理解できなかったから本番中は無理ぽ．
C. Making Chess Boards
Bが読めないので，とりあえずCに来た．Cを読んだらLargeは知らないけどsmallはやるだけっぽかったのでガリガリ書き始める．
30分程でだいたいかけて，40分ぐらいで提出．small合わない…
本番後に少し条件が抜けていたことがわかった．数行訂正すれば直ってた．気づきにくいといえば気づきにくい．
結果
1300ぐらい．英語が読めなかったことと，Cでミスに気づかなかったのが原因かな．
でもCをn^5で出してたかというと怪しい．その根性はなかったなァ…通るなんて．
謎
PKU 2671なんだけど，while (1);を書くかどうかでACがWAになる．
ダイクストラで解いたのだけど，擬似コードはこんな感じ．
int bfs(){ while (!q.empty()){ } while (1); // これを消すとWA } int main(){ ... ... cout << bfs() << endl; }
なんぞこれ？
実際のコード
#include <iostream> #include <queue> #include <cstdio> using namespace std; int distsum[300][300]; int costsum[300][300]; int dist[300]; int cost[300]; int totaldist,totalcost; int dp[300][300][2]; int N; #define RIGHT 1 #define LEFT 0 struct State{ int left,right,which; int cost; bool operator<(const State& s)const{ return cost > s.cost; } }; int bfs(){ priority_queue<State> up; up.push((State){0,0,0,0}); up.push((State){0,0,1,0}); while (!up.empty()){ State st = up.top(); up.pop(); int l = st.left; int r = st.right; int c = st.cost; int w = st.which; //cout << l << " " << r << " " << c << " " << w << endl; if (c > dp[l][r][w]) continue; if ((r+1)%N==l) return c; int nl = (l + N - 1) % N; int nr = (r + 1) % N; int nc,nw; if (w == RIGHT){ nc = c + (totalcost - costsum[l][r])*distsum[nl][r]; nw = LEFT; if (dp[nl][r][nw] > nc){ up.push((State){nl,r,nw,nc}); dp[nl][r][nw] = nc; } nc = c + (totalcost - costsum[l][r])*distsum[r][nr]; nw = RIGHT; if (dp[l][nr][nw] > nc){ up.push((State){l,nr,nw,nc}); dp[l][nr][nw] = nc; } }else{ // from LEFT nc = c + (totalcost - costsum[l][r])*distsum[nl][l]; nw = LEFT; if (dp[nl][r][nw] > nc){ up.push((State){nl,r,nw,nc}); dp[nl][r][nw] = nc; } nc = c + (totalcost - costsum[l][r])*distsum[l][nr]; nw = RIGHT; if (dp[l][nr][nw] > nc){ up.push((State){l,nr,nw,nc}); dp[l][nr][nw] = nc; } } } while (1); // これを消すとWA } int main(){ while (1){ scanf("%d",&N); if (!N) break; totaldist = 0; totalcost = 0; for (int i=0;i<N;i++){ scanf("%d%d",&cost[i],&dist[i]); totalcost += cost[i]; totaldist += dist[i]; } for (int i=0;i<N;i++) for (int j=0;j<N;j++) for (int k=0;k<2;k++) dp[i][j][k] = 1 << 30; for (int i=0;i<N;i++){ int dsum=0,csum=0; for (int j=i;;j++){ j %= N; csum += cost[j]; costsum[i][j] = csum; distsum[i][j] = dsum; dsum += dist[j]; if ((j+1)%N==i) break; } } cout << bfs() << endl; } }
なんぞこれ？
追記
intの関数が値を返した方がいいというのはまさにそのとおりでございます．
でもwhile(1)
SRM469
すごい久しぶりに更新．５月病．
なんかやらなきゃいけないことをやってない気がして……
250 TheMoviesLevelOneDivOne
long long を掛け算につけなかった＼(^o^)／
500 TheMoviesLevelTwoDivOne
N=20の時点で1 << 20を考えて，TSPっぽいなーって思った．
とりあえず深さ優先で解いて，それにキャッシュをつけようとしたけど
なんだかバグが抜けなくて落ちるの確定だけど出してしまった．
僕の点数をだれかが喜んでいるはず……！！
そんなに難しくないと思うんだけどなァ．
プラクティスでといたけど，キャッシュを上手く使ってなくて一度TLEになった．
結果
1204ｗDiv2転落リーチ．次回からdiv2に上がりたい(ryになるかも．
最近やるきがでなくてサボっているのが良くない．人生に対して凡ミスをしている気がする．
Emacs23 on Windows のフォント設定
Windowsのemacs23.1で好きなフォントにする方法．調べたら EmacsWikiに書いてあったので，日本語で説明．
- emacsを起動してスクラッチバッファを開く．( C-x b *scratch* )
- (w32-select-font)と入力して，行末(')'の右)でC-j
- フォントを選択する窓が開くので，使いたいフォントを選んでOK
- バッファに次のようにフォント名が挿入される
(w32-select-font)
#("ＭＳ Ｐ明朝-12" 0 9 (charset cp932-2-byte))
- .emacsを開いて次のように入力する．ダブルクォーテーション内は(w32-select-font)で取得したフォントを指定する．
(set-face-font 'default "ＭＳ Ｐ明朝-12")
- emacsを再起動する
