# AtCoder 練習帳２： 2019年10月～

ひとつまえは、[AtCoder 練習帳１](atcoder_drills)

## 2019-11-19
### ABC145E - All-you-can-eat
Difficulty = 1474, コンテスト中に、わりと惜しいところまでいったような気がして悔しかったやつ。t-1 秒以内に食べきる範囲で、n-1 個で dp して、最後に１個追加すればいいというところまでは着想して、ギリギリ動かしたところで時間切れ。[3WA だった](https://atcoder.jp/contests/abc145/submissions/8486286)。

時間でソートしたつもりが、おいしさでソートしてしまっていた以外にも、
いろいろ問題があって、コンテスト後に書き直そうとしても、なんかよくわかんなかった。

さっき、[Sen さんのブログ](https://sen-comp.hatenablog.com/entry/2019/11/17/003150)
を参考にしつつ書いたものがこれ： [8526021](https://atcoder.jp/contests/abc145/submissions/8526021)

時間でソートし、t-1 秒以内で食べられる最大満足度を dp するんだけど、
最後の一個は（dpの時間制約外で）食べ始めたら満足度がいくらになるのかを常に更新していく。
私のコードで、内側ループを昇順にすると、dp の埒外で食べたやつをもう一度カウントしてしまうので、降順に変えた。もしくは、[Sen さんのコード](https://atcoder.jp/contests/abc145/submissions/8491799) のように、dp の更新が過去向きに（時刻が j - A になってる）なるようにする必要がある。

なるほど。

## 2019-11-13
### ARC081D - Coloring Dominoes
Difficulty = 1158. SAPIX さんすう的： [8419445](https://atcoder.jp/contests/arc081/submissions/8419445)

### ARC006B - あみだくじ
あみだくじは互換の積って感じか： 
[8420238](https://atcoder.jp/contests/arc006/submissions/8420238)

## 2019-11-07
### ABC007C - 幅優先探索
蟻本を前から読み始めて、BFS はあんまり書いたことないんだよなぁ（DFSは、ごく自然に書けるんだけどなぁ）とおもって、これを：
[8323218](https://atcoder.jp/contests/abc007/submissions/8323218)

基本形になれなきゃと、蟻本みながら書いてみた。
９月にもこの問題はやっていて、その時の[提出 7434888](https://atcoder.jp/contests/abc007/submissions/7434888) と、今回のは、
あたりまえだけど、ほぼ同じ。今回のの方が、０オリジン処理を最初にやったので、後半がシンプルになってるかな、程度。

もう覚えたかな。（今日は、９月にどんなの書いたか記憶にも残ってなかった）

### ABC136C - Build Stairs
C うめていこうとおもって。とくにいうことなし：
[8325321](https://atcoder.jp/contests/abc136/submissions/8325321)

## 2019-11-03

### ABC036C - 座圧
推定 Difficulty 1112 だけど…、普通に書くだけだったような気が：
[8264516](https://atcoder.jp/contests/abc036/submissions/8264516)

### ARC011B - ルイス・キャロルの記憶術
推定 Difficulty 1334 …んなわけない気がする。Experimental だからか：
[8264997](https://atcoder.jp/contests/arc011/submissions/8264997)

## 2019-10-27
随分日にちがあいてしまった。

### ABC143D - Triangles
きのう[おさらいした](https://uhideyuki.sakura.ne.jp/studs/index.cgi/ja/Snippets#p3)、BisectRight 
をつかった。Left かしら、Right かなとか、検索範囲をどうすんのとか、すこし手元でどたばたしたけど、提出自体はいっぱつ
AC で。

## 2019-10-10
### CADDi 2018 D - Harlequin
DP ... では無理だよなぁ、どうするんだろう？？ くらいで解説を読んでしまって反省。
小さなケースで実際に紙と鉛筆でためす、または、小さいケースを解くDPで様子をみてみるなどしろと。

…はい。あとで解く。

## 2019-10-09
### ABC096D - Five, Five Everywhere
はじめ、試しに、単に素数を前から N 個だしてみて WA（そりゃそうだ）。
つぎに、条件にあうものだけ前から順に追加していく方法をためしてみたが、
解説にあるように N=9 までしか求められなかった。

解説をみて、納得。なるほど。5で割って1あまるものばかり5個の和は、5で割り切れる：
[7914215](https://atcoder.jp/contests/abc096/submissions/7914215)

## 2019-10-07
### Educational DP Contest K - Stones [メモ化再帰]
DP？…メモ化再帰か、ということで、比較的あっさり書けた：
[7897867](https://atcoder.jp/contests/dp/submissions/7897867)

### Educational DP Contest L - Dequeue 
これも、メモ化再帰のような、DP のような。
あまり頭の中で区別がなくなってきた…。
DP の状態表現を先に考えて、ループで更新するか、それが無理ならメモ化再帰にするかを後で考える感じかもしれない：
[7898319](https://atcoder.jp/contests/dp/submissions/7898319)

ちなみに、メモ化の際に、計算がまだなことを表す０と、たまたま値が０になるのを区別していないけど、わざとです（無駄な計算をする可能性があるけど、手抜き分はペイするとおもった）。

## 2019-10-05
### AGC018A - Getting Difference, Difficulty = 428
検索で殴るのでなく、数の性質を使うタイプ。\(k\) が \(A_i\) の最大個約数の倍数で、かつ、\(A_i\) の最大値以下であれば可能：
[7856693](https://atcoder.jp/contests/agc018/submissions/7856693)

## 2019-10-04
### AGC023A - Zero-Sum Ranges [数列], Difficulty = 775
部分数列の和がゼロになるケースを数え上げろというもの。
累積和ではTLEだろうなぁと思って、TLE。累積和の同じ値が出現する個数を数えればいいと気づいたのだけど、Dictionary を使って個数を数えようとして、今度はRE。
解説をみて、なるほどと思ったという。我ながら、ニブいなぁ。

累積和の配列をソートすれば、同じ値は固まるのでそれを数えればよかった：
[7845589](https://atcoder.jp/contests/agc023/submissions/7845589)

### AGC028A - Two Abbreviations, Difficulty = 285
一応自力で通したが…。
どの範囲で知らべるのがいいのかわからず、lcｍ から N*M の範囲を調べることにした。
最初それではTLE（その前に、おそらく int あふれでエラー）、次に二分探索するようにして AC になったが、ほんとは lcm だけチェックすればよかった：
[7846332](https://atcoder.jp/contests/agc028/submissions/7846332)

## 2019-10-01
### AGC031A - Colorful Subsequence
簡単だった（difficulty 254 らしいし）。９分：
[7804248](https://atcoder.jp/contests/agc031/submissions/7804248)

### AGC030A - Poisonous Cookies
これも書くだけ (difficulty 1), 5 分：
[7804331](https://atcoder.jp/contests/agc030/submissions/7804331)

### AGC033B - LRUD Game
Difficulty 1323. 高橋君が右/上 を目指すシナリオと、左／下を目指すシナリオの２通りをシミュレートして、
いずれかで盤からはみ出たら NO って感じで。すんなり通った：
[7804539](https://atcoder.jp/contests/agc033/submissions/7804539)