ひらめの日常

日常のメモをつらつらと

AtCoderで水色になるまでやったこと

競技プログラミング atcoder

2019/12/23追記: ※このブログはABCがABCDの4問だった頃の記事になりますので，現在では当てはまらないことも多いですがご承知ください．

2019/03/24のABC122で水色になりました．

自分が割と苦労して水色になったのと，同じようなブログがかなり参考になったので自分も書いてみようと思い，残しておきます ．

f:id:thescript1210:20190325162007p:plain
レート遷移図

競プロ始めた時の自分

  • 工学部のB3（情報系とは明言できない学科）
  • Java/KotlinでAndroidアプリ開発を一年間やっていた．
  • Pythonあたりも機械学習周りで使っていた．
  • C言語系の知識はほぼなし．
  • 数学はとっても苦手．

基礎固め，灰→茶

ここはAtCoder解くだけならいらないかも知れません

Javaで競技プログラミングをやろうと思っていたので，AtCoderに参加すると同時にJavaでアルゴリズムとデータ構造的な初歩的な内容を勉強しました．

定本Javaプログラマのためのアルゴリズムとデータ構造

定本Javaプログラマのためのアルゴリズムとデータ構造

それと同時に自分は図で何が起こっているのかを理解するタイプだったので，アルゴリズム図鑑を買って各種アルゴリズムがどのように動くのかイメージを理解しました．（すごくわかりやすい本です）

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

ここまでで以下のことを身につけました．しかし具体的に使えるかというとそうではありませんでした．

  • 計算量の概念
  • 各種ソートアルゴリズムとその計算量
  • スタック・キュー・ハッシュ・ヒープなどのデータ構造
  • 二分木の概念
  • 二分探索の概念
  • 深さ優先・幅優先・ダイクストラ法のイメージ

コンテストに参加するにあたって，入出力についてもちょっと勉強しました．

茶→緑の精進

最初は緑下位パフォが出たものの，回数を重ねるにつれてパフォが茶色になっていました．200点問題までは解けるのですが，300点の壁が非常に高かったです．

そこで本格的にアルゴリズムの勉強と，AtCoderの問題を解くことを始めました．具体的には以下のことを並行して行いました．

ここまででだいたい300点問題を30分ほどで解けるようになり，緑パフォが安定してきました．

一つ大きな疑問として，なぜC++に変えようと思ったのか？ということがありますが，これは完全に自分の気持ちです．

  • C言語系を勉強したかった．
  • アルゴリズムの教材にC++で書かれていたものが多かった．（別言語に変換するところで時間を取られるのは本質的ではないので，より多くの人間が使っているものを使うのがいいと考えました）
  • 実行速度が速い．（...正直水色までだったら大して問題にはなりません．）

緑→水の精進

ここでは300問題を早く解く + 失敗をなくす + たまに400点問題を解く．あたりが必要になってくるかと思います．

  • 400点問題埋めを始める．
  • ABCのセットのバチャを AtCoder Virtual Contest で立てて，きちんと緊張感持ってやる．
  • 苦手分野を集中的にやる．（自分はグラフ問題とか二分探索とかやってました．）

あとは本質的ではありませんが，早解きのためのtipsをためていきました． hiramekun.hatenablog.com

問題量をこなすと引き出しが増える + その引き出しを開くのが早くなるので，300点問題なら15分前後で解けるようになり，水色パフォが増えてきます．

水色になった時にはこれくらいの問題を解いていました

f:id:thescript1210:20190325173726p:plain
AtCoder Scores

ここまでで最終的にできるようになったことはだいたい以下のようなものです．

大事なこと

自分は何ができないのかを把握する

使っているアルゴリズム自体がわからないのか，それとも問題の解法自体が思いつかないのかによって違ってくると自分は思います． 前半がわからないなら蟻本やQiitaの記事で身につける．後半がわからないなら，ひたすら問題を解き，解説などもみて発想の過程を訓練するという感じでした．

復習大事

まず解説放送は聞いたほうがいいと思います．日本トップレベルの競プロerがどのような思考過程を経て解答にたどり着いているのかを，なんと無料で聞けるのですから聞かない手はありません．

