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

kakurenbo

#196 Coprime to Each Other に解答します。

https://scratch.mit.edu/projects/624134306
昨日一通り書いた後「あれぇ..どうやってオーバーフロー対策しよう…もっと効率的な手段があるのか…？」と悩んだ末に諦めてしまいましたが、まさかの制約変更と聞いて作り直しました。ちゃんと質問しておけばよかったと後悔中です…
追記：オーバーフローではないですね()

Last edited by kakurenbo (Jan. 6, 2022 03:36:35)

Yuulis

kakurenbo wrote:
#196 Coprime to Each Other に解答します。

https://scratch.mit.edu/projects/624134306
昨日一通り書いた後「あれぇ..どうやってオーバーフロー対策しよう…もっと効率的な手段があるのか…？」と悩んだ末に諦めてしまいましたが、まさかの制約変更と聞いて作り直しました。ちゃんと質問しておけばよかったと後悔中です…

ACです。
制約変更ごめんなさい。Scratchへの無知が露呈した… 以後気を付けます

Yuulis

#196 Coprime to Each Other - 解答
https://scratch.mit.edu/projects/624054293/

まんまオイラー関数φ(n)の問題。知っていたらすぐできたかもしれないが、一応導出も。

(1)
1からP^K までのP^K個の自然数のうち、条件を満たす自然数は、「Pの倍数でない」もの。
Pの倍数は(P^K) / P = P^(K-1) 個ある。
したがって、f(P^K) = P^K - P^(K-1) である。累乗のプログラムは素直に実装する。(制約がガガガ)

(2)
X ≠ Yより、1からX*Y までのX*Y個の自然数のうち条件を満たすのは、「Xの倍数でもYの倍数でもない」もの。
Xの倍数は、 X, 2X, 3X, … , (Y-1)X, Y*X のY個。
Yの倍数は、 Y, 2Y, 3Y, … , (X-1)Y, X*Y のX個。
XYの重複に注意して(ベン図を書くとわかりやすい)、f(X*Y) = X*Y - (Y+X-1) = X*Y - Y - X + 1 = (X-1)(Y-1) である。

NT_ZZzz

#188 びっくりサイン(Hard)に回答します
https://scratch.mit.edu/projects/628562283/

hirayuu1414

#210
これは面白いw正解です。

NT_ZZzz

第1兆項実行時間制限:1秒
数列Aは以下のように定義されます。
・初項が a である
・全ての整数 i ( i ≧ 1 ) において、第i項が X であるとき第i+1項は bX^2+cX+d である
a,b,c,dが与えられるので数列Aの第1兆項を 997 で割ったあまりを求めてください。
制約
-10^12 ≦ a ≦ 10^12
-10^12 ≦ b ≦ 10^12
-10^12 ≦ c 10^12
-10^12 ≦ d ≦ 10^12
a,b,c,d は全て整数
結果例
入力 a=1,b=0,c=1,d=1
出力 81
この数列の第1兆項は1000000000000であり、これを997で割ったあまりである81を解答すれば良いです。

入力 a=1234567890,b=0,b=0,d=3
出力 3
この数列の第1兆項は3であり、これを997で割ったあまりである3を解答すれば良いです。

入力 a=1,b=1,c=1,d=1
出力 31
この数列は初項から順に 1,3,13,183,33673,… と続いていきます。

入力 a=-1000000000000,b=-1000000000000,c=1000000000000,d=1000000000000
出力 87

watashida

#212 第1兆項に解答します
https://scratch.mit.edu/projects/648714111/
(最初FPSかと思ったけど，そんなことはなかった (FPSでも殴れる))

NT_ZZzz

watashidaさん第1兆項 Accepted! 正解です! FA!

そのlog外せませんかという気持ちになっています。きちんと制約を作れば落とせた気がしています。

Last edited by NT_ZZzz (Feb. 23, 2022 05:23:39)

inoking

NT_ZZzz wrote:
#188 びっくりサイン(Hard)に回答します
https://scratch.mit.edu/projects/628562283/

今さらですが、これに乗っかって、、
#188 びっくりサイン Scratchで競技プログラミング！最速版？
※半分ネタです。
↓
最速と思ったが、一部加工が必要だったため NT_ZZzz さんのと変わらないかも。

追記：
NT_ZZzz さんのときから対応できていなかった x が 0 の場合に対応しました。

Last edited by inoking (Feb. 24, 2022 21:11:24)

Poteto143

お知らせ
#2の問題リストを大きく改修し、見やすくしました。
また、新たに投稿された2題をリストに反映しました。

ちなみに、今までに投稿された問題数が20問を超えました！いつもこのトピックを利用していただきありがとうございます！

Poteto143

お知らせ
Turbowarpおよび第三者によるScratchのModの扱いについてです。
それらのModでは演算をはじめとするプログラムの仕様が純正のScratchと全く同じであることが保証できません。
よって、あらかじめ本トピックでは作問時と回答時のModの使用を禁止とします。
作問と回答は必ず純正のScratchで行うようお願いします。

