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

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

kwfumou

この記事は新歓ブログリレー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

この記事をシェア

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

関連する記事

2019年4月5日
1年で水色Coderかなーやっぱりww【新歓ブログリレー28日目】
Silviase
2019年3月16日
競技プログラミングを始めよう【新歓ブログリレー2019 8日目】
eiya
2019年3月14日
永続データ構造【新歓ブログリレー2019 6日目】
nari
2019年4月26日
traPへの入部、ありがとうございました!
Yosotsu
2019年4月25日
本【新歓ブログリレー2019 48日目】
xecua
2019年4月24日
gnuplotで遊ぼう
mds_boy

活動の紹介

カテゴリ

タグ