そして，自力で解けるようになるまで間違えた問題は解き直しました．これは，一回解説放送などで聞いたはずの，自分より強い人たちの思考方法を追うことができます．AtCoder Scores などを使って解けなかったの問題はお気に入り登録して解き直します．

ここはかなり大事だと思っていて，問題からアルゴリズムへの帰着に対する良い練習になりました．

焦らない

周りの人がすごいペースで問題解いていたりすぐに色が変わったりすると焦ります（自分が周りと比べて成長が遅かったので）．自分のペースで，何より自分に合ったやり方で続けることが大事だと思います．

Twitter

同じくらいのレートの人や，自分より上のレートの人が，どのような精進をしているのか・何を考えているのかを知れて良いです．頑張っている人たちの様子が見れるので良い刺激とプレッシャーにもなります．

C++のクラス関連で調べたことメモ

競技プログラミング C++

アクセス修飾子

まずは書き方．順番やその個数は任意で，何度現れても良い．

class Hoge {
public:
    int a;
private:
    int b;
public:
    int c;
};

デフォルトのメンバは private として扱われる．

コンストラクタ

コンストラクタは，クラスオブジェクトが生成されるときに呼び出される．（値を返さないので自分の実感としてはコンストラクタというよりイニシャライザの方がしっくりくる．）もし明示的にコンストラクタが定義されていない場合，引数を受け取らないコンストラクタが自動的に定義される．

class Hoge {
private:
    int a;
public:
    Hoge(int x) {
        a = x;
    }
    void fuga() {
        a++;
    }
};

引数が1つの場合

引数が一つのコンストラクタは，変換コンストラクタと呼び，明示的呼び出しと暗黙的呼び出しの二つの呼び出し方がある． つまり，上記の Hogeクラス の場合，以下の二通りの呼び出しが同義になっている．

Hoge h = 10;
Hoge h = Hoge(10);

暗黙的呼び出しを禁止したいときには，explicit とコンストラクタに宣言しておくことで，明示的呼び出しのみが呼び出される．

参考 引数1個のコンストラクタの暗黙呼び出しとexplicit

移譲コンストラクタ

delegating constructors. 例えば，引数ありで生成した時はその引数でメンバを初期化し，引数なしで初期化した時はデフォルト値で初期化したいという時がある．この時は，次のように移譲コンストラクタを書けば良い．

class Hoge {
private:
    int a;
    const int DEFAULT_VALUE = 0;
public:
    Hoge(int x) {
        a = x;
    }
    Hoge: Hoge(DEFAULT_VALUE) {}
    void fuga() {
        a++;
    }
};

参考 移譲コンストラクタ - cpprefjp C++日本語リファレンス

ヘッダとソースを分離する

宣言とその定義を別ファイルに分けて可読性を高めようということ． ヘッダファイルはクラス定義などを書き，ソースファイルにはメンバ関数の定義などを書く．

他のファイルで使用する時は，宣言が書いてあるヘッダファイルをincludeすれば良い．

Hoge.h

class Hoge {
private:
    int a;
    const int DEFAULT_VALUE = 100;
public:
    Hoge(int x);
    Hoge: Hoge(DEFAULT_VALUE);

    void fuga();
};

Hoge.cpp

#include "Hoge.h"

Hoge:: Hoge(int x) {
    a = x;
}
Hoge:: Hoge: Hoge(DEFAULT_VALUE) {}

void fuga() {
    a++;
}

参考

新・明解C++入門編 (明解シリーズ)

新・明解C++入門編 (明解シリーズ)

競技プログラミングに便利なCLionの機能

競技プログラミング tool

はじめに

僕は競技プログラミングやるときのIDEとしてCLionを使っています．周りにCLionを使っている人が多くないので，今回はCLionってこんなに便利だよ！ということを紹介します．

テンプレート機能

VSCodeにも同様の機能があると聞きます．

Settings → Editor → Live Templatesに登録することで，補完が出てくれるようになります．

f:id:thescript1210:20190220081248p:plain
live template

例えば，cmd + j で登録したテンプレート一覧が表示され，union find tree を入力してみます．

他にも，補完時にどの場所にカーソルを入れるかなども指定することができます．

デバッグ

