古生代の歴史
この記事は、もすーんアドベントカレンダー12月2日に掲載するために書きました。
人間が誕生する何億年も前、恐竜の時代よりもはるか前、古生代と呼ばれる時代がありました。
今回は古生代の歴史について、ほとんど何も知らないですし調べるほどの気概もないのですが、朝てきとうに考えた結果そういうタイトルにしてしまったので、知っている範囲で書きたいと思います。
6億年ほど前、地球は急速に寒冷化し(全球凍結)、氷が解けた後多細胞生物が大進化を遂げました。カンブリア大爆発と呼ばれます。
その後生物は新たな生息先を陸上に求め、両生類や爬虫類や昆虫が栄えました。
しかし、古生代の最後に大量の生物が絶滅(ペルム紀末期の大量絶滅)、生物の進化はやり直しになってしまったわけです。
以上です。何も知らないのが露呈してしまいました。三葉虫はしってます。「君の名は」のヒロインは三葉虫です。
ごはんのおともについて
この記事は、もすーんアドベントカレンダー12月1日に掲載するために書きました。
ごはんは炭水化物を効率的に摂取できますが、飽きてくるため、なにかとセットにすると食べやすいです。これをごはんのおともと呼びます。
ごはんのおともを分類します
・甘い
ごはん自体が甘いので、あまり好まれないように思います。
おかゆなどにすると甘みが増幅されるかもしれません。
・辛い
ラー油やキムチなどです。
辛いものが好きな人はなんでも辛くしないと気に食わないので、ごはんも当然辛くします。
・すっぱい
梅干しなどが伝統的です。
ごはんの安直なおいしさへのアンチテーゼとして少しの酸味を混ぜるとコクが出ます。
・しょっぱい
味噌、塩昆布など多くのごはんのおともが該当します。
甘いものとしょっぱいものは、嗜好品の二大巨頭ですから、それらを合わせれば鬼に金棒というわけです。
・苦い
イメージが掴めないです。わたしは苦みにとても鈍感なので、みなさんが苦いと思っているものがあまり苦くなかったりします。もし苦いごはんのおともがあればおしえてください。
※追記
魚のはらわたは苦いというご指摘をいただきました。ありがとうございます！
・納豆
邪道です。単品で食べるのは好きです。
以上です。みなさまもごはんを食べるときはこの記事をご活用ください。
YouTubeはじめました
Twitterでも宣伝しましたが、YouTubeへの動画投稿をはじめました！
どきんちゃんねるでは、競技プログラミングの動画を投稿していきます！
動画の内容
競技プログラミングのメディアコンテンツはすでにかなり充実しています。
ABCの公式解説放送、かつっぱさんの解説動画、けんちょんさんをはじめとした色々な方の解説記事などがあります。
そのような群雄割拠の競プロコンテンツの中で、わたしが不足していると感じているのは、競技プログラミングをはじめたてで、まだプログラミングやプログラミング的思考に慣れていない方のための解説記事です。
競技プログラミングは誰でも気軽に始められる一方で、簡単とされる問題に対しても求められることが多く、そこで諦めてしまう人が多いのではないかと思います。
例えば、A問題では、文字式の計算、条件分岐との組み合わせ、切り捨て、切り上げ、小数、文字列の性質判定、整数問題などに対する理解が求められていますが、これら一つ一つは、例えば中学校なら一か月くらいかけて教えるレベルのことだと思います。
そこで、私のYouTubeチャンネル「どきんちゃんねる」では、A問題やB問題ではどのようなことが求められているか、どのように対策していけばよいのかをお話ししながら、若い方や初心者に向けて、プログラミング的思考の楽しさについてお伝えできればと思います。
わたしのツイッターをご覧になっている方は、すでに競技プログラミングを始めている方や、プログラミング的思考に慣れている方がほとんどだと思うので動画の対象外にはなりますが、プログラミングを始めようとしている方がもしまわりにいらっしゃれば、AtCoderと併せて宣伝していただけるととてもありがたいです。
人気YouTuberに向けて
YouTubeに動画を出す以上、再生回数、チャンネル登録者数がどうしても気になります。もちろん、収益化を目指したいとも思っています。
そのために心がけたいことを列挙します。
量と質の両立
動画編集をして気づいたことなのですが、動画の質を高めることはいくらでも可能です。
動画をみていて気に食わないところがあれば適宜修正する、というのを繰り返していけば、どんどんクォリティが上がっていきます。
しかしそれだといつまでたっても動画を公開できず、投稿頻度が遅くなってしまう。
人気YouTuberは、最低限の質が担保された動画を毎日のように投稿することで生計を立てているわけです。
そこで、私も編集手順をできるだけ固定化し、短期集中で質の高い動画を作れるように努力していきたいと感じています。
今のところ、丸1日かければ2本の動画を作ることが可能だと考えているので、このペースを維持しつつ、毎週の動画投稿を目指します。
顔出し
個人的に、顔出しyoutuberの方が好きなので、私も顔を出しています。
顔もわからない謎の人物が動画投稿していると、不安感があったりもします、、、
プログラミングをはじめようとして私の動画を見る方はお若い方が多いでしょうから、生身の人間が動画投稿しているのだとわかると、親近感がわくのではないかと考えています。
顔出しする以上、当然美人な方がよいので、日々のスキンケアなりメイクなりを頑張っていきたいです。
はっきり話す
わたしは滑舌がとても悪いので、話し方にかなり苦戦しています。
画面の向こうにいる方のことをつねに考えながら、自分の伝えたいことをしっかり伝えられるように、練習したいです。
わかりやすさとテンポの良さの両立
初心者に向けての動画ですから、出来る限り疑問点がでないように、「これさえ見れば完璧に理解できる！」動画を作りたいと考えています。
一方で、YouTubeでは動画のテンポが大事です。だらだらと説明してしまっては、授業のようになって嫌気がさしてしまいます。
もちろん授業をdisっているわけではありませんが、YouTubeの動画は簡単に見るのをやめてしまえますから、飽きさせない工夫が重要です。
話したいことのテーマを決めて、一本の動画を通してそのテーマをしっかりお伝えできればと思っています。
情報収集
我流は良くないので、人気youtuberの方の動画をたくさん見て、よいところがあれば参考にしていきたいと考えています。
その一方で、なんでも参考にしすぎてわけがわからなくなるのは良くないので、自分を見失わないようには心がけたいです。
そういう意味では、邪悪ではありますが、むしろ悪いところを探して反面教師にするという使い方でもよいのかなと思っています。
動画作成の手順
現在は、「どきんの精進！競技プログラミングA問題編」と題して、A問題の解き方を解説する動画を作成しております。
動画のテーマ決め
過去のA問題(100点問題)にほぼすべて目を通し、テーマを分類し、各テーマごとに代表となる問題を一つ選ぶという作業をします。
一本の動画では一テーマについて代表となる一問を解説し、残りの問題についてはバチャ形式で解く動画を別撮りします。
この作業はある程度完了しており、あとは問題を選ぶのみな状態です。
スライド作成
パワーポイントを用いて、問題を解説する動画を作成します。
「問題文→サンプル→考察と方針→実装→まとめ→よくある間違い→類題紹介」の流れです。
1枚のスライドに情報をつめこみないよう、A問題に必要な最低限の知識だけを伝えるように心がけています。
イラストには、イラストACのものを使用しています。
アフレコ
OBS Studioを用いて、パワーポイントに声をアフレコします。
言葉に詰まるのはあとで編集すればよいだけですが、早口になりすぎないようにするのが大変です。
イントロ動画撮影
動画の概要を紹介するイントロ動画を撮影します(何回分かまとめ撮りします)。
部屋が汚く暗いので、ライト二台体制でなんとか体裁を保っています。
第一回の動画は、カメラの角度が悪くあまり美人に見えないうえにブレもあったので、次回以降は修正したいです。
面白いことをいう動画ではないので、特にボケる予定はないです。
バチャ動画撮影
AtCoderProblemsを用いて問題をまとめ、バチャを実況解説します。
長丁場なので、リラックスして話すことを心がけたいです。
タイピングは少し練習しましたが、あまりスムーズな実況には生かされていないように思います。
編集
Filmoraを用いて撮った動画を編集します。
具体的には、動画をインポートし、「イントロ動画→タイトル画像→スライドアフレコ→チャンネル登録呼びかけ画像」の順に並べて、余計な間をカットします。
さらにBGMを入れて音量を調整し、必要に応じてテロップをいれます。
テロップですが、プリインストールに簡単な字幕とやたらハイクォリティな字幕しかなくて、ちょうどよいものがなさそうなのですよね、、、どうしましょう、、、
BGMには魔王魂のものを使用しています。
バチャ動画については、カットはほとんどせずBGMとテロップを入れるだけです。
サムネイル作成
canvaを用いてサムネイル画像を作成します。
既にテンプレートがあるので、それを差し替えるだけで終わります。
動画のアップロード、概要欄などの設定
動画のアップロードですが、意外とお時間がかかってしまいます。その間は特に何もできないので、虚無です。
アップロードが終わると、概要欄に説明を書いたり、サムネイルを設定したりします。
数学的事項は動画内で説明しきるのが難しく、既に良い動画が世の中に出回っているので、関連動画を探してリンクしたりします。
公開
公開して、Twitterで宣伝します。
公開時間は何時ごろがよいのでしょう？初回動画は19時すぎに公開しましたが、ごはん時と重なりあまりよくなかったように思います。
初回動画はchokudaiさんにツイートしていただき、予想よりも多くの方に見ていただくことができました。ありがとうございました。
ABC182 感想
ABC182に出場しました。
全完+2ペナ(59:20)、順位は56位でした。
途中ネット接続が切れてしまい、Dの一度目の提出前に10分ほど離脱してしまいました。
ABCなので、そのあとは落ち着いてのぞめましたが、ARC,AGCなら発狂しているところでした。
今後は、万が一そういうことがあっても、残りの問題の考察ができるよう、試験が始まったら問題を全部開くようにしたいと思います。
A問題
書かれている内容を理解して整理するのに時間がかかるタイプの問題です。
しかしながら、実は制約を見るだけで答えがエスパー出来ます(ペナを出すと5分失うので、あまりお勧めできる方法ではありません)。
0:46でAC
B問題
B問題なので、あまり何も考えず全探索です。この問題は、制約が大きい場合でも解くことができそうです。
3:29でAC
C問題
前回は8の倍数判定ですが、今回は3の倍数判定です。各位の和が3の倍数になるようなもののうち、もっとも長さの長いものをbit全探索で求めます。
この問題も、制約が大きい場合を考えると面白そうです。
最後の詰めでミスをおかし、1ペナです。
8:22でAC
D問題
(累累積和)+(累積和のmax)の最大値を計算します。
N=1の場合に誤った出力をしてしまい、1ペナです(たぶん実装方針が悪かったです)。
28:32でAC(途中ネット接続が切れていました)
E問題
各電球が照らす領域を全探索します。
普通に探索すると、O((H+W)HW)になってTLEします。
そこで、途中で探索を打ち切ることを考えます。
別の電球に到達したら探索を打ち切ることによって、各マスにつき高々4方向しか探索されないので、O(HW)になって間に合います。
類題でございます。
atcoder.jp
35:37でAC
F問題
各硬貨は、「店員⇒ルンルン」「ルンルン⇒店員」「移動なし」の3通りです。
これを小さいものから順番にDPで数え上げていけばよいです。
(小さい順にDPするのは、実際にお金を払うときのことを思い出せば察しが付くと思います)
はじめ「借金X円」の状態から、iを増やしていくとルンルンの借金が変化していくわけですが、i番目までみたとき「借金[X/A_i]円」「借金[X/A_i]+A_i円」の二通りしかないことがわかるので、状態をまとめることができO(N)でとけます。
N<=50なのにO(N)で解けて変な気持ちになりますが、これはA_iのオーバーフローを避けるためなので、実はあまり気にしなくてOKです。
類題でございます(最適化か数え上げかの違いだけで、同じ解法です。)
atcoder.jp
49:20秒でAC
まとめ
おもしろかったです！！！
HTTF2021予選参加記
Future社主催のマラソン型コンテスト、HTTF2021の予選に参加しました。
コンテスト時間は8時間で、上位は本選進出権が与えられるほか、飛び賞もあるそうです。
参加記
限られた時間の人生でマラソンにまで手をまわすのはたいへんそうだったので、当初は参加するつもりはなかったのですが、ツカモさんが「色々な楽しみ方ができる」とおっしゃっていたので参加することにしました。あーだこーだーでツカモさんのお姿を拝見することができますが、すごく聡明でイケメンな方でした(私が勝手な評価をする立場にはないです)
コンテスト開始後、参加者が13万点くらいをとっていたので、たぶんこれが愚直コードだと思いました。
というわけで某動画のラストシーンに出てくる点数を狙いにいこうと思ったのですが、chokudaiさんがその動画を苦手にされていることを思い出し、やめました。
まずは最低点を狙いに行きました。
1点がとれそうなコードを書いて提出したら、少し甘い部分があり2点になってしまいました。つらいです…1点が好きなので…
3時34分ごろにねむくなってきたので、お昼寝ターイム！をして、おきたら9時前になっていました。は？
2点のコードを少し修正したら334点が取れそうだったので、取りました。
おわりです！
解法
2つのテストケースで167点、残りのテストケースで0点をとればよいです。
入力からハッシュ関数を通すことで、テストケースがちょうど2つになるように抽出します。
2つのテストケースでは愚直解をかき、操作の後ろの方で無駄な往復を何回かして167点になるように調整します。
残りの48個はむにゃむにゃして0点をとります
ただし、移動回数の偶奇は決まっているので、ちょっとがんばる必要はあったりとかもします。
おわりです！
おわりに
みなさんがマラソンをしているなか、私はコスプレではじめの100メートルだけ走ってリタイアするみたいな人間になってしまい、恥ずかしいです。次回もがんばりましょう。
競プロキャンプ2020参加記
競プロキャンプ2020に参加したので、出来事をまとめます。
朝起きて身支度を行い、宇治に向かいました。
昼ごはんの会場につくと、もうすでに全員集まっていました。わたしが最後だったようです。
お昼ごはんを食べていると、閉会式が始まりました。
閉会式が終わって、平等院鳳凰堂に向かいました。
そこで流れ解散となり、平等院鳳凰堂を出て数人の方々と近くのカフェに入りました。
アイスを注文して食べました。
そのあと、京阪電車に乗り他の方々と別れて一人になりました。
そのころ相撲では正代が優勝しました。
晩ごはんをどうしようか悩んでいたところ、友人が近くにいるとのことだったので一緒に晩ごはんを食べました。
家に帰って別の友人とビデオ通話しました。
21:00になったので半沢直樹を見ました。
お風呂に入った後、ちょうどCodeForcesの時間だったので参加しました。
冷えて橙に落ちました。
以上です。
印象に残ったのは、スギノキさん、のいみさん、いずらいとさんがとてもお美しかったことです。その裏には、常日頃から美容と健康を意識した生活があるのだと思います。わたしはついつい怠けてしまいますが、少しでも近づけるように努力をしていきたいものです。
最高のキャンプを運営してくださった幹事のみなさま、ありがとうございました。
B問題の傾向と対策
はじめに
前回の記事の続きです。
今回は、ABCのB問題について、分類・考察していきます。
B問題の分類
対象はABC126～ABC178(現在の6問形式で開催されるABC)です。問題の解き方のネタバレが載っているので、閲覧注意でお願いします。
1重for文による全探索
B - Algae:順に計算し出力
B - Uneven Numbers:数え上げ
B - FizzBuzz Sum:条件を満たす値の和
配列(数列)の扱いと全探索
B - Bounding:数え上げ
B - Ordinary Number:数え上げ
B - Buffet:複雑な処理の実装
B - Roller Coaster:数え上げ
B - Common Raccoon vs Monster:配列の要素の和
B - Papers, Please:Yes/No判定
B - Homework:配列の要素の和
B - Judge Status Summary:文字列からなる配列、数え上げ
B - Distance:幾何、数え上げ
配列に対するより複雑な考察
B - 0 or 1 Swap:条件の置き換え、Yes/No判定
B - Achieve the Goal:平均値
B - Popular Vote:和の計算、数え上げによるYes/No判定
文字列の扱いと全探索
B - YYMM or MMYY:判定
B - Tap Dance:YesNo判定
B - Echo:YesNo判定
B - ROT N:文字列の置換、文字コード
B - Palindrome-philia:数え上げ
B - Strings with the Same Length
B - Count ABC:数え上げ
B - I miss you...:文字列の置換
B - String Palindrome:回文判定
B - ... (Triple Dots)
B - Minor Change:数え上げ
B - Multiple of 9:整数を文字列として受け取る
2重for文、全探索
B - Balance:最小値
B - Bite Eating:和の計算と最小値
B - Good Distance:幾何、数え上げ
B - TAKOYAKI FESTIVAL 2019:和の計算
B - 81:全探索によるYes/No判定
B - Trick or Treat:数え上げ
B - Substring:文字列、数え上げたものの最小値
3重for文による全探索
B - Making Triangle:数え上げ
ソート
B - Guidebook:pair型のソート
B - Mix Juice
数学的な問題
B - Golden Apple:状態の考察
B - One Clue:状態の考察
B - Power Socket
B - Greedy Takahashi:シミュレーション
B - Comparing Strings
B - Count Balls:大きな数に驚かない。余りによる場合分け。
B - Golden Coins:最適化の考察
B - Battle:シミュレーション、場合分け
B - Easy Linear Programming:場合分け
B - Crane and Turtle:全探索でも解ける
B - Product Max:最大値
その他
B - Resistors in Parallel:小数型の扱い
B - Digits:整数の桁の和
B - Bingo:複雑な実装の処理
B - Multiplication 2:コーナーケースの場合分け、オーバーフロー
B - 1%:小数型の扱い、while文
考察
前回の記事でも述べましたが、C++とPythonでは大きく言語仕様がことなるので、勉強方法も当然変わってくると思います。
このブログではC++での学習を仮定しています。
B問題では、A問題とは異なり、for文や配列を用いた問題が出題されます。
これらを用いることで、プログラミングの幅が一気に広がります。
いきなりB問題を解くのは難しいので、A問題のうち、以下のような問題をfor文や配列で解くのがよい練習になると思います。
おすすめの問題
A - We Love Golf:for文
A - Five Variables:配列
A - Lucky 7:文字列に対するfor文
A - Security:文字列に対するfor文
for文や配列を用いる問題についても、難易度にはかなりバリエーションがあります。
条件をみたすものの数を数える、配列の合計値を求めるといったシンプルな処理を指示通りに書けばよい問題から、じっくりと考察して正しい解き方を自分で考えないといけない問題まで、それぞれです。
つづいて文字列ですが、こちらもA問題以上の知識や実装力が要求されます。
具体的には、
- 文字列の長さの取得方法
- 部分文字列の取得方法
- 文字列上でのfor文の利用
などです。
ソートに関して、該当の問題が2問ありましたが、B問題の時点ではあまり必要な知識ではないと思います。ただし、決して難しくはないので覚えてしまってもよいと思います。
数学的な考察を行う問題についてですが、やはりA問題より高い水準の洞察力が要求されます。
難しい知識はあまり必要でないので、サンプルなどをもちいて実験し、法則を見つけ出すとよいでしょう。
また、数学的に解くか、for文を用いて解くかの正しい判断が必要な問題もあります。
もちろん、A問題と同様、
- 独特の問題形式に対する慣れ
- バグが出たときに、どこが間違えているかを見つけ修正する能力
- どうやって実装するか忘れたときに、インターネットの海から正しい情報を見つける能力
をさらに高めていく必要があります。
とくに、B問題では入力の与えられ方がA問題よりも複雑になっています。
B問題まで安定して解ければ、わたしはプログラミングができると自信をもって言えるレベルに達しています。
茶色コーダーまではもうすこしステップアップが必要です！
