今までAtCoderで経験した典型問題への解答のジャンル別整理

ここ半年ほど、AtCoder Beginner Contest(通称ABC)に参加することを継続している。

 

ABCに参加する主な目的としては、競技プログラミングを通じてアルゴリズムとデータ構造に関する教養をつけることと、それを客観的に示すことだ。

 

2020年2月9日現在のレートは506で、茶コーダーになっている(コンテスト実績で確認できる)。ただ最近、思っていたよりもパフォーマンスがでない。特にD問題以上になると以下の2点がボトルネックになっている。

  1. そもそも解法が思いつかない
  2. 解法はすぐに思いつくが、実装に時間がかかる

個人的には最低でも緑、がんばって水色まで行きたいので、上記2点に何らかの手をうちたい。1に関してはAtCoder Problemsでひたすら過去問を解いていく必要があるだろう。2に関してはC++14の言語仕様や、ABCの問題を解く上で知っておくべきコードを覚えておく必要があるだろう。

 

そこで今まで解いてきた問題、特に典型問題について、ACした解答を、一度ジャンル別に整理してみることにした。主に2に対する打ち手になるだろう。今後「あ、この問題以前やったことある!」という気持ちになったら、ここを参照してどういう風に実装していたかを思い出すことにする。ていうか、コピペするかな・・・。もちろん、何も見ずにコードをかければそれに越したことはないのだけれど、別段仕事で使っているわけでもないC++14を身体に覚えさせるには、やはりまだ時間が必要そうだ。

 

典型問題であるかどうかは割と主観で決めた。ジャンルについては蟻本の目次(主に初級編)に従ってみた。

 

(以下、過去のABCの解答あり。まだ解答していない、かつこれから解答する予定のある人は注意。)

 

↓↓

 


全探索

状態が2値ならビット演算子で全探索可能。
https://atcoder.jp/contests/abc128/submissions/10046498
(↑やや怪しいコード)

幅優先探索
https://atcoder.jp/contests/abc151/submissions/9969553

深さ優先探索
→未経験


貪欲法

https://atcoder.jp/contests/abc148/submissions/9072563

区間スケジューリング
https://atcoder.jp/contests/keyence2020/submissions/9585664
https://atcoder.jp/contests/abc131/submissions/9263145

 

動的計画法

解いた覚えはあるけどどれだったか忘れたため不記載

 

データ構造

優先度付きキュー
https://atcoder.jp/contests/abc141/submissions/9166698

 

グラフ

未経験

 

数学

素数
https://atcoder.jp/contests/abc142/submissions/9188911
最小公倍数
https://atcoder.jp/contests/abc070/tasks/abc070_c


2分探索

https://atcoder.jp/contests/abc146/submissions/8627947
(↑やや怪しいコード)



しゃくとり法

https://atcoder.jp/contests/abc143/submissions/11477394

※2分探索で解く方法もあり、こちらの方が重要。

 https://atcoder.jp/contests/abc143/submissions/8034764

 

2019年1月2月の振り返り

月次報告みたいな何か。

何をやったか

  • 転職活動を行い2社から内定を得た
  • エリック・エヴァンスのドメイン駆動設計を読み、セミナーに参加した
  • How Google Worksの英語版を購入し、読み進めている
  • TOEIC受験を申し込んだ
  • スタディサプリEnglishによる英語の学習を継続した
  • Python3でWebスクレイピングの練習を行った

量的には以下のグラフの通りとなる。 

f:id:ShandyGaffLover:20190306180636j:plain

2019年1月2月の学習時間

 

1か月の合計学習時間は1月が38時間11分、2月が46時間6分だった。すごいね。

 

成長ポイント

  • 転職活動における連日の面接を通じて、2社から内定を得ることができた。基本給が少しだけ上がった。
  •  英語のドキュメントを読む上での精神的な抵抗が下がった。

    Automate the Boring Stuff with Python を参照しながらBeautifulSoupで簡単なWebスクレイピングを行うくらいには。

 

