Discuss Scratch
- Discussion Forums
- » 日本語
- » Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
- nyankodaisensou-suki
-
Scratcher
100+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#301
それは含まないという事でいいです。
それは含まないという事でいいです。
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#302
それならば、#297「注文内容の多過ぎる料理店」に対する解答のhttps://scratch.mit.edu/projects/1018100914/(#298 )は、#300「注文内容の多過ぎる料理店その2」で追加された制約もすでに満たしていることになりませんか?
このプロジェクトは実行時間計測に使用するブロックを除くと12ブロックなので、スプライト名が変更されていても問題ないことになるはずです。
それならば、#297「注文内容の多過ぎる料理店」に対する解答のhttps://scratch.mit.edu/projects/1018100914/(#298 )は、#300「注文内容の多過ぎる料理店その2」で追加された制約もすでに満たしていることになりませんか?
このプロジェクトは実行時間計測に使用するブロックを除くと12ブロックなので、スプライト名が変更されていても問題ないことになるはずです。
Last edited by sakura_neko (May 11, 2024 13:24:09)
- Poteto143
-
Scratcher
1000+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
トピ主からのお知らせ
#2の問題リストの作りを刷新しコンパクトかつ見やすいように作り変えました!
また、#269 35 or Under以降の新しい問題をリストに追加しました。最終更新が1年以上前ってマジ…?
#2の問題リストの作りを刷新しコンパクトかつ見やすいように作り変えました!
また、#269 35 or Under以降の新しい問題をリストに追加しました。最終更新が1年以上前ってマジ…?
- nyankodaisensou-suki
-
Scratcher
100+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#303
すみません、出題ミスをしました。
すみません、出題ミスをしました。
- nyankodaisensou-suki
-
Scratcher
100+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
正しくは、3ブロック以上でした。出題ミスをしてすみませんでした。
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#300 注文内容の多過ぎる料理店その2に解答します。
(競技プログラミングでは幅広いプログラム言語で解ける問題が出されるので、ソースコード等に直接制約を加えることは少ないと思います。
そのため今回の問題はどちらかというとスクリプトクイズのトピックに適した問題かもしれません。)
(競技プログラミングでは幅広いプログラム言語で解ける問題が出されるので、ソースコード等に直接制約を加えることは少ないと思います。
そのため今回の問題はどちらかというとスクリプトクイズのトピックに適した問題かもしれません。)
- nyankodaisensou-suki
-
Scratcher
100+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#307
@sakura_neko さん正解です。
僕の想定解とほぼ同じでした。
@sakura_neko さん正解です。
僕の想定解とほぼ同じでした。
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
なげなわ選択 実行時間制限: 10秒
あなたはお絵描きソフトで、いくつかの点を多角形のなげなわツール(囲んだ範囲が選択されるツール)で選択しようとしています。それぞれの点について、なげなわの中に入っているかを判定してください。
制約
・入力
多角形のなげなわの頂点数 N
頂点の座標 (px_1,py_1), (px_2, py_2), …, (px_N, py_N)
候補の点の数 Q
候補の点の座標 (qx_1,qy_1), (qx_2, qy_2), …, (qx_Q, qy_Q)
Easy: 1≦N, Q≦10
Hard: 1≦N, Q≦5000
入力はすべて整数であり、頂点・候補の点の座標は絶対値が10^7以下とする。
また、多角形のなげなわは1~N番目の点を順に結び、N番目の点と1番目の点を結んでできる閉曲線で、自己交差を持たないものとする。
ただし、多角形は凸とは限らない(へこみがあるかもしれない)。
さらに、候補の点はなげなわの辺上に存在しないものとする。
・出力
各候補の点Q個について、多角形のなげなわの中に入っていればtrue, そうでなければfalse
結果例
入力1:N=5, 多角形のなげなわの頂点 (0, 0), (10, 0), (5, 5), (10, 10), (0, 10), Q=4, 候補点 (3, 4), (11, 0), (7, 5), (8, 1)
出力1:true, false, false, true
久しぶりに出題します
あなたはお絵描きソフトで、いくつかの点を多角形のなげなわツール(囲んだ範囲が選択されるツール)で選択しようとしています。それぞれの点について、なげなわの中に入っているかを判定してください。
制約
・入力
多角形のなげなわの頂点数 N
頂点の座標 (px_1,py_1), (px_2, py_2), …, (px_N, py_N)
候補の点の数 Q
候補の点の座標 (qx_1,qy_1), (qx_2, qy_2), …, (qx_Q, qy_Q)
Easy: 1≦N, Q≦10
Hard: 1≦N, Q≦5000
入力はすべて整数であり、頂点・候補の点の座標は絶対値が10^7以下とする。
また、多角形のなげなわは1~N番目の点を順に結び、N番目の点と1番目の点を結んでできる閉曲線で、自己交差を持たないものとする。
ただし、多角形は凸とは限らない(へこみがあるかもしれない)。
さらに、候補の点はなげなわの辺上に存在しないものとする。
・出力
各候補の点Q個について、多角形のなげなわの中に入っていればtrue, そうでなければfalse
結果例
入力1:N=5, 多角形のなげなわの頂点 (0, 0), (10, 0), (5, 5), (10, 10), (0, 10), Q=4, 候補点 (3, 4), (11, 0), (7, 5), (8, 1)
出力1:true, false, false, true
久しぶりに出題します
- 9q9q9q
-
Scratcher
12 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#309に回答します
https://scratch.mit.edu/projects/1041576782/
走査線が頂点と一致した時の方法がわからず、回避することにしました。
確かnakakou-TVさんの3Dマイクラの解説のところで見た方法を思い出しながら作りました
https://scratch.mit.edu/projects/1041576782/
走査線が頂点と一致した時の方法がわからず、回避することにしました。
確かnakakou-TVさんの3Dマイクラの解説のところで見た方法を思い出しながら作りました
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#310 以下のケースなどで誤って判定されます。
入力:N=3, 多角形のなげなわの頂点 (0, 0), (7, 8), (1, 7), Q=1, 候補点 (1, 5)
正解の出力:true
回答された出力:false
テストケース生成用プロジェクトも作りました。
正解の出力(判定点が実際に中に入っているか)はないので、確認は目視でしかできませんが参考にしてください。
入力:N=3, 多角形のなげなわの頂点 (0, 0), (7, 8), (1, 7), Q=1, 候補点 (1, 5)
正解の出力:true
回答された出力:false
テストケース生成用プロジェクトも作りました。
正解の出力(判定点が実際に中に入っているか)はないので、確認は目視でしかできませんが参考にしてください。
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
…さすがにもう誰も挑戦しなさそうなので解答をだします…私も忘れていた
解答例はこちらです。
入力が多く難しそうですが、Easyは素直に実装ができます。「多角形の内外判定」などで調べれば実装方法がすぐ出てくると思います。
問題はHardでしょうか。Scratchで実装するには厳しすぎたかもしれません。
ソート→二分探索はともかくセグ木に近い処理が必要だったのは反省しています。
私は競プロをこのところ全くやっていないので、難易度を某サイトの色で表すことができる人がいればどのくらいか教えてください。
解答例はこちらです。
入力が多く難しそうですが、Easyは素直に実装ができます。「多角形の内外判定」などで調べれば実装方法がすぐ出てくると思います。
問題はHardでしょうか。Scratchで実装するには厳しすぎたかもしれません。
ソート→二分探索はともかくセグ木に近い処理が必要だったのは反省しています。
私は競プロをこのところ全くやっていないので、難易度を某サイトの色で表すことができる人がいればどのくらいか教えてください。
- Poteto143
-
Scratcher
1000+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
お知らせ
なぜか本トピックがクローズされていましたが、STへ再オープンを依頼し無事に解除されました。
ついでに#2の問題リストを更新しています。
ところで#1の文章も一部変更しようと試みたのですが、もともと入っている文章が後から悪い言葉検出器に引っかかるようになったのかどう編集しても投稿を保存できなくなってしまいました。おそらく今後も変更されることはないかもしれません…。
なぜか本トピックがクローズされていましたが、STへ再オープンを依頼し無事に解除されました。
ついでに#2の問題リストを更新しています。
ところで#1の文章も一部変更しようと試みたのですが、もともと入っている文章が後から悪い言葉検出器に引っかかるようになったのかどう編集しても投稿を保存できなくなってしまいました。おそらく今後も変更されることはないかもしれません…。
- yuito2013
-
Scratcher
100+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
ミス削除
Last edited by yuito2013 (June 6, 2025 23:08:05)
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
久しぶりに見かけたので簡単めな問題を一つ
解いてくれる人がいるか分からないが…
りんご拾い 実行時間制限: 10秒
N×Nのマス目があり、各マスにはりんごが落ちているか数字が書いてあります。
最初にあなたは左下のマス(1,1)にいます。
あなたは上下左右に隣接するマスに移動することができ、りんごのあるマスではりんごを拾うことができますが、数字の書いてあるマスにはその数字の分だけりんごを持っていなければ移動することができません。
あなたが右上のマス(N,N)まで移動できるかを判定してください。
制約
・入力
マス目のサイズ N
各マスの情報のリスト S = [S_1, S_2, … , S_N²]
Easy:1≦N≦10、Hard: 1≦N≦400であり、S_iは文字“a”または0以上N²以下の整数。
マス(i,j)はS_(i-1)×N+jに対応しており、この値が“a”であるときマス(i,j)にはりんごがあり、整数であるときマス(i,j)にはその整数が書いてある。
また、S_1は常に“a”または0である。
・出力
(1,1)から(N,N)まで問題文の条件を満たして移動できるならtrue、そうでなければfalse
結果例
入力:N=3, S=[0, 0, a, 1, 2, 2, a, 2, 0]
出力:true
(1,1)→(1,2)→(1,3)(りんごを拾う)→(1,2)→(1,1)→(2,1)→(3,1)(りんごを拾う)→(3,2)→(3,3)のように移動すればよいです。
入力:N=4, S=[0, a, 3, 0, 0, 0, 3, a, 0, 0, 3, 0, a, 0, 3, 0]
出力:false
左から2行目までにはりんごが2個しかないので、左から3行目のどのマスにも移動できないため(4,4)まで行くことはできません。
入力:N=400, テストケース, テストケース2
出力:true
Hard条件のもとでは、このようなケースも10秒以内に判定する必要があります。
解いてくれる人がいるか分からないが…
りんご拾い 実行時間制限: 10秒
N×Nのマス目があり、各マスにはりんごが落ちているか数字が書いてあります。
最初にあなたは左下のマス(1,1)にいます。
あなたは上下左右に隣接するマスに移動することができ、りんごのあるマスではりんごを拾うことができますが、数字の書いてあるマスにはその数字の分だけりんごを持っていなければ移動することができません。
あなたが右上のマス(N,N)まで移動できるかを判定してください。
制約
・入力
マス目のサイズ N
各マスの情報のリスト S = [S_1, S_2, … , S_N²]
Easy:1≦N≦10、Hard: 1≦N≦400であり、S_iは文字“a”または0以上N²以下の整数。
マス(i,j)はS_(i-1)×N+jに対応しており、この値が“a”であるときマス(i,j)にはりんごがあり、整数であるときマス(i,j)にはその整数が書いてある。
また、S_1は常に“a”または0である。
・出力
(1,1)から(N,N)まで問題文の条件を満たして移動できるならtrue、そうでなければfalse
結果例
入力:N=3, S=[0, 0, a, 1, 2, 2, a, 2, 0]
出力:true
(1,1)→(1,2)→(1,3)(りんごを拾う)→(1,2)→(1,1)→(2,1)→(3,1)(りんごを拾う)→(3,2)→(3,3)のように移動すればよいです。
入力:N=4, S=[0, a, 3, 0, 0, 0, 3, a, 0, 0, 3, 0, a, 0, 3, 0]
出力:false
左から2行目までにはりんごが2個しかないので、左から3行目のどのマスにも移動できないため(4,4)まで行くことはできません。
入力:N=400, テストケース, テストケース2
出力:true
Hard条件のもとでは、このようなケースも10秒以内に判定する必要があります。
Last edited by sakura_neko (June 13, 2025 16:15:11)
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#316 WA/TLEです。
・N=2, S=[0,0,1,0]のケース、trueのはずですがfalseと出力されます。
・N=3, S=[0,0,a,0,0,0,1,2,2]のケース、TLEです(実行が停止しないものと思われます)。
・(Hardで)N=400, 特定のケースで(上のケースに対する修正をいれてもなお)TLEです。
具体的には、下のN=10のケースを拡張したような場合にN⁴に比例する計算時間がかかります。(見やすさのためスペース区切りにしています)
S=[
0 0 0 0 0 0 0 0 0 0
0 100 7 100 6 100 5 100 4 100
0 100 a 100 a 100 a 100 a 100
0 100 100 100 100 100 100 100 100 100
0 0 0 0 0 0 0 0 0 0
0 100 3 100 2 100 1 100 0 100
0 100 a 100 a 100 a 100 a 100
0 100 100 100 100 100 100 100 100 100
0 0 0 0 0 0 0 0 0 8
0 0 0 0 0 0 0 0 8 0
]
一応テストケースを生成するプログラムを置いておきます。
あとこれは実装に関係ないですが、入力においてSの要素をN個しか受け取らないようになっています(N²個受け取る必要があります)。
解いてくれて嬉しいです
・N=2, S=[0,0,1,0]のケース、trueのはずですがfalseと出力されます。
・N=3, S=[0,0,a,0,0,0,1,2,2]のケース、TLEです(実行が停止しないものと思われます)。
・(Hardで)N=400, 特定のケースで(上のケースに対する修正をいれてもなお)TLEです。
具体的には、下のN=10のケースを拡張したような場合にN⁴に比例する計算時間がかかります。(見やすさのためスペース区切りにしています)
S=[
0 0 0 0 0 0 0 0 0 0
0 100 7 100 6 100 5 100 4 100
0 100 a 100 a 100 a 100 a 100
0 100 100 100 100 100 100 100 100 100
0 0 0 0 0 0 0 0 0 0
0 100 3 100 2 100 1 100 0 100
0 100 a 100 a 100 a 100 a 100
0 100 100 100 100 100 100 100 100 100
0 0 0 0 0 0 0 0 0 8
0 0 0 0 0 0 0 0 8 0
]
一応テストケースを生成するプログラムを置いておきます。
あとこれは実装に関係ないですが、入力においてSの要素をN個しか受け取らないようになっています(N²個受け取る必要があります)。
解いてくれて嬉しいです
Last edited by sakura_neko (June 13, 2025 02:18:21)
- sakura_neko
-
Scratcher
83 posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
#318 @Catapult-さん りんご拾い(Easy) 正解です!! FA!!
Hardに関して、このテストケース(#317のものとは異なります)でこちらの環境だと15秒程度かかってしまったので(もしそちらの環境で時間内に実行終了していたら申し訳ないのですが)TLEとさせてください…
Scratchのプログラムだとリストに対する削除・挿入操作は1ブロックで実装できますが、計算量的には最悪の場合リストの長さに比例する時間がかかってしまいます(最初の要素を削除する場合など)。
そのため、Catapult-さんのプログラムは1ブロックの実行にかかる時間を定数とみなすとN²に比例する計算時間となり十分高速ですが、一般には上のようなケースで最悪N⁴に比例する計算時間がかかるものとみなされると思います。
今回の条件だと、Catapult-さんのプログラムに適切な定数倍高速化をすればHardでも時間内に抑えることができると思いますが、実はこの問題はあるデータ構造を使うとN²logNに比例する時間で解くことができます。よければ考えてみてください。
Hardに関して、このテストケース(#317のものとは異なります)でこちらの環境だと15秒程度かかってしまったので(もしそちらの環境で時間内に実行終了していたら申し訳ないのですが)TLEとさせてください…
Scratchのプログラムだとリストに対する削除・挿入操作は1ブロックで実装できますが、計算量的には最悪の場合リストの長さに比例する時間がかかってしまいます(最初の要素を削除する場合など)。
そのため、Catapult-さんのプログラムは1ブロックの実行にかかる時間を定数とみなすとN²に比例する計算時間となり十分高速ですが、一般には上のようなケースで最悪N⁴に比例する計算時間がかかるものとみなされると思います。
今回の条件だと、Catapult-さんのプログラムに適切な定数倍高速化をすればHardでも時間内に抑えることができると思いますが、実はこの問題はあるデータ構造を使うとN²logNに比例する時間で解くことができます。よければ考えてみてください。
Last edited by sakura_neko (June 13, 2025 16:01:24)
- Catapult-
-
Scratcher
100+ posts
Scratchで競技プログラミング!(初めての人は最初の投稿をお読みください)
再び#315に解答します。定数倍高速化です。
https://scratch.mit.edu/projects/1188555193/
sakura_nekoさんのつよつよマシンならTLEしないことを願って…
https://scratch.mit.edu/projects/1188555193/
sakura_nekoさんのつよつよマシンならTLEしないことを願って…






