$A _ {i-1} \gt A _ {i} \lt A _ {i+1}$ のように，谷になっているものに注目した．すると，問題は「谷となっているところのうち，一番低いところ $b$ と，左右の崖のうち低い方 $l$ の間の区間 $b \leq s \lt l$ が，一番重なっているところはどこか」という風に言い換えることができる．

...しかし区間の重なりと捉えたところで計算量が落ちるわけではないのでよく分からない...

解説を読んで

状態ごとに捉えてみる．具体的には，「注目している陸地が一つ沈んだ時に島の数はどうなるか？」について注目する．すると，注目している陸地の左右に注目するだけで変化を捉えることができる．考えていることは近いが，自分は谷に注目していたので処理が煩雑になっていた...

JOI 2018/2019 予選問題４解説

そこで，陸地をsortして順番に海面を上げていき，陸地の数の増加を数えれば良い．計算量はsortがボトルネックとなり $Nlog(N)$

Submission #4936590 - JOI2018/2019 予選ページ

自分の詰まったところ

陸地が同じ高さで連続している時に，余分に引き算をしていたので，入力を読み込む時に連続しているものは弾くことが必要．
全ての陸地が0の時にバグが発生すので，陸地の入力の最初と最後に高さ0を入れることで解決．

学んだこと

注目するものを転換するということは大事だと思った．一つのものに注目していて解法が出ない時，その対照的なものに注目すると答えにつながる可能性がある．
状態ごとに捉える（i-1回目からi回目への遷移でどのように答えが変化するか）ことが苦手なので，トレーニングが必要．
重複は入力の時点で弾く．
コーナーケースに対しては，入力の両端に自分で何か加えるとうまくいくことも多い（lower_bound()の時などが思い返される...）

2019-04-11

AtCoder: ABC045-D すぬけ君の塗り絵 (400)

競技プログラミング解法メモ atcoder

すぬけ君の塗り絵

問題はこちら

atcoder.jp

自分が気づいたところ

$H=O(10^{5}), W=O(10^{5})$ なので，全てのマス目を調べていくのは間に合わなさそう．そこで，黒く塗られているマス目だけに注目することにした．

一つの黒いマス目が影響を及ぼすマス目は，周囲の9マスだけである．これを考慮すると， $3\times3$ のマス目の中心になり得るマス目は最大でも $N\times 9$ になるので，間に合いそう．よって， $3\times3$ の中心のマス目として考えられるものに対して周囲の黒いマス目を数え，すでに見たマス目はmap<pair(int, int)>で管理することによってACした．

実行時間1946 ms...

Submission #4911309 - AtCoder Beginner Contest 045

学んだこと

他と違うものに注目する（？）
unordered_mapのキーにpairは入らないけど，mapのキーには入る．（pair内部にhashは用意されていないが，比較関数は定義されているので）

2019-04-10

AtCoder: ABC095-D Static Sushi (500)

競技プログラミング解法メモ dp atcoder

Static Sushi

問題はこちら atcoder.jp

自分が気づいたところ

最大でも反対方向に向きを変える動きは一回だけなので，反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた．

これだと，計算量は反転する場所が $O(N)$ ，反転後の最大値探索が累積和を使うと $O(N)$ で $O(N^{2})$ になるので，部分点はもらえる．

Submission #4898403 - AtCoder Beginner Contest 095

しかし，ここから計算量をどうやって落とすのかが理解できなかった．

解説を読んで

「最大値を保持」しておけば良い．ということがわからなかったので，以下のブログを参考にした．

http://blog.livedoor.jp/misteer/archives/9017497.htmlblog.livedoor.jp

最大値をdpの値として持っておいて，逐次更新していく．

自分の詰まったところ

取得カロリーの累積和を事前に計算しておき，dpの更新時に距離分の消費カロリーを引く．自分は逐次差分 $x(i+1) - x(i)$ を追加していく方法だったが，これだと例えば一個飛ばして更新が発生した時に正しく消費カロリーが計算されない．

Submission #4900921 - AtCoder Beginner Contest 095

学んだこと

最大値dpという考え方．「iまでの最大値」という値の持ち方をすることで計算量が下がる時がある．
往復可能なものについては，折り返しが何回起きうるかを考えてみる（だいたい1回で十分な時が多い）．

2019-03-25

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プログラマのためのアルゴリズムとデータ構造

作者:近藤嘉雪
発売日: 2011/01/26
メディア: 単行本

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

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

作者:石田保輝,宮崎修一
発売日: 2017/06/06
メディア: 単行本（ソフトカバー）

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

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

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

茶→緑の精進

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

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

C++の基礎固め：こちらを参考にしました． kyoupro_on_cpp.md · GitHub
蟻本：自分には難しいと感じたので，初級編を何回も読み直しました．
問題を解く：AtCoder 版！蟻本 (初級編) - Qiita
上記が終わったら https://kenkoooo.com/atcoder/ などを使って300点問題埋め．

ここまででだいたい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

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

bit全探索
累積和
ダイクストラ
ワーシャルフロイド
UnionFind
二分探索
深さ優先探索，幅優先探索
ユークリッドの互除法
素因数分解，素数列挙
（DPは勉強していますが一向に解けません）

大事なこと

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

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

復習大事

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

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

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

焦らない

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

Twitter

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

2019-03-17

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

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

アクセス修飾子
コンストラクタ
- 引数が1つの場合
- 移譲コンストラクタ
ヘッダとソースを分離する

アクセス修飾子

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

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++入門編 (明解シリーズ)

作者: 柴田望洋
出版社/メーカー: SBクリエイティブ
発売日: 2017/12/16
メディア: 単行本
この商品を含むブログを見る

2019-02-20

競技プログラミングに便利な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環境を作っちゃってください！