課題

  • ドメイン駆動設計については今の時点で何らかのアウトプットが欲しい
  •  英語のドキュメントを読む速度が圧倒的に足りない

 来月について

 

 

 

【書評】アジャイルサムライ――達人開発者への道

よく耳にするアジャイルな開発とは何か、というのを理解したかったので、アジャイルサムライを読んだ。

shop.ohmsha.co.jp

どんな本か

アジャイルな(agile)開発とは、直訳すると「敏捷な」「すばしっこい」「活発な」開発であり、特にソフトウェア開発の文脈では迅速かつ適応的にソフトウェア開発を行う軽量な開発手法群の総称である。

いくつかのよく知られた実践方法が人口に膾炙しがちだが、その本質は以下のアジャイルマニフェストにある。
アジャイルソフトウェア開発宣言
アジャイル宣言の背後にある原則

本書は、上記アジャイルマニフェストに則ったアジャイルな開発がどういう問題意識のもとに生じたのかや、アジャイルな開発の全体像及びプラクティスについて、ざっくり語ったものである。文体が非常にフランクでとっつきやすく、アジャイルな開発の入門書として読みやすい。

学んだこと

  • アジャイルな開発では動くソフトウェアこそが進捗の最も重要な尺度である、と考える。
  • 開発はイテレーティブに進む。各イテレーションで分析、設計、実装、テストが密に連携する。
  • アジャイルな開発には「顧客」が存在し、あらゆる要求の真実の源、優先順位づけ、何を作らないかを決める存在となる。そして顧客を直に巻き込めば巻き込むほど、プロダクトは良くなっていく。
  • チームで成果責任を果たす。役割分担をきっちり区別しない。
  • QCDを固定し、スコープを変動させる。プロジェクトの進捗に合わせ何を作らないかを決めていく必要がある。
  • 決して簡単ではない。万人がこのような働き方を好むわけではない。

感想

アジャイルな開発を実践するにあたって近年ではDon't "Do" Agile. Be Agile.というフレーズがよく聞かれる。

www.slideshare.net

アジャイルな」という言葉の広まりとともに、エクストリームプログラミングの手法も周知されていった。しかし重要なのは背景となる原理原則あるいは思いである。結局のところプロジェクトは常に生ものであり、ひとつとして同じプロジェクトがない以上、自分で考える必要があるだろう。もちろん、知識として数ある手法を覚えておくことは必要だ。

以下、完全に余談だが、この本の最初のページには以下のようなことが書かれている。

君がこの本を手に取ったことに祝福を。おめでとう。というのも、君にはすごく大事な2つのことが備わってるってことだからだ。

  1. 君は学ぶことが心から好きだ。
  2. 君はソフトウェアのことを大切に思っている。

このどちちらもが大切なんだ。君が学びたいという気持ちを抱かなければ、私との旅がこうして幕を開けようとすることもなかった。君がソフトウェアのことなんて気にしない人物だったら、私たちの世界は今よりも暮らしづらいものになっていただろう。

この本を購入した当時の自分は孤独だったが、この言葉には勇気をもらうことができてよかったと思う。

【書評】テスト駆動開発

よく耳にするTDD:テスト駆動開発とは何か、というのを理解したかったので、テスト駆動開発を読んだ。

www.ohmsha.co.jp

どんな本か

その名の通り、テスト駆動開発の実践の様子をコードと文章で説明したもの。
テスト駆動開発とは「動作するきれいなコード」をゴールとし、その過程で生じる開発者の不安を解消するための開発手法である。具体的には以下の3つを繰り返す。

  1. 失敗するテストコードを書く
  2. プロダクトコードを書き、テストを成功させる
  3. 設計判断を行う*1

学んだこと

つまるところ、よりよいコードと設計を生み出すための試行錯誤のプラクティスである。

感想

ポイントは2つあると思っていて、1つはプロダクトコードよりも先にテストコードを書くこと。これから作ろうとしているプロダクトコードがすでにあるという気持ちでテストコードを書くということ。