Poteto143

追記: #217に伴い#1に加筆を行いました。

kakurenbo

age もかねて
Egotistical Dictionary? 実行時間制限: 2秒
※Hard(通常) と Easy があります。

問題文
　とある星には，ふぬけ国王の治めるふぬけ王国があります．
　ふぬけ王国には N 個の文字があり，A はそれらをふぬけ王国での辞書順に基づいて最小になるように並べ替えたものです．

　ところで，国王は辞書を引くのがとても遅く，辞書が嫌いになりました．
　そこで国王は「見出し語の順番を変えれば，辞書を引きやすくなるのではないか」と考え，知恵がある召使いを一人呼び出し，自分の要求を満たすような辞書を作ってもらうことにしました．

　国王の要求は以下の通りです．
　(ただしここでいう「見出し文字」とは，辞書の“つめ”の部分に書かれている文字であるとします．つまり従来の一般的な辞書では，見出し文字は辞書順に並んでいることになります．)

見出し文字を順番に書き並べた文字列が，ふぬけ王国での辞書順でなるべく大きくなること．
Q 個の文字列 S[1], S[2], …, S[Q] について，その文字列に含まれる文字がそのまま順番で見出し文字に現れること．
より厳密には，T = S[i] (1 ≦ i ≦ Q) としたとき，全ての k (1 ≦ k ≦ |T | - 1) において文字 T[k] が文字 T[k+1] よりも見出し文字として先に現れること．

　あなたの仕事は，この召使い君の代わりに国王の要求を満たす辞書の見出し文字の順番を考えてあげることです．

制約

2 ≦ N < 100 (入力には与えられない)
1 ≦ Q ≦100
2 ≦ |S[i] | ≦ N (1 ≦ i ≦ Q)
A, S[i] (1 ≦ i ≦ Q) には
半角英数字(小文字)，ひらがな，カタカナ，記号「,」「.」「!」「?」「、」「，」「。」「．」「？」「！」
のみが含まれる．(Scratch において「1文字」とカウントされる文字)
A の各文字は相異なる．
S[i] (1 ≦ i ≦ Q) は A に含まれる文字のみを含む．
S[i] (1 ≦ i ≦ Q) において，同じ文字は 2 つ以上連続しない．

入力
　A, Q, S[1], S[2], …, S[Q] がこの順番で与えられる．

出力
　ふぬけ国王が使う辞書としてふさわしい(国王の要求を満たす)見出し文字の並びとなるように A を並び替えた，長さ N の文字列を出力(適当な変数へ代入するか，リストに追加して表示)せよ．
　ただし，どのように A を並び替えても国王の要求を満たすことができない場合は，「-1」を出力せよ．

結果例
入力例 1:

A: 12345  Q: 2  S[1]: 21  S[2]: 235

出力例 1:

　2 が 1 よりも先に現れ，2 が 3 よりも先に，3 が 5 よりも先に現れるような A の並び替えとして 21354, 23145, 42315, 42135 などがありますが，その中で(ふぬけ王国での)辞書順が最大となるのは 42351 です．

入力例 2:

A: abcdefghijklmnopqrstuvwxyz  Q: 5  S[1]: aiueo  S[2]: jisho  S[3]: kane  S[4]: ai  S[5]: king

出力例 2:

zyxwvtrqpmlkjfdcbaiusnhgeo

入力例 3:

A: あかさたなはまやらわいきしちにひみゐりうくすつぬふむゆるえけせてねへめゑれおこそとのほもよろをん
Q: 5  S[1]: あいうえお  S[2]: かきくけこさしすせそ  S[3]: たちつてとなにぬねの  S[4]: はまやらわ  S[5]: わおん

出力例 3:

をろよもほれゑめへるゆむふりゐみひはまやらわたちつてとなにぬねのかきくけこさしすせそあいうえおん

　A が地球での辞書順最小に一致しているとは限りません．

入力例 4:

A: abc
Q: 3  S[1]: ab  S[2]: bc  S[3]: ca

出力例 4:

-1

　召使い君がどのように頑張ったところで，国王を満足させることはできません．

入力例 5:

A: あいうえおかきくけこさしすせそたちつてとなにぬねのはひふへほまみむめもやゐゆゑよらりるれろわをんがぎぐげござじずぜぞだぢづでどばびぶべぼぱぴぷぺぽぁぃぅぇぉっゃゅょゎ、。！？
Q: 7  S[1]: すくらっちで  S[2]: きょうぷろの  S[3]: もんだいを  S[4]: とくのも  S[5]: また  S[6]: たのしい  S[7]: よね？

出力例 5:

！。、ゎゅゃぉぇぅぃぁぽぺぴぱぼべぶびばどづぢぞぜずじざごげぐぎがわれるりよゑゆゐやめむみまほへふひはね？ぬになとてつたそせすさこけくらっちできょかおえうぷろのもんだしいをあ