CLionには優秀なデバッグ機能があります．cmd + f8でブレイクポイントを貼り，debugモードで実行すると1ステップごとに処理を追うことができます．この例では配列aが更新されるところにブレイクポイントを貼り（赤丸です），aの中身をみています．

f:id:thescript1210:20190220083836p:plain
debug
．

ステップ実行や，ステップ実行中に関数が呼び出された場合はその関数の中に入る→出るといったこともできます．lldbを使っているので，コンソールからも似たようなことはできます．

ファイル単位での実行

競プロではmain()を一つの問題ごとに用意し，各ファイルを実行して手元でテストケースを試したい時があるかと思います． こんな感じでたくさんのファイルを一つのプロジェクトに入れると，実行ができません．

f:id:thescript1210:20190220084202p:plain
ファイル構造

そんなときに便利なのがこのプラグインです．実行させたいファイル上で右クリック→Add executable for single c/cpp fileを選択することによって，単一ファイルごとにmain()を実行するとができます．（ターミナルからコンパイルして実行しろというのは正論です．） plugins.jetbrains.com

やっていることは，CMakeListsにexecutableとして登録しているだけなので，手動でもできますがだいぶ楽になります．

ファイルのリフォーマット

速さを意識しすぎてコーディングすると，コードが汚くなりがちですよね？？しかしながら，汚いコードは読みにくいのでバグの温床にもなってしまいます．そこで，Reformat Code というコマンドを使いましょう．デフォルトだと cmd+option+Lです．

自分で設定したコーディング規約に基づいてコードをリフォーマットしてくれます．

肝心のコーディング規約をどう設定するかですが，Preferences -> Editor -> Code Styleでインデントの幅からどこで改行するかまで細かく指定することができます．

f:id:thescript1210:20190412004416p:plain
Code Style

最後に

やはり強力な補完や，エラーになりうる箇所を事前に見つけてくれてwarningを出してくれるのはIDEならではの良さがあります．もちろん，他のIDEでもできるでしょうし，他のエディタにはエディタの良さがあると思います．

他にも，debugの時だけフラグを追加して，ローカル環境のみで実行させたい箇所を作るなんてことも可能です． ぜひ自分のお気に入りのCLion環境を作っちゃってください！

京都大学大学院情報学研究科の入試情報まとめ（自分用）

院試

はじめに

この記事は，外部からの院進先として京都大学大学院情報学研究科の「社会情報学専攻」を選択肢に入れている僕が，ネット上の情報を自分用にまとめたものです．（知能情報学専攻についてはごめんなさい...！）

いかんせん情報が少ないので，コメントなどいただけると嬉しいです．

随時更新していきます．

公式

URL

科目内容

  • 情報学基礎は「入門 コンピュータ科学 IT を支える技術と理論の基礎知識」から3問出題．（ただし、第 10 章「コンピュータグラフィックス」は出題範囲から除く。）
  • 専門科目の出題分野は「人工知能、データベース、情報システム、計算機ソフトウェア、情報ネットワーク、データ構造、アルゴリズム、パターン認識、情報教育、ヒューマンインタフェース」
  • 英語は「TOEFL/TOEIC/IELTS」のスコア．

参考URL

体験記

社会情報学専攻が見つからないので，知能情報学専攻の受験対策について．専攻は違うが，進め方とかで参考になる．

入試対策

URL

出題傾向と対応するシラバス

まず，過去問は京大に行ってコピーしなければならない...自分は平成28年度分〜30年度分だけだが、友達に頼んでコピーしてもらった。

自分で5年分の過去問を見て出題されている分野をまとめたのと，出題分野に対応しそうな京大の学部授業urlをまとめる．

院試まとめ - Google スプレッドシート

その他

志望大学院に特化していないけど院試に関連した情報たち

dotfilesの管理方法を変えた話

shell tool

以前の記事でdotfilesの管理方法をまとめるという記事を書いたのですが，これは.vimrcとかのdotfileに対してシンボリックリンクを貼るだけのものでした．

hiramekun.hatenablog.com

今回はこちらのcreastyさんのdotfilesを参考にして，ansibleで構成を管理するように変更しました．

github.com

github.com

ansibleで管理した結果，大きく変わったのは以下の点です．

  • アプリを極力 brew cask でインストールすると自動化できる．
  • brew install も自動化できる．
  • *env（pyenvとか）の設定についても自動化できる．
  • macの設定（キーリピート速度とか）についても自動化できる．

