Scratchで競技プログラミング！(初めての人は最初の投稿をお読みください)

NT_ZZzz

A!/B! Problem 解説・解答のポイント
とりあえず確認すること
・問題文に怪しい記述はありませんか
・制約が異常に大きい/小さいものはありませんか
今回は
・「1000で割ったあまり」を解答する
・10^500 (普通のやり方では四則演算ができない)
が該当する
→「1000で割ったあまり」がわかれば A!/B! の実際の値はわからなくてもいい
→通常の四則演算で計算する方法ではなさそう

A!/B! について考える
例えば 20!/10!を考えると
(1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20)/(1*2*3*4*5*6*7*8*9*10) = 11*12*13*14*15*16*17*18*19*20
A+1からBまでの連続するB-A個の整数を掛けた数になる (順列・組合せ)

数学知識 (ここは純粋な知識を要求します)
・連続するN個の整数の積は N! の倍数である
を利用すると、
15!は1000の倍数である→連続する15個の整数の積は1000の倍数である→連続する15個以上の整数の積は1000の倍数である
→連続する15個以上の整数の積は1000で割ったあまりが0である
つまり、 B-A>=15の時は答えが0になることがわかる
B-A<15の場合のみ計算をすれば良い

A の代わりに Aを1000で割ったあまりで計算しても答えを1000で割ったあまりは変わらない (合同式)

出題者の解答方針
1 B-Aを計算する演算ブロックでは計算できないので繰り下がりのある引き算を自作する
2-1 B-A<15なら変数にそれを記録
2-2 B-A>=15なら変数を15とする
3 Aを1000で割ったあまり x を計算する下3桁を見ると良い
4 x+1から順番に掛けていくと答えが出る
解答
https://scratch.mit.edu/projects/527809514/

Last edited by NT_ZZzz (Dec. 19, 2021 15:28:21)

hirayuu1414

びっくりサイン実行時間制限: 5秒
ある整数xがあります。sin(x!)を求めてください。
※!は階乗である。
※sinの引数は°である。
※sinはScratchの範囲で求めて構わない。
制約
【Easy】
1≦x≦10
【hard】
1≦x≦10000000000(10^10)
結果例
x=1のときはsin(1!)=sin(1)≒0.017
X=3のときはsin(3!)=sin(3*2*1)=sin(6)≒0.105

2/25追記
私が「正解」と言っていたいくつかの回答が間違いなことが判明したため、後づけだがその回答が正解になるように制約変更。

Last edited by hirayuu1414 (Feb. 24, 2022 21:41:49)

Doctor_Fe

#188
hardに解答します。
https://scratch.mit.edu/projects/623231684/

hirayuu1414

正解です。HARDに正解した時点でEASYも解けるので両方FAです。

kakurenbo

>> #188
sin() の引数はラジアンですか。
結果例の値を見落としていました

Last edited by kakurenbo (Jan. 3, 2022 10:04:26)

kakurenbo

#188
Hard に解答します。
https://scratch.mit.edu/projects/623215447

なお問題文に指定がなかったため、! をガンマ関数ではなく純粋“階乗”とみて x は整数値であるとしています。

hirayuu1414

正解です。この問題ガバガバですね。書き足します。

Poteto143

問題リストを更新しました。

hirayuu1414

僕の「びっくりサイン」はEasyとHardに分かれているのでFAをEとHに分けてください。（どっちもDoctor_Feさんです）

Yuulis

Coprime to Each Other 実行制限時間:1秒

nを自然数とするとき、m ≦ n で、mとnが互いに素であるような自然数mの個数をf(n)とする。
(1) 自然数K、素数Pに対して、f(P ^ K)を求めよ。
(2) また、相異なる素数X, Yに対して、f(X * Y)を求めよ。

制約 (追記)2022 / 01 / 05 23:29 制約の見直しを行いました。
・Kは整数であり、0 < K ≦ 10 を満たす。
・Pは20以下の素数
・X, Yは10 ^ 6以下の素数 (ただし、X ≠ Y)

入力
K, P, X, Yはこの順に#1に示される方法で入力される。

出力
変数ansに(1)と(2)の答えを空白区切りで出力せよ。

結果例

入力 wrote:
K = 2
P = 3
X = 5
Y = 3

出力 wrote:
ans = 6 8

m ≦ 3 ^ 2 の範囲でmと3 ^ 2(= 9)と互いに素な自然数mは、m = 1, 2, 4, 5, 7, 8の6個である。
また、z ≦ 5 * 3 の範囲でmと5 * 3(=15)と互いに素な自然数zは、z = 1, 2, 4, 7, 8, 11, 13, 14の8個である。

Last edited by Yuulis (Jan. 5, 2022 14:29:13)

kumaman123

#196に回答します
Coprime to Each Other

NT_ZZzz

Coprime to Each Otherに質問です
想定解は K,P,X,Y=15,19,999999937,999999929 の時正しい答えを返しますか？

Yuulis

NT_ZZzz wrote:
Coprime to Each Otherに質問です
想定解は K,P,X,Y=15,19,999999937,999999929 の時正しい答えを返しますか？

「正しい答え」というと…？オーバーフローなどは起きないはずです。

Yuulis

kumaman123 wrote:
#196に回答します
Coprime to Each Other

変数outの方を見ていました。ごめんなさい。
ACです。FA！！

Last edited by Yuulis (Jan. 5, 2022 14:07:24)

NT_ZZzz

Coprime to Each Otherに質問です
K,P,X,Y=15,19,999999937,999999929の時の解は
14382120344091914178 999999864000004608 で合っていますか？
(Scratchでは16桁くらいから精度が足りなくなってくるのでそれを疑っています)

Last edited by NT_ZZzz (Jan. 5, 2022 14:09:44)

Yuulis

げっ、ほんとじゃん。テストケース抜けてた…
制約見直します

K,P,X,Y=15,19,999999937,999999929の時の解は@NT_ZZzzさんのもので正解です。

Yuulis

#196 の制約を見直しました。RJしたところ、@kumaman123さんの回答はACでした。

Last edited by Yuulis (Jan. 5, 2022 14:31:22)

NT_ZZzz

#196 Coprime to Each Other に解答します。
https://scratch.mit.edu/projects/624185539/

hirayuu1414

びっくりサインこれから解く人用のヒント1
問題文を見る限り、階乗のプログラムを作って、

([sin v] \( () \))

ブロックを使えばよさそうです。
では、階乗のプログラムをどう作るか。
Doctor_feさんやkakurenboさんは、「回帰」というテクニックを使って階乗を実装していますが、難しいので割愛。
ヒントとしては、下のようなブロックを作ることです。（答えは、「x!」という変数に実装します）

定義 (x)!
[x! v] を [1] にする //0にしてしまうと何をかけても0になってしまう
[何をかけるか？ v] を [1] にする //1*2*3...と続くので、その最初の数
(x) 回繰り返す
...
end

繰り返しの中を考えてみてください。（もっとも、階乗の実装はここの住人には簡単だと思いますが）

Yuulis

NT_ZZzz wrote:
#196 Coprime to Each Other に解答します。
https://scratch.mit.edu/projects/624185539/

ACです。これが想定解でした。

Discuss Scratch