feature image

2019年4月19日 | ブログ記事

ScratchでABCのD問題を解いてみた

この記事は新歓ブログリレー2019の40日目の記事です。

はじめまして、kwfumouです。
今回は、Scratchというプログラミング言語でAtCoder Beginner ContestのD問題を解いてみようと思います。

こんなことをした理由

最近、小学生にプログラミングを教えるバイトを始めたのですが、そこではScratchというプログラミング言語が使われていました。ryuon君が一昨日の記事でも取り上げていましたし、ここでは詳しい説明は省きますが、プログラミングに全く触れたことのない人にも扱いやすい言語です。
このScratchで競技プログラミングの難しめの問題を解いてみれば、基本的なことを学ぶだけでも十分に競プロを楽しめることを実感していただけるかなと思い挑戦してみました。

ABC123-D "Cake 123"

問題、解答はこちらで読むことができます。ぜひ、皆さんも挑戦してみてください。
リンク:ABC123-D
なお、この記事ではScratchで使える文法だけで、解答となるプログラムを記述できることをお伝えすることが目的であるため、解答に至るプロセスなどは省略させていただきます。

関門

越えなければいけない関門は、

  1. 値の入力
  2. ソート(ヒープソート)
  3. ソートしたリストの要素から、新しいリストを作る

この中では、圧倒的に2つ目のソートの実装が大変でした…

値の入力

blog_input
こんな感じで、入力はすんなりと行きました。

ヒープソート

blog_sort
c++だったら1行で終わるのですが、大変長くなってしまった。
このソートを合計3回行う必要がありました。こういう機会でもないと、ソートのプログラムを1から組むことなんてないので、いい経験になりました。

新たなリストの作成

blog_create
こちらも、繰り返し文を使えば、すんなりと書けました。

プログラム全体

blog_whole
blog_whole2

実行してみる

実は、Scratchで作ったプログラムをc++に書き換えてAtCoderでジャッジしてもらうことができるのですが、この問題に関しては、プログラムを書き換えるためにかなりの実行時間がかかってしまうみたいなので、今回は問題のページにある、入力例3で試してみたいと思います。

入力
10 10 10 20
7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488
1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338
4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736

出力
23379871545
22444657051
22302177772
22095691512
21667941469
21366963278
21287912315
21279176669
21160477018
21085311041
21059876163
21017997739
20703329561
20702387965
20590247696
20383761436
20343962175
20254073196
20210218542
20150096547

実行してみると、
blog_ans

一応、正しい答えが出てくれました!

終わりに

大学に入って初めて自分のパソコンを持ったため、プログラミング経験はもちろんありませんでしたが、そんな私でも基本的な事項をさっと学んで、競プロを楽しめるようになりました。
数学、特に組み合わせや確率の分野が好きだった人は、本当にはまると思います。ぜひ、挑戦してみてください。
人生初のブログということで、非常に拙い内容になってしまったかとは思いますが、ここまで読んでくださってありがとうございました。

明日はnambatsuさんの記事です、お楽しみに!

kwfumou icon
この記事を書いた人
kwfumou

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2019年4月22日
アセンブリを読んでみよう【新歓ブログリレー2019 45日目】
eiya icon eiya
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2021年4月26日
CPCTF2021 作問者writeup by hukuda222
hukuda222 icon hukuda222
2021年4月25日
CPCTF2021 作問者writeup by xxpoxx
xxpoxx icon xxpoxx
2019年4月16日
Logicのすヽめ+新歓コンピ宣伝
SolunaEureka icon SolunaEureka
記事一覧 タグ一覧 Google アナリティクスについて