etc...いいことだらけでした．初めはansibleを知らない状態からcreastyさんのコードを読むところから始めたのですが，sh upから続々とアプリやパッケージがインストールされ，環境構築されていく様子はとても楽しいです．

是非みなさんも参考にしてみてはいかがでしょうか！

教育情報学が勉強できそうな大学院を調べてみた（自分用メモ）

院試 教育

こちらの記事は完全に自分用にまとめたものです．
情報学的観点から教育を捉えることがしたいのですが，その教育と情報という軸の中で，どの点から関わっていくのかが悩ましいところです．
入れるかどうかは別として考えて，入るとしたらという観点で書いていきます！ 簡単に，教育と情報工学の2軸で分けると，下の図の様に分けられるのかなと思います． f:id:thescript1210:20180825033215p:plain

① 東京大学大学院学際情報学府 学際情報学専攻 文化・人間情報学コース
東京大学大学院 情報学環・学際情報学府 – 文化・人間情報学コース
Ylab 東京大学 山内研究室がかなりこの分野では有名らしく，教育工学や実証実験に基づく教育効果の測定など興味深い研究がたくさんあります．

② 東北大学大学院教育学研究科 教育情報アセスメントコース
東北大学の教育学部ですが，2018年から再編が行われたみたいであまり情報がありませんでした．前身はこちらの東北大学教育学研究科教育情報デザイン論分野という専攻だったのでこのサイトが役に立つかもしれません．

コース紹介 || 東北大学 大学院教育学研究科 教育学部

③ 京都大学大学院情報学研究科 社会情報学専攻
京都大学大学院情報学研究科 社会情報学専攻
緒方研究室 – 京都大学 学術情報メディアセンターという研究室では，教育情報学という分野を扱っており，ここでは教育について集まったビッグデータの解析基盤を研究したり，データ解析そのものを行ったりと，自分の興味分野に一番近い研究をしているイメージがあります．

misc/reference_url.md at master · haya14busa/misc · GitHub
募集要項 http://www.i.kyoto-u.ac.jp/admission/pdf/master-h31-4.pdf

次の計算機科学から三題．人工知能、データベース、情報システム、計算機ソフトウェア、情報ネットワーク、データ構造、アルゴリズム、パターン認識、情報教育、ヒューマンインタフェース

情報学基礎に関する筆記試験は以下に指定した教科書の内容から５問出題する。このうち、３問を解答時に選択して解答すること。 ・入門 コンピュータ科学 IT を支える技術と理論の基礎知識（J. Glenn Brookshear 著、神林靖・長尾高弘 翻訳、KADOKAWA/アスキー・メディアワークス 出版、ISBN-10: 4048869574、ISBN-13: 978-4048869577）※ただし、第 10 章「コンピュータグラフィックス」は出題範囲から除く。

④ 東京大学大学院情報理工系研究科 コンピュータ科学専攻
コンピュータ科学 | 専攻 | 組織 | 東京大学 大学院 情報理工学系研究科
こちらは完全に情報側のアプローチになりそうです．情報学として教育に役立つ様な要素技術を開発するスペシャリストになるイメージですね．

【まとめ】terminalでShift-JISの文字コードを扱う時の便利なコマンド

Linux shell

terminalでshift jis

shift-jisファイルを扱う時、そのまま扱う・文字コードを変更するなどいろんな方法があると思います。 今回はshift-jisで困っている方向けにterminalで便利なコマンドを紹介します。
どのコマンドも、aliasを貼って短くタイピングして呼び出したいですね。

vimでshift jisファイルを開く

-cオプションの引数に与えてあげることで、ファイルを開く時点で文字コードを指定することができます。

vim -c ":e ++enc=shift_jis file_name"

qiita.com

diffを改行コードを無視して表示する

以下のコマンドで改行コードは無視してdiffを表示することができます。shif-jisとutf-8のファイルを比べる時などに便利です。

diff --strip-trailing-cr file_a file_b

qiita.com

ファイルの文字コードを変更する

そもそもファイルの文字コードを変更したい時にはnkfコマンドが便利です。
以下の記事で使い方を説明しています。 hiramekun.hatenablog.com