# 2019 年 5 月
## 2019-05-18
すこしずつ、すこしずつ。むきにならない、がんばりすぎないのが大事、なはず。

### Wiz Study

$<verb>{prj/dungeon} に、マップを表すテキストと、その変換スクリプトを書いていく。
maptxt-b1f.txt を書いてくなかで、フォーマットの大枠はきまり。

スクリプトは、まず、読み込むところまで。気が向いてからつづきを。

### AtCoder 過去問

今日も、まず、安全のために 1AC してから、なんか手ごわそうなのに取り組むことにしよう。

というわけで、abc105a ac, つぎに recommended の abc099c をやってみたが、sample3 があわない。
そうか。1, 6, ..., 6^6, 9, ..., 9^5 をソートして、でかい金額から引いていけばいいかと思ったが、それほど単純ではなかった。

探索が必要なのだが、\(6^p\) で引き出す金額をきめると残りが決まるので \(O(N)\) ということのよう。あしたにでもやるか。
→ [書いた](https://atcoder.jp/contests/abc099/submissions/5437907)

そうか、O(N) かというので素直に書いたらこうなったんだけど、もっと簡潔にかけるべきという気もする。


## 2019-05-15

素振りばっかりじゃ飽きそうなので、ABC 出てみようかなぁ。
水色くらいまでは ABC でいけるらしいというのと、１０回くらいしないとレートはでないとかいうので、あんまり後回しにしすぎない方が良い気がした。

んでも、まだ、あまり過去問やっていないので、基本的な知識が抜けてそう。

### 水色くらいまでに必要そうなもの

以下は水色になるまでに必要になるそう。まだ、いくつかしか確認していない。

- 幅優先探索
- 深さ優先探索
- GCD
- GLM
- 一次元累積和
- 加減乗算の剰余
- ダイクストラ法による採点経路
- Union Find
- 簡単な DP
- エラトステネスの篩
- メモ化再帰 / DFS
- 二分探索
- BFS
- 重み付き Union Find

### 水色なってからで良さそうなもの

もうちょっと後からでもよさそうなの

- ワーシャルフロイド法（任意の二点間の最短経路）
- ベルマンフォード法（負の経路の検出）
- 除算の剰余（M = \(10^9 + 7\) の場合）
- しゃくとり法
- 二次元累積和
- 最小全域木（クラスカル法　または　プリム法）
- 二部マッチング
- 最大フロー、最小カット
- トポロジカルソート

いままでの過去問ででくわしたものもあるな。このリストに対する星取り表（？）を書いていくのもいいかも。

今週末は、まだ無理そうなので、それまでに最初のリストはさらっておくかな。

## 2019-05-08

Markdown Preview Plus を久々につかったら文字化け。ん？と思ってしらべると、Chrome で文字コードを変えるメニューがなくなっていて、
[拡張機能に](https://chrome.google.com/webstore/detail/set-character-encoding/bpojelgakakmcfmjfilgdlmhefphglae/related?utm_source=chrome-app-launcher-info-dialog) なってたのでいれた。