後日談
　召使い君があまりに難しすぎると泣きついた結果，国王は「辞書順で最大にならなくてもよい」と妥協案を示しました．
Easy: 答えは(ふぬけ王国での)辞書順で最大にならなくてよい．すなわち，少なくとも，国王による 2 つ目の要求を満たすもの(一意に定まるとは限りません)のうち一つを出力せよ．

一言：(方針にも依りますが)実装量は若干多いと思います。“Scratch 特有の難しさ” もあるかもしれません。(なおヒントになってしまうかもしれないので，推定難易度は解説と同時にご紹介します。)
#1 曰く難易度は制約以外の部分で分割してもいい…はず。(まずかったらプロフィールなどで教えてください。)

Last edited by kakurenbo (April 6, 2022 11:20:34)

kakurenbo

#219: Egotistical Dictionary?

Easy 用の出力チェッカーを公開しました。
以下の点に留意してご利用ください。

Easy 用です。条件(国王の要求)のうち 1 つ目については検証しません。
「-1」の出力が正しいかどうかの判定には対応していません。(一律 WA が出ます。)
出力に対する入力はすべて正しいものとして検証を行います。すなわちテストケース自体の正当性の検証は行いません。
全探索なので遅いです。
バグがないとは言い切れません。もし発見した場合は，件のプロジェクトか私のプロフィールのコメント欄にその旨を書いていただけると助かります。

また，私の技術では Hard の出力チェッカーを，コードから解答を導けないように対策しつつ実装することができませんでした。これについて知見のある方がいらっしゃれば，(解答公開後に)私のプロフィールにてお話をしましょう()

Last edited by kakurenbo (March 24, 2022 01:38:49)

sakura_neko

#219 Egotistical Dictionary? Hard(通常)に解答します
https://scratch.mit.edu/projects/664485322/

入力例の5、「う」が「あいうえお」と「わゐうゑを」の二か所あり、制約に反してるみたいです。

kakurenbo

あぁっ！確認したつもりが，いつもの癖で入れてしまっていたみたいです…
ご迷惑をおかけして申し訳ありません。。

改めまして
@sakura_neko さん Egotistical Dictionary?(Hard) AC です，FA！おめでとうございます！
想定解よりも簡潔な実装で素晴らしいです。また，-1 となるケースの検出が特に速い印象でした。
(なお，Hard の要求は Easy のそれも同時に満たすため，Easy も FA は @sakura_neko さんとなります。)

–お知らせ–
ご指摘を受けたため，入力例 5 の A，及び出力例 5 を修正いたします。

また，制約を一部変更します。
具体的には，|S[i] | (1 ≦ i ≦ Q) の範囲を N 以下に制限します。
並びに下記の内容を加えます。

S[i] (1 ≦ i ≦ Q) は A に含まれる文字のみを含む．

Last edited by kakurenbo (April 6, 2022 08:40:02)

sakura_neko

Complex Anagram 実行時間制限: 2秒
@kakurenboさんの設定をお借りします
とある星にある, ふぬけ国王の治めるふぬけ王国では, 国王の主催する「アナグラム大会」が開催されています. 国王は知恵のある召使いに応募されたアナグラムの精査をさせていますが, 一つ一つ文字を追うのは大変です. あなたの仕事は,アナグラムの文字がどこへ移動しているのかをリストにすることです.
入力
文字列A, Aを並べ替えた文字列B
出力
リストL(k):「Bのk番目の文字」のA中の位置
制約
A(B)に重複する文字は含まれず, 文字種はテストケースを参照.
Aの長さは5000以下の自然数. （結構大きいため、実行時間注意）
結果例
例1)A=silent, B=listen
→L=3,2,1,6,4,5（Bの1文字目「l」はAの3文字目に、…）
例2)A=1938274650, B=7608125394
→L=6,8,10,4,1,5,9,3,2,7

sakura_neko

今更ですがブロック数111リスト1定義1で実装できたので
#87 ナベアツアツ数に解答します
https://scratch.mit.edu/projects/666332040/

kakurenbo

#223 Complex Anagram に回答します。
https://scratch.mit.edu/projects/672001413/

オーダー |A|^2 で間に合わなかったのはちょっと意外でした。Scratch って思いの外遅いんですね。
定数倍は若干重めですがオーダー |A| なのでおそらくどの環境でも間に合うと思います。(それでも実行時間制限ギリギリ)

追記：リストの表示非表示ってそんなに影響が出るのですね。(若干速度に影響を及ぼすことは存じていましたが，ここまでとは)

Last edited by kakurenbo (April 6, 2022 13:48:49)

sakura_neko

#225 @kakurenboさん Complex Anagram ACです。FA!
追記：どうやらリスト・変数の表示/非表示で結構実行時間に差が出るみたいです。
解答のリストのみ表示するようにすると、実行時間が6割くらいに落ちました。

Discuss Scratch