もうひとつは設計判断より先にテストコードを書くこと。139ページの言葉を借りると、

テストとコードの間の重複除去が、設計を駆動する

となる。

すなわち、テスト駆動開発設計ありきではないのだ。したがって古典的なウォーターフォール開発のように、詳細設計書ありきでコードを書く開発現場では適用できないのは残念であった(仕事で生かせないため)。

そもそもテスト駆動開発においては、ウォーターフォールにおける詳細設計と製造を分割しない。それらはテストコードによって駆動され、互いにフィードバックをかけながら洗練されていくものである。

そしてその哲学は非常に納得感がある。

*1:本文中では「リファクタリング」と呼ばれている。しかしメソッドの外部構造も変更しうるので、リファクタリングってあまり適切な呼び方ではないと思っている

2018年12月の振り返り

月次報告みたいな何か。

何をやったか

  • スタディプラスで学習記録をつけ始めた
  • 技術書を2冊読んだ
  • アルゴリズムパズルの解答を継続した
  • CodilityのLessonsの解答を行った
  • スタディサプリEnglishによる英語の学習を継続した
  • はてなブログとQiitaのアカウントを新設した
  • Herokuに自作アプリを上げた

 

量的には以下のグラフの通りとなる。 

f:id:ShandyGaffLover:20190104144218p:plain

2018年12月の学習記録

 

1か月の合計学習時間は65時間35分だった。すごいね。

 

成長ポイント

アルゴリズムの教養がない自分の弱みを認識し、具体的に対策案を講じ実践したこと。

このあたりは確かに課題発見・解決力が強い...。

 

shandygafflover.hatenablog.com

 

一番継続しやすそうな本で21時間18分学習した。その結果

  • 最低限知っておくべきアルゴリズムの知識がついた
  • 問題を何度も解くことで実践的な分析ができるようになった
  • CodilityのRespectableの難易度の問題を自力で2問解けた

特に3つ目は大きい。

 

上記が一番のメインなのだけど、ほかにも

  • 単純に勉強量が増加した
  • 週15時間のペースをつかんだ
  • 英語の勉強を週2時間継続している

とか。

 

課題

読んだ技術書に対し「何を学んだか」のアウトプットが弱いと思う。

アクセス解析を見る限り、特に誰が読んでいるというわけでもないブログなので、今後は「他人が読んで理解できるか」よりも「自分が何を学んだか」がわかるように書くようにしよう。

 

 来月について

  • 週2時間の英語の学習を継続しよう
  • アルゴリズムの学習を継続しよう
  • (ペースをつかんだので)スタディプラスのTwitter連携を停止する
  • 読んだ技術書に対し「何を学んだか」がわかるような書評を書こう

 

あとはこれを12か月続けてみよう。

 

 

 

【書評】Head Firstネットワーク――頭とからだで覚えるネットワークの基本

私事で恐縮なのだが、このたび情報処理技術者試験の高度区分であるネットワークスペシャリスト試験に合格した。

 

というわけで、自分がネットワークの勉強をしたときに読んだ本を紹介する*1

www.oreilly.co.jp

 

<どんな本か>

数あるO'ReillyのHead Firstシリーズのひとつである。同シリーズはいずれも独特で特徴的な記法により読者の学習を促進する試みがなされており、ビジュアル重視で、文体はくだけており、考えを深めながら学べるようになっている。したがって何かを「学ぶ」人には格好の教材だ(本稿の趣旨とは若干ずれるが、なかでも私は O'Reilly Japan - Head Firstオブジェクト指向分析設計が好きだ)。

 

本書のテーマは「ネットワーク」である。ネットワークとひとことで言っても、物理層からアプリケーション層まで扱う範囲は極めて広大だ。本書では例えば以下のような基本事項の理解に主眼を置いている。

 

 随所に簡単なエクササイズもあるので、理解を深めながら読み進めることができる。まさに学習教材としてはうってつけであろう。ただし、既にネットワークに関する知識の深い人が読んでも得るもの少ないと思われる。あくまでもネットワークに関する基礎知識を楽しく学習できるものだ。そういう意味でネットワークの学習の初めの一歩としては大変おすすめできる

 

