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

watashida

#85 robot simulation 解答

まず、N個のうちのどれかがゴールにつくようにつくような時刻の計算を考えてみます。つまり、いったんロボットの番号を忘れて考えてみます。
この時、衝突はただそのまま何も起こらなかったことに変換できます。
例を挙げると
P = (1, 3)
D = (右, 左)
で衝突して
P = (2, 2)
その後
P = (1, 3)
D = (左, 右)
となるところを、そのまま通過して
P = (3, 1)
D = (右, 左)
としても、ロボットの番号は関係ないとき問題はありません。
つまりこのときロボットはただ一直線に進むだけになります。

ここでXi = 座標 0 にi番目に到着したロボットの到着時刻と定義します。
同様にYi = 座標 T にi番目に到着したロボットの到着時刻と定義します。
いまロボットは一直線に動くとしているので、Xiは「左を向いたロボットの中で、i番目に座標が小さいものの座標」となることがわかります。
同じくYiはT - 「右を向いたロボットの中で、i番目に座標が大きいものの座標」となります。
つまり次のような例を考えると、
D = (左, 右, 左, 右, 右)
のとき
X = (P1, P3)
Y = (T - P5, T - P4, T - P2)
となります。

最後にX, Yが何番目のロボットに対応するか考えます、
つねに P1 ≦ P2 ≦ … ≦PNなことと、X,Yは到着した時刻順であることを考えると、Xiは前からi番目のロボットに対応し、Yiは後ろからi番目のロボットに対応することがわかりました。
つまり、求める答えansは
ans = (X1, X2, X3, …, Y3, Y2, Y1)となり、これは全て高速に計算できます。

想定解
https://scratch.mit.edu/projects/519665620/

watashida

#87 に解答します
https://scratch.mit.edu/projects/520081711/

NT_ZZzz

watashidaさん #87 ナベアツアツ数EASY Accepted, ナベアツアツ数HARD Time Limit Exceeded
私の環境では N=333333333333333 が12秒かかりTLEです(想定解は同ケース1.8秒)

watashida

さすがにメモ化再帰のメモをリストで保存するのは計算量的につらかったらしいので、hash tableを実装して更新しました
多分これで大丈夫だと思います

Poteto143

お知らせ
問題リストを更新しました！
また、#1のルールに以下を追加しました。
・間違えた問題に再度回答する場合は、新しく投稿をしてください。
・難易度を分ける場合は二つまで、難易度名はEasy、Hardで統一してください。※トピック管理上の理由による

NT_ZZzz

watashidaさん #87 ナベアツアツ数HARD Accepted! FAです！

Yuulis

#80の解答例です。
https://scratch.mit.edu/projects/518273432/

s_koki

Poteto143 wrote:
というわけで、さっそく僕から問題です。
スーパーべき乗君実行時間制限:5秒
ねこくんは、小さなロボットを作りました。
そのロボットは、2^nの計算をして、結果をしゃべる機能を持っています。
ある日、ねこくんはロボットにnの値をセットし、計算を始めさせました。
このとき、ロボットがしゃべると予想される数字の1ケタ目の数字を、変数「結果」に入れてください。
制約
5 ≦ n ≦ 10^15 (nは自然数)
結果例
n=10のとき、2^10は1024のため、変数「結果」に入るべき値は「4」となります。

https://scratch.mit.edu/projects/521116324

Poteto143

#108
不正解です…
https://scratch.mit.edu/discuss/post/5121585/ に理由があるので読んでみてください！

massa-g

2乗くん実行制限時間:0.5秒
※Poteto143さんの問題を参考にしました。
乗田くんは、正の数xを2乗し、それを(Scratchの「切り捨て」ブロックを使い、)切り捨てするプログラムを作りました。この時、
ロボットが出す結果の桁数を変数「桁数」に入れてください。
制約
【Easy】
0<x<10^10
【Hard】
0<x<10^308
【結果例】
xが11のとき、桁数には「3」が入ります。
xが2.5のとき、桁数には「1」が入ります。

Last edited by massa-g (April 26, 2021 14:25:30)

Doctor_Fe

#110に解答させていただきます。
https://scratch.mit.edu/projects/521831488/

#3にも解答させていただきます。
https://scratch.mit.edu/projects/521854131/

Last edited by Doctor_Fe (April 27, 2021 12:38:08)

massa-g

Doctor_Fe wrote:
#110に解答させていただきます。
https://scratch.mit.edu/projects/521831488/
不正解です。
例:32の場合、32^2は1024のはずなのに、3と出力される

00giri

#110への回答です。(Easy&Hard)
https://scratch.mit.edu/projects/705797430/

Last edited by 00giri (June 16, 2022 02:54:27)

Doctor_Fe

#112について、修正できたと思います。

yuikunyeah

温度調節の大切さ実行時間制限:5秒
あるエアコン会社が、easy or hard　の温度まで上げることのできるエアコンを作り上げました。
しかし、この影響で宇宙にある星がある温度でそれぞれ溶け出します（という設定です。）。
その段階は4あります。
1:ひとつ前に溶けた星の次の温度で溶ける。
2.ひとつ前に溶けた星の2つ上の温度で溶ける。
.
4
というふうに、つまり「段階の数だけ前の星が溶けた温度より上がるとその星は溶ける」というふうになっています。
星の並び順は12341234…etcです。

n度に溶けた星の数の下二桁をお答えください。
easy
0≦n≦1000

hard
0≦n≦10^15

例:
n=30なら12
n=2なら01

Last edited by yuikunyeah (April 27, 2021 13:50:01)

massa-g

#114,#113
正解です!今回は(Hard,Easyの両方)のFA者は00giriさんとなります。

00giri

#115への回答です(Easy&Hard)。
https://scratch.mit.edu/projects/705797020/

Last edited by 00giri (June 16, 2022 02:53:09)

yuikunyeah

00giriさん、#115正解、FAです！

なんか簡単に作ったつもりでも早く解かれると悔しい

Last edited by yuikunyeah (April 27, 2021 14:14:53)

Yuulis

Discussion Forum 実行制限時間:1秒

Scratchのディスカッションフォーラムでは、ページの長さが一定以上になるとそれ以降の投稿は次のページに表示されます。
今、ページの長さがH pxに指定されたフォーラムに、N個の表示待ちの投稿があります。各投稿の長さ(a1, a2, a3, … , aN (px))が与えられるので、全投稿を表示した後のフォーラムの総ページ数pを出力してください。

制約
値はすべて正整数
・0 < H ≦ 10^9
・0 < N ≦ 2 * 10^5
・0 < ai ≦ H (乱数生成)

入力
H, Nは変数に、aiはリストaに格納される。

出力
変数pに答えを出力せよ。

結果例

入力 wrote:
H = 10
N = 8
a = {3, 5, 2, 8, 10, 1, 10, 9}

出力 wrote:
p = 4

新しいページの追加は、“/”の部分で行われています。
a = {3, 5, 2, / 8, 10, / 1, 10, / 9}

Last edited by Yuulis (April 30, 2021 02:42:58)

soutamamapapa

#119 解答します
https://scratch.mit.edu/projects/525028447/

Discuss Scratch