# atCoder 過去問練習帳

atCoder の過去問を解いていくろぐ。（[atCoder Problems のユーザーページ](https://kenkoooo.com/atcoder/?user=unnohideyuki&kind=user))

わからんまま保留しているもののリスト→ [わからんものリスト](pendingItems)

## 2019-08
### 8/10 ABC137 初参加 → 灰色、パフォーマンス：916
### 8/18,19 ABC138E [LUT を逆むきサーチで]
本番で50分ほどあったのに解けなかったやつ。テーブルを前もってつくることで高速化。アルファベットの個数 << t の長さ << 答えの大きさ　という大小関係をとらえる感覚が鈍かった。そこに気づけば、かなり重い前処理でもAC, のちにしーやん先生にならって逆にみていくのがミソのLUT版を投稿: [7041951](https://atcoder.jp/contests/abc138/submissions/7041951)

### 8/21 ABC054C [DFS]
N小さかったので、すなおにDFSで。next permutation 使えるなとおもったけど、未実施

### 8/21 ABC040D [UnionFind]
サイズを数える機能つき Union Find をその場で実装しちゃえとおもって、ソラで書いて無限にバグった。反省: [705691](https://atcoder.jp/contests/abc040/submissions/7057691)

### 8/21 ABC131E [グラフ]
探索によらない、グラフの性質を考える問題。
スター接続のときが、最も「距離２ペア」の数が多く、そのとき \(\frac{(n-1)(n-2)}{2}\) 個ある、などから考えていく。

解説読むまでわからず、読んで「わかった」つもりでも、実装段階で数回間違った。
要反省： [7059102](https://atcoder.jp/contests/abc131/submissions/7059102)

### 8/22 ABC049D [UnionFind + α]
ABC040D (二個まえにやった) の反省を生かして、手元ライブラリの UnionFind を使う。これは、配列を上手につかって、
連結成分のサイズもとれるやつなので、これ使えばすごくいいではないか、道路で連結だった場合のみ Unite するようにしよう！
と思ってよろこんで書いたやつは [WA](https://atcoder.jp/contests/abc049/submissions/7066417)

解説などをみつつ、あとからちゃんと数えるように作り直して AC になったが、上の版でだめになる反例をまだ思いつけていない。あとで→ [わからんものリスト](pendingItems) へ：
[7066761](https://atcoder.jp/contests/abc049/submissions/7066761)

### 8/23 ABC128C 
解説によるとガロア体上の連立方程式と思えみたいなことが書いてあった気がする。今回は、Nがちっさいので全探索した。
Hacker's delight に population count あったなぁというので、ビット列を使った高速化：[7089408](https://atcoder.jp/contests/abc128/submissions/7089408)

### 8/23 ABC129C
みんな大好きフィボナッチって感じで、書くだけだったけど、「入力例３」がなかったら、バグに気づかずWAしてたかも。
壊れているのを特別に -1 とかで表現するか、実際投稿したやつのように二つの配列に分けるか悩んで後者にしたんだけど、
broken[a] = true に設定するだけじゃなくて、stairs[a] = 0 にしないといけない（んだが、問題になるのは a = 1 のときのみ）
てのにはまった：[7091512](https://atcoder.jp/contests/abc129/submissions/7091512)

### 8/24 AGC019B
自力では解けなかった。解説参照：[7097088](https://atcoder.jp/contests/agc019/submissions/7097088)

### 8/24 ABC067D
着想は自力で正解だったのだけど、牛刀を使おうとして失敗。AtCoder Problems で Moderate (50%) サジェストされるやつなので、二問にいっかいくらいは自力で解きたい。

自力で解けそうだったんだけど、RE に悩まされる。
原因は、Warshall-Floyed のための配列が大きくなりすぎたことのようだった。
（そこにたどり着くまでに３０分ロス）
任意の二点間の距離を求める必要はないので、Warshall-Floyed に頼る必要はなかった。

あとで実装しなおす。→ した： [7102655](https://atcoder.jp/contests/abc067/submissions/7102655)

### 8/24 第１回日本最強プログラマー学生選手権　予選　3回目の参加 → 茶色、パフォーマンス： 927
### 8/27 CODE FESTIVAL 2016 qualC C
わかったと思ってスラスラ書いたつもりが [WA](https://atcoder.jp/contests/code-festival-2016-qualc/submissions/7150641)。
簡単かなってときにも、矛盾するケースをちゃんと書き出すとか、丁寧にやるべきだったかな： 
[7157750](https://atcoder.jp/contests/code-festival-2016-qualc/submissions/7157750)

### 8/27 Code Festival 2016 Grand Final B
わからず、解説みた。中学～高校数学って感じの問題だった。解説に書かれていなくて必要な知識は、以下の２つくらいだったかな： [7160019](https://atcoder.jp/contests/cf16-exhibition-final-open/submissions/7160019)

![三角形の面積とか、内接円の半径とか](cf16b.png)

### 8/27 ABC021B
「AtCoder の問題を問題を分類しました」の 5.5 グラフより。[7160319](https://atcoder.jp/contests/abc021/submissions/7160319)

### 8/27 Nikkei 2019 予選 C
「ゼロサムゲームだ！」って感じでふつうにとけた
[7160711](https://atcoder.jp/contests/nikkei2019-qual/submissions/7160711)

ゼロサムちがう気もする。（ちがう）

### 8/27 AGC033A
最初の着想でそのまま解けた。
[7164832](https://atcoder.jp/contests/agc033/submissions/7164832)

### 8/27 ABC051D
Difficult(20%) だけど解けそう！と思ったもののWA。くっ、やはり。

ワーシャルフロイドの過程で、距離を書き換えるケース（経路圧縮？）でついでに消していけばよかろうと思ったものの、うまくいかなかった。なんでうまくいかないのか、
まだ理解してない → [わからんものリスト](pendingItems) へ。

ひとまず、解説通り、まずは最短経路を求めておいてから、最短経路の一部になっているかどうかを調べる方法を採用： [7165628](https://atcoder.jp/contests/abc051/submissions/7165628)

### 8/27 ABC054D [DP]
Difficult(20%) で推薦されたやつ。わかんなかったので、解説見て「うむむ、なるほど…？」ってなってる。あとで再挑戦。

あとで書こうとしてみたけど、結局わかんなくなって写経。あとでもいっかい考える: 
[7168802](https://atcoder.jp/contests/abc054/submissions/7168802)

つぎの日に、自分で書けるかやってみた。ちょっと間違い。そうか、0個まで買った状態で次に買う商品は0番なので、商品番号はゼロ始まりにしなきゃ。
だった。 [7183167](https://atcoder.jp/contests/abc054/submissions/7183167)

### 8/30 ABC021D [Warshall-Floyd]
まず、Warshall-floyd を使うときの初期化で、自分へもどってくるのをゼロに初期化すべきだったところでバグ。そっちは自分で気づいたんだけど、Inf にあたる数が小さすぎてWAを連発してしまった。これは、初期化にも、最後のMinを求めるときにも使う：
[7208397](https://atcoder.jp/contests/abc012/submissions/7208397)

### 8/30 ABC070D グラフ
おおまかな方針はすぐわかったのだけど、隣接行列でやろうとして失敗。そこから心を入れ替えて一応自力で解けたけど、時間かかりすぎ。
はじめから、この実装にたどりつきたかった：
[7211329](https://atcoder.jp/contests/abc070/submissions/7211329)

### 8/31 AGC032B グラフ
難しかった。補グラフを考えるという発想自体がなかった。けっか、できたプログラムはすごく簡潔：
[7224022](https://atcoder.jp/contests/agc032/submissions/7224022)

### 8/31 EDPCA [DP]
Educational DP Contest A を解いてみた。普通にとけたけど、これは典型的なDPの書き方になってなかったな:
[7233600](https://atcoder.jp/contests/dp/submissions/7233600)

### 8/31 EDPCB [DP]
つづけて二問め。こんどは、典型的な「配るDP」風に書いたつもりだったけど、Inf の大きさが甘くてWA。これ、よくやる。要注意。
あと、dp 配列を n+k で余分にとっておけば、ループ条件緩和できる。どっちでもいいような気もするけど：
[7233978](https://atcoder.jp/contests/dp/submissions/7233978)

### 8/31 EDPCC [DP]
なるほど [7234407](https://atcoder.jp/contests/dp/submissions/7234407)

でも、↓こういうループにした方がよかったかな

$$<pre>{
    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j == k) continue;
                chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
            }
        }
    }
$$}

## 2019-09
### 9/3 soundhound2018_summer_qual_c [さんすう]
かんたん、とかいいつつ、例２に助けられた（うかつ）：
[7318110](https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/7318110)

### 9/3 ABC139E [グラフ]
本番では、ひとつだけTLEのまま一時間くらい溶かしてしまったやつ。
グラフの最長経路の長さを求める問題に帰着させる。
あと、循環の検出。なかなか、ちゃんと書けなかった。
[7318341](https://atcoder.jp/contests/abc139/submissions/7318341)

### 9/3 ARC073B [累積和、全探索]
あまり考えずに解説みてしまった。ナップサックだからといって DP ではない。
条件を用いれば全探索可能になる。高速化のために累積和。
そういえば、いちど、w の int あふれで WA だした。きをつけよう：
[7322752](https://atcoder.jp/contests/arc073/submissions/7322752)

### 9/3 ABC135D - Digits Parade [DP]
なるほど、DP って強力なんですね。解説みて、上の桁（左端）からやってくのかというのが意外だったけど、なるほどきれいだ。
[7339526](https://atcoder.jp/contests/abc135/submissions/7339526)


### 9/4 ARC059B
寝る前になんかやるかとおもて、Easy でレコメンドされたやつ。Easy ってのがヒントになっちゃったかもしれん。
[7342360](https://atcoder.jp/contests/arc059/submissions/7342360)

### 9/5 ABC019D - 高橋くんと木の直径 [グラフ]
限られた質問回数で木の直径（二点間の距離の最大値）を求める： 
[7345767](https://atcoder.jp/contests/abc019/submissions/7345767)

### 9/8 ABC140D - Face Produces Unhappiness
N や K の大きさから、探索めいたことをやっていてはダメだなぁとは思いつつ、ちゃんと腰をすえて考えられなかった。
（つぎのEを考えてみたり、Fを考えてみたりと注意を分散させてしまった）
[7420982](https://atcoder.jp/contests/abc140/submissions/7420982)

### 9/8 CODEFESTIVAL 2017 qual A C - Palindromic Matrix
Difficulty 983, Solve Provability 51% でレコメンドされたやつ。普通にとけた。
[7424622](https://atcoder.jp/contests/code-festival-2017-quala/submissions/7424622)

### 9/9  ABC112C - Pyramid
Difficulty = 1104, Solve Probability = 44% でレコメンドされたもの。
解けそうな気がしたし、解きたかったのだけど WA がひとつ取れなくて。
座標 (Cx, Cy) の候補の数が１万程度なので、全探索すればいいというのは気づいたんだけど、h が ０ になるケースの扱いを、あんまり考えずに書き始めたのがよくなかった。

解説をみて書き直したものは、だいぶすっきりしている。

[提出一覧](https://atcoder.jp/contests/abc112/submissions?f.Task=abc112_c&f.Language=&f.Status=&f.User=unnohideyuki)

### 9/9 ABC109D - Make Them Even [グリッド]
Difficulty 1083。回数に制限ないので、すべてのコインを (1, 1) に集めてやればいいじゃんと思いやってみたけど、TLE の嵐。（ついでにWAもなんかでてるけど…）

グリッドをジグザグに一筆書きして一本の帯にしてしまうのは、典型的なのかも。
[7434100](https://atcoder.jp/contests/abc109/submissions/7434100)

### 9/9 ABC007C - 幅優先探索 [BFS]
実は、はじめて幅優先探索のプログラムを書いた。Queue<T> も初めてつかった。
[7434888](https://atcoder.jp/contests/abc007/submissions/7434888)

### 9/9 ABC045D - すぬけ君の塗り絵 [数え上げの高速化] 
解説にあるような方針には自力でたどり着いていたのに、TLE 回避できずにいたもの。
他のひとのACを参考に高速化した。

必要だったのは、ans[n] をあとから数えるんじゃなくて、インクリメンタルに更新していくこと。さらに、C# の場合は、10^5 オーダの Key をもつ Dictionary をひとつで賄うのはダメっぽかったので、d[x][y] と階層化した (Dictionary<int, Dictionary<int, int>>)。C++の場合は、こんなことしなくても間に合っているようだった：
[7437758](https://atcoder.jp/contests/abc045/submissions/7437758)

### 9/10 ABC129D - Lamp
Difficulty 981, Probability 52%, time 34 mins でレコメンドされたもの。
最初の着想のまま書いてAC、23分：
[7445120](https://atcoder.jp/contests/abc129/submissions/7445120)

### 9/10 ABC089D - Practical Skill Test [累積和]
Difficulty 1104, 制約が Q >> h, w だったので、こりゃ累積和だなってんでとけた。
全ての数字は d の剰余で分類できるってのが、ミソっちゃみそかな（ってほどでもない）。
23 分：
[7448675](https://atcoder.jp/contests/abc089/submissions/7448675)

### 9/10 Tenka1 Programmer Beginner Contest C - Align
Difficulyt = 1152. さほど難しくないかなと思ったものの、解説を読んだ後でも、なかなか正解するプログラムが書けなかった。紙に書いて、落ち着いてコーディングしたらかけたもの。
[7451777](https://atcoder.jp/contests/tenka1-2018-beginner/submissions/7451777)

### 9/11 AGC024C - Sequence Growing Easy
敗北。なんか例外の多い「規則性」を見出したつもりで間違えたというのと、\(A_{i-1} > A_1\) のケースでは、べつに \(A_i > 1\) でもいいのを見落とし（勘違い）。
いちおう書いたけど、このように解く感覚をつかんでいない。要復習：
[7461064](https://atcoder.jp/contests/agc024/submissions/7461064)

### 9/12 AGC034B - ABC
Difficulty 968. ひとまず A に着目して、書いてみたら TLE. TLE になってみると、そうか、BC に着目して、これが連続するAを「あがって」
いくイメージかと気づいて、しゃくとり的に探索回数減らせると気づいた。気づいたあとも、なんどかTLEになる度高速化したり、
ばぐってWA出したり。自力で解けたけど、最初からスっとこのくらいかけるといいんだな：
[7475426](https://atcoder.jp/contests/agc034/submissions/7475426)

### 9/12 ABC063D - Widespread [二分探索]
Difficulty 1164. これは、糸口がつかめず（普通にやったらTLEなのはよくわかる）、解説をみた。なるほど。
条件を満たす最小のパラメータを求めるのは難しいが、与えられたパラメータが条件を満たすかどうかは計算できるときには、
こんな風に二分探索する手があるのか。思いつかなかった。

正直いうと、与えられたパラメータが条件を満たすかどうかを簡単に判定できる、ということにも気づけなかったけど。
爆心ダメージがA, それ以外が B （A>B)というのを、すべてにBだけダメージをあたえて、１体だけ（A-B)の「追加ダメージ」
と捉えなおすというちょっとした考え方のコツなど。

あと、二分探索を自分で実装することが少ないので、ぱっと一発でかけなかったりもした：
[7479064](https://atcoder.jp/contests/abc063/submissions/7479064)

### 9/16 ABC141D -  Powerful Discount Tickets [プライオリティ・キュー]
プライオリティ・キューが思いつかなかったのは痛恨。
あと、\(2^Y\) で割って切り捨てるのと、2で\(Y\) 回割って都度切り捨てるので違いがでそうな気がして気が散ってしまったのだけど…。Yビット右シフトだと考えたら、1ビットずつやろうが、複数まとめてやろうが一緒なのは直観的にも納得のはずだった。
AC取っておきたかった問題： 
[7556950](https://atcoder.jp/contests/abc141/submissions/7556950)

### 9/17 ABC023D - 射撃王 [二分探索]
これ、「二分探索の問題らしいな」と思って眺めていても、なかなか、
それで上手くいきそうな確信がもてなかった。慣れと計算量の感覚の両方が必要。
あと、H も S も結構大きいので、計算は long でやる必要があったのを見落としていて、
不要なバグをなんども出してしまった：
[7574714](https://atcoder.jp/contests/abc023/submissions/7574714)


### 9/20 ARC092A - 2D Plane 2N Points [二部マッチ、最大フロー]
二部マッチは最大フローに帰着できるというのをはじめてやってみた。蟻本の
Ford-Fulkerson コードを利用。

### 9/20 ABC010D - 浮気予防 [最小カット、最大フロー]
もう一つ、最大流でとけるというのでやってみた。最小カットは最大フローと等しいというので、直前につくった Ford-Fulkerson がつかえると思い。

たしかに、使えるんだけど、無向グラフなので AddEdge を二回呼ぶというのでWA連発と、
G = ０ のケースで、ReadIntArray に空行を食わせると Runtime エラーというのに随分はまった。

あと、最終的にログインしてみられるというのを、マークされた人からゴールへのパスで表すというのは、自分では思いつけなかったかな：
[7619461](https://atcoder.jp/contests/abc010/submissions/7619461)

### 9/21 AGC038A - 01Matrix
正解はとてもシンプル。いろいろ焦りながら考えていくなかで、
正解のパターンにはたどり着いていたのに、ごちゃごちゃした混乱から抜け出せず 0 完におわってしまった。
あと、一文字ずつ1万文字 Write すると TLE になるらしいというのは意外だったかな：
[7644986](https://atcoder.jp/contests/agc038/submissions/7644986)

一文字ずつ出力するとTLEになるのは、AutoFlushをオフにし、最後にFlushするようにしたら通った：
[8145382](https://atcoder.jp/contests/agc038/submissions/8145382)

### 9/24 ABC141E - Who Says a Pun? [DP, RollingHash + 二分探索]
他にも、Z-Algorithm でも解けるらしいけど、DP とローリングハッシュで。
DPについては、解説ビデオでは後ろからサーチしていて、ひとまずそれをまねてみた。
が、べつに前から見ていってもよくね？
もうひとつは、ローリングハッシュをつかって、部分文字列同士の比較を \(O(1)\) 
にしておいた上で、二分探索。それぞれの提出コードは、以下：

- [DP 後ろから](https://atcoder.jp/contests/abc141/submissions/7674069)
- [DP 前から](https://atcoder.jp/contests/abc141/submissions/7677383)
- [RollingHash + Binary Search](https://atcoder.jp/contests/abc141/submissions/7675416)

### 9/26 ABC041D - 徒競走 [bitDP, トポロジカルソート]
結構難しく感じたが、トポロジカルソートの数え上げに bitDP を用いるというのは典型なのかもしれない。あと、また dp 配列が int あふれて WA をやらかした：
[7697771](https://atcoder.jp/contests/abc041/submissions/7697771)

### 9/27 diverta 2019 Programming Contest 2 B - Picking Up
N が小さいので、(p, q) の候補すべてについて、pick 回数をしらべて最小値を答えればよい。
単純にやると \(O(N^4)\) だが間に合う：
[7708941](https://atcoder.jp/contests/diverta2019-2/submissions/7708941)

### 9/27 Educational DP J - Sushi [期待値DP]
ちょっと難しかったので、[まとめてみた](EDPJ)

### 9/30 AGC037A -  Dividing a String [DP]
最初に考えたのは、まず１文字選んで \(s_1\) とする。
\(s_i\) が一文字のとき、次の文字が異なれば \(s_{i+1}\) も一文字選ぶ、
同じなら二文字選ぶ。
\(s_i\) が二文字のときは、常につぎの一文字を選らんで \(s_{i+1}\) にするという方法。
…が、これでは、末尾で二文字選べないケースに破綻してしまう。

そこで、バックトラック…なんてやっているとスタックあふれちゃいそうだが、
これは DP でとける：
[7794952](https://atcoder.jp/contests/agc037/submissions/7794952)

※↑のコードは、AC だったけど、|S| = 1 であるような入力でしぬ。

### 9/30 AGC035A - XOR Circle
条件にあうよう円環上に並べなおした結果が \(b_1, b_2, \cdots, b_n\) となったとする。
そうすると、\(b_1 = b_n \oplus b_2, b_n = b_{n-1} \oplus b_1\) および、
\(b_i = b_{i-1} \oplus b_{i+1} (1 < i < n)\) が成り立つ。これを用いて、
\(b_1 = b_n \oplus b_2\) の一番最後の項を置き換えていくと、

$$<pre>{
b_1 = b_n ̟⊕ b_2
      = b_n ̟⊕ b_1 ⊕ b_3
      = b_n ̟⊕ b_1 ⊕ ... ⊕ b_{n-2} ⊕ b_n
      = b_n ̟⊕ b_1 ⊕ ... ⊕ b_{n-2} ⊕ b_{n-1} ⊕ b_1
$$}

この両辺に ⊕ b_1　すると、結局 \(b_1 \oplus b_2 \oplus \cdots \oplus b_n = 0\) 
となる。Yes になるのは、入力された数列を全部　XOR してゼロになるとき：
[7799304](https://atcoder.jp/contests/agc035/submissions/7799304)

嘘回答だった！→ [AGC 035 A - XOR Circle の正しい解き方](https://qiita.com/k_yamashita/items/2cce2d2dfac28a77cc60)

### 9/30 AGC032A - Limited Insertion 
逆から考えて、i 番目にある数字 i を取り除けるかを確かめればいいというのには気づいたんだけど、全探索の DFS を書いてしまって TLE。解説にあるように、各回で、取り除き得るもっとも大きいものを取り除くしかないことに気づけば計算量が減らせた。なるほど、もうひといき：
[7799966](https://atcoder.jp/contests/agc032/submissions/7799966)

つづきは [AtCoder 練習帳２](atcoder_drills2)へ

# 以前のメモ

丁寧にかいていたら続かないので、やめた。以下はやめる前の残骸。

## AtCoder Regular Contests
- ARC102 [C - Triangular Relationship (300)](arc102c)
- ARC101 [C - Candles (300)](arc101c)
- ARC100 [C - Linear Approximation (300)](arc100c), [D - Equal Cut (600)](arc100b)
- ARC099 [C - Minimization (300)](arc099c)
- ARC098 [C - Attention (300)](arc098c), [D - Xor Sum 2 (500)](arc098d)

## AtCoder Beginner Contests

- ABC123 [C Five Transportations (300)](abc123C)
- ABC122 [A Double Helix (100)](abc122A), [B ATCoder (200)](abc122B), [C GeT AC (300)](abc122C)
- ABC121 [C Energy Drink Collector (300)](abc121C)
- ABC106 [D AtCoder Express 2 (400)](abc106d)
- ABC099 [C - Strange Bank (300)](abc099c)
- ABC073 [D - joishino’s travel (400)](abc073d)