<感想>

自分のバックグラウンドはアプリ開発メインなので、これまでネットワークについてはかなり朧気な理解のまま業務を行っていた。しかしこの本を読んでネットワークについて一定の理解を得ることができたので良かったと思う。ただ正直なことを言うと、前半の物理層の話はあんまり興味を持てなかった。

 

ネットワークに関する技術は現代のインターネットにおいて重要で不可欠なものとなっているし、ネットワークを利用しない場面はほとんどない。しかしその仕組みをきちんと理解する難易度はとても高い(そもそも範囲が広大すぎるし、ひとつひとつも結構難しい)。また日頃の業務においてpingコマンドを利用したりはするけれど、背後の原理やメカニズムについて理解はあやふやなままだったりもした。そんな中本書でネットワークの学習の敷居が下がったのはうれしかった。

 

<こんな人におすすめ!>

  • ネットワークを「なんとなく」理解した状態で仕事をしているエンジニア
  • 過去にネットワークを勉強しようとしたけど難しすぎて挫折した人
  • まだ技術にそこまで精通していない社内SEやインフラ担当者 

 

<逆にこんな人にはおすすめできない>

  • ネットワークの特定の領域に関する深い知識を求めている専門家

  • リファレンスを探しているプロフェッショナル

 

*1:ちなみにもしネットワークスペシャリスト試験の合格を目指す場合は、過去問を3年分3周解答することをおすすめする。ここで紹介する本はあくまでもネットワークに関する「理解」を促すものであり、情報処理技術者試験のような「過去問からの流用が多い問題」の攻略はまた別に必要だ。

【書評】アルゴリズムパズル ――プログラマのための数学パズル入門

アルゴリズムについて勉強する必要が私情により出てきたので、以下の本を買って取り組んでみた。

www.oreilly.co.jp

<どんな本か>

アルゴリズム的なパズルを集めた本。アルゴリズム的なパズルとは、問題を解くためのはっきり定義した手順を扱うパズルのこと。例えば エイト・クイーンハノイの塔狼とヤギとキャベツなどだ。

 

またこの本は副題にもあるように、プログラマ向けである。その理由は、コーディングにおいて適切なアルゴリズムを選択し実装することが、ロジックの簡潔さやパフォーマンスに影響するためである。

 

具体的な例を知りたい方はCodilityのLessonsなどがわかりやすいだろう。

app.codility.com

 

実際、IT企業の採用試験として問われることも多いようだ。

www.iandprogram.net

 

書籍の最初にはチュートリアルとして知っておくべきアルゴリズムの解説がある。バックトラックや縮小統治法、分割統治法、動的計画法といった基本的なアルゴリズムを学ぶことが可能だ。

 

本編のパズルは合計150問収録されている。難易度は初級、中級、上級の3段階。いずれも歯応えがある。 

 

<感想>

ひとつひとつのパズルに歯ごたえがあり、とても勉強に...というか頭の体操になった。普段アルゴリズムを意識してコーディングする機会が全くないため、チュートリアルで紹介されるアルゴリズムも勉強になった。

 

ただ解説は良くも悪くも必要最小限にとどまっている印象が強かった。ものによっては「え、ほんとにそれで証明できるの?」というポイントもあった(例えば52. 三角形の数え上げ)。

 

<こんな人におすすめ!>

・パズルが好きな人

アルゴリズムを楽しく学びたい人

・日常的にコーディングを行う人

 

<逆にこんな人にはおすすめできない> 

・パズルがニガテな人や、休みの日にわざわざ頭を使うことに疲労を感じる人

・生活の中でコンピュータに触れる機会がない人

・より本格的な数学書アルゴリズムの厳密な証明を求めている人