問い121
袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.
プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.
ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう. 支払いはすべてポンドの整数倍であり, またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため, 与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.
15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.
解法
組み合わせ数が少ないのでLispの分数計算で全探索します。
(defun saiki (p deep get)
(if (= deep 15)
(if (< (/ deep 2) get) p 0)
(+ (saiki (* p (/ 1 (+ deep 2))) (+ deep 1) (+ get 1))
(saiki (* p (/ (+ deep 1) (+ deep 2))) (+ deep 1) get))))
saiki
(let ((a (saiki 1 0 0)) (b 0) (c 0))
(setq b (numerator a)
c (denominator a))
(floor (/ c b)))
問い123
pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)n + (pn + 1)n を pn2 で割った余りとする.
例えば, n = 3 のとき, p3 = 5 であり, 43 + 63 = 280 ≡ 5 mod 25.
余り r が 109 より大きくなる n の最小値は 7037 である.
余り r が 1010 より大きくなる最初の n を求めよ.
モード演算は分けて個別に計算しても全部合わせて計算しても答えが変わらないということを利用してステップ単位で解きます。
高速化しようと考え
n^23=n^16*n^4*n^2*n^1のように累乗が2^累乗の指数に分解出来る性質を利用して解こうとしたらint64で溢れるので上手くいきません。
Ｌｉｓｐなら高速化は簡単ですがＣ++では多倍張整数を用意しないと無理かもしれません。
#include<stdio.h>
#include<vector>
#include<iostream>
const int up=1000000;
std::vector<__int64> sosuu;
bool so[up];
void setSo(){
int i2;
memset(so,true,sizeof(so));
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
int main(){
setSo();
__int64 p,pd,pu,p2,calcD,calcU,ten=1;
for(int i=0;i<10;i++){
ten*=10;
}
for(int i=0;i<sosuu.size();i++){
p=sosuu[i];
p2=p*p;
calcD=pd=p-1;
calcU=pu=p+1;
for(int n=0;n<i;n++){
calcD=(calcD*pd)%p2;
calcU=(calcU*pu)%p2;
}
//std::cout<<(calcD+calcU)%p2<<"\n";
if((calcU+calcD)%p2>ten){
std::cout<<i+1;
break;
}
}
std::cout<<"?";
}
問い124
n の"根基"(radical)は、rad(n) で表し、n の素因数の積を意味する。 例えば 504 = 23 × 32 × 7 であるから、 rad(504) = 2 × 3 × 7 = 42 である。
1 ≤ n ≤ 10 に対して rad(n) を計算し、rad(n) を対象にソートし、 rad(n) が同じ場合は n を対象にソートすると以下のようになる。
未ソート ソート済み
n rad(n) n rad(n) k
1 1 1 1 1
2 2 2 2 2
3 3 4 2 3
4 2 8 2 4
5 5 3 3 5
6 6 9 3 6
7 7 5 5 7
8 2 6 6 8
9 3 7 7 9
10 10 10 10 10
E(k) をソートした表の n の列の k 番目の要素とする。 例えば、 E(4) = 8, E(6) = 9 である。
rad(n) を 1 ≤ n ≤ 100000 でソートした場合、 E(10000) を求めよ。
普通に構造体を定義して優先順位付きキューに放り込むだけです。
この時10000個目を超えた分はいらないのでキューから放り出します。
後は上段に残ってる10000個目を取り出すだけです。
#include<stdio.h>
#include<queue>
struct S{
int n,rad;
bool operator<(const S& s)const{
if(rad!=s.rad)return rad<s.rad;
return n<s.n;
}
void set(int n1){
n=n1;
rad=1;
for(int i=2;i*i<=n;i++){
if(n1%i==0){
rad*=i;
while(n1%i==0)n1/=i;
}
}
rad*=n1;
}
};
int main(){
int count=0;
std::priority_queue<S> pQ;
S s;
for(int i=1;i<= 100000;i++){
s.set(i);
pQ.push(s);
count++;
if(count>10000)pQ.pop();
}
s=pQ.top();
printf("%d %d\n",s.n,s.rad);
}
問い125
回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ: 62+72+82+92+102+112+122
1000 未満で連続する平方数の和で表せる回文数はちょうど 11 あり、その合計は 4164 である。正の整数の平方のみをこの問題では扱うため、1=02+12 は含めないことに注意せよ。
回文数でありかつ連続する平方数の和で表せる、108 未満のすべての数の合計を求めよ。
解法
この問題ははまった。
問題では式の形が違う場合ではなく、合計値の集合を求めよと書いてある。
合計値が同じで別の式で表せる場合が少しだけあるのに気づかず不正回を食らった問題。
他の人も同じようにはまってたらしい。
#include<stdio.h>
#include<vector>
#include<iostream>
#include<set>
bool saiki(__int64 n,__int64 rev,__int64 s){
if(n==0){
return rev==s;
}else{
return saiki(n/10,rev*10+n%10,s);
}
}
int main(){
std::vector<__int64> memo;
__int64 p=0,sum=0,up=1;
for(int i=0;i<8;i++)up*=10;
while(p*p<=up){
sum+=p*p;
memo.push_back(sum);
p++;
}
std::set<__int64> nums;
__int64 ans=0,t;
for(int i=0;i<memo.size();i++){
for(int j=i+2;j<memo.size();j++){
t=memo[j]-memo[i];
if(t>=up)break;
if(saiki(t,0,t)==true){
std::cout<<t<<"\n";
if(nums.find(t)==nums.end()){
nums.insert(t);
ans+=t;
}
}
}
}
std::cout<<"ans="<<ans<<"\n";
}
問い127
nのradicalをrad(n)と書き, nの異なる素因数の積とする. 例えば, 504 = 23 × 32 × 7なのでrad(504) = 2 × 3 × 7 = 42である.
正整数の3つ組 (a, b, c)がabc-hitであるとは
GCD(a, b) = GCD(b, c) = GCD(c, a) = 1
a < b
a + b = c
rad(abc) < c
の4つの性質を満たすことである.
(5, 27, 32) はabc-hitである:
GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
5 < 27
5 + 27 = 32
rad(4320) = 30 < 32
abc-hitは非常に稀である. c < 1000のときには31個しかなく, そのときの∑cは12523である.
c < 120000での∑cを求めよ.
解法
とりあえずいい解法を思いつかなかったので定義通り全探索してみました。
全探索なので当然速度が出ません。
一応正しい答えが出ましたがこれでは正答とは言えませんね。
後日再挑戦です。
#include<stdio.h>
#include<iostream>
const int up=120000;
bool so[up+1];
__int64 rad[up+1];
int gcd(int a, int b){
while( 1 )
{
a = a % b;
if( a == 0 )return b;
b = b % a;
if( b == 0 )return a;
}
}
void setRad(){
for(int i=1;i<=up;i++){
rad[i]=1;
}
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=2;i<=up;i++){
if(so[i]==false)continue;
for(int j=i;j<=up;j+=i){
if(i!=j)so[j]=false;
rad[j]*=i;
}
}
}
int main(){
setRad();
int herf=up/2;
__int64 ans=0;
int c;
printf("ok");
for(int a=1;a<=herf;a++){
for(int b=a+1;a+b<up;b++){
if(gcd(a,b)!=1)continue;
c=a+b;
if(rad[a]*rad[b]*rad[c]>=c)continue;
if(gcd(a,c)!=1)continue;
if(gcd(b,c)!=1)continue;
ans+=c;
printf("(%d %d %d)",a,b,c);
}
}
std::cout<<"\nans="<<ans;
}
最終更新：2012年10月03日 19:13
