競プロあさかつ参加記

あさかつ 11/01

#あさかつ考察

1. a[:-8]
2. 地味にややこしかった。二点間でNGなのは、最短経路でもたどり着けない場合、途中でたどり着けるが、そこから残り秒数が奇数秒ある場合
3. 前解いた。AGCTのそれぞれについて累積和を取ったうえで二十ループで全探索して判定。
   まあ、って感じ

あさかつ 10/29 初あさかつ一位（参加人数が少ない）

あさかつ 10/28 DPを累積和の組み合わせ　過去の本番のリベンジに成功

#あさかつ考察
10/28

1. x文字目からx+w文字目を表示 => x+=wを繰り返す。
2. N<=100だから、全探索。
3. Nが偶数ならappend->appendleftを順に繰り返す。Nが奇数なら逆 insertだとTLE. dequeを使った
4. コンテスト中にWAして復習していた問題。今回は自力で解けた！
   dp。ただしdp[i] = sum(dp[x] where x <= i-3)みたいな感じなので、dpと別に累積和のテーブルを持っておけばよい。解説はもう一度読んだけどやっぱり良く分からなった。本番で解けなかった問題を自力で解けるようになるのはいいこと（しかも今目標にしているD問、緑パフォ）。

コンテスト中に解いた時の記録を見返したらなんか良く分からないことを書いてた。
まあもちろん前の復習の時の記憶が残っているのがでかいが、今回問題を読んだら制約を見てDPに見えるし累積和を使いたくなった。

あさかつ 10/27 位置をすべて区別すれば、累乗の世界

#あさかつ考察
10/27

1. 大小比較　a, cの大小関係は決まってないのでちょっとひっかけ
2. もう五回ぐらい解いてしまっていて
3. 差からPが求まり、Pと平均からQが求まる
4. 解けず。
   異なる位置から作られたものを区別する→2N-1っていう発想ができてなかったな。すべての文字を使うか使わないかの２択という。nCrの和みたいな方向性で考えようとしたが無理が出てきたが2N-1という考え方で見れば、解説のようにすべての文字cについて(cの出現回数+1)の積という発想ができたかも

久しぶりに競プロ。前回の漢字からしても少し疲れてる感あったので、週末ゆっくり休むことにした。あと久しぶりに週末人と話す用事ができていたこともあり。
今後も競プロ程よくのんびり続けていきたい

あさかつ 10/24 集中力皆無の日

あさかつ 10/21 バブルソートとかも学んでおきたい

#あさかつ考察
10/21

1. sortして最大値から最小値を引く
2. xを押した回数を数える。oの場合は一つ前にoでなかったら１プラスする。
3. 解いたの三回目
4. 解説とやり方違った。角も考慮に入れつつ周り８マスが#であるような#を見つけてメモしておいた。
   元の画像からそのマス＋そのマスの周り８マスを白く塗ったとして全部白く塗れたらOKみたいな。当て勘だったから改めて説明しようとすると、
   ある#マスの周りが全部#だったら、そこは縮小前の画像の#の候補になる。候補のみを#にした画像から縮小処理を行って等しくなればOK
   多分これと等価な解き方
5. 偶数番目と奇数番目をソートした後に全体をバブルソートみたいなことをしたけどWAだった・・・ｗこれすごい好きな問題だなあ解けるようになりたい
   https://t.co/OR7LjHieV4?amp=1

あさかつ 10/20 PAST第三回A～C問

A. case-insensitiveの場合はs.upper()とかで比較する。
B. 複雑な問題ではないが、データの持ち方に少し手間取った。
C. 最初にpython最強！と思ってar(n-1)を馬鹿正直に計算してそれを出力させようとしたらTLEになった。そのあとまじめに一度ずつかけていって10^9超えたらprint exitみたいな感じにしたら通った。
解説を読んだら、N>=31なら常に10^9超えるから、常にlarge, それ以下は順次実行すればよいとあった。いわれてみれば当たり前だが、具体例を丁寧に読んでこういう主要な値の見積もり（この問題でいうと10^9を超えないのはNが高々どれくらいか）とかを大事にしていかないとなと思った。そしてそれができてないと今回みたいなところで足をすくわれる。

あさかつ 10/18

この５問目いい練習になりそうだから解きたいよね・・・

あさかつ 10/17 余事象に目を向けよ

#あさかつ考察

1. gcdの関数のコピペ
2. やることは問題通り。でも、いつもマス目の問題は入力も多いからか実装にすごい時間かかってしまうので苦手意識がある。どうやったらスムーズに実装できるのか
3. A & B // A | B
4. 面倒くさそうだったのでスキップ
5. 数分間に合わんかったがAC.
   この前のコンテストで余事象求めればうまくいくパターンが印象に残っていて、この問題もそれだと思う。
   数字毎に、その数字が表れるインデックスを配列で持っておく（便利のため-1とnも加える）。そのインデックスを使って、「その数字が表れないような場合の数」を求めて全体から引く。
   解説を読んだが両端に仮想のインデックスを入れておくようなテクは「番兵」といわれているらしい？
   しれっと水パフォ通せたのでナイス

あさかつ 10/13 茶パフォから解くのもあり？

あさかつ 10/12 vscodeで解く練習（４番要復習）

#あさかつ考察
10/12

1. 偶数なら2だけを使う、奇数なら1,2だけを使う
2. 前解いた。Xに2をかけてく
3. 前解いた。Counterゲー
4. 解いたことあるけど解けなかった。解説読む->
   二分探索か・・・前も似たようなこと言ってたんだろうな

あと今日はvscodeを使ってキョウプロする練習。まだ慣れないし設定も詰めてないからぎこちない。ちなみにpython
でやりやすい環境みたいなの調べればきっとある
https://qiita.com/natsuozawa/items/c97f374900312fc4d8ca
この記事をみつつ、vscodeでキョウプロ解く環境を整えていく
エディターを整えるというよりかは、一連の作業を高速化およびストレスフリーにすることが目標。
この４番は解けるようになりたいっすね

あさかつ10/11 そもそも問題が理解できなかった回

#あさかつ考察
10/11

1. 前解いた。replace
2. これも前解いた
3. int(平均)とint(平均)+1だけ試したら通ったけど嘘解法ではないよね・・・？
4. 結局なんか問題の意味が理解できずに終わった。入力例１は高橋君が9を選んで青木君が１を選んだ時の9点じゃないのか・・・？

テストケースすらも理解できず終わったのは久しぶりかも・・・何を勘違いしてるんだ私は

あさかつ10/10 3,4問目要復習

#あさかつ考察
10/10

1. if文
2. 前解いた。前と同じようなミスをした
3. 前解説ＡＣしたんだけどな・・・うまく条件が導けなかった
4. うーん、、、解説は読んだ。

微妙な出来・・・うーん、台風のせい！３，４番はこれきちんと再度ＡＣしておきたいな
と、いいつつ今週末コンテストラッシュだし台風出しなのでのんびりします。。。メモしておけば未来の自分にまかせる・・・
マイペースにやっていきます。

あさかつ10/09 二分探索をきれいに応用できるといいよね

#あさかつ考察
10/09 4完

1. 前解いた。確かにP+P//100を足せばいいのか。P*101//100を足してた
2. ソートしてi番目の木とi-k+1番目の木の差を順にみていく
3. 前解けなかった。嬉々としてunion findをコピペ
4. 前解けなかった。全探索をうまくやろうなという、シンプルで個人的に好きな問題
5. WA.　解説を読んだ。かっこよく二分探索できるようになりたいって最近週に二回は言ってる気がする。解説より「問題 X が採用されるためには問題 1, 2, . . . , P − 1, X が採用されるように動くの
   が最適です」みたいなことは考えたけど、その後の考察とそもそも二分探索に沿って考えられなかったな

今日の５番みたいなのが解けるともう一段上達した気になれる気がする。
あと６番も問題軽く考察して解説チラ読みしたけどDPか、、、こういうのも同上。こういうのはEDPCに任せよう（解けよという話）

あさかつ10/07 簡単なDPはすらすら書けるようになりたい

#あさかつ考察
10/07

1. 最大値ー最小値　無駄にsortしてしまった
2. dpを頑張って作ったら時間がかかった。テーブルを100円の品物について、101円の品物について・・・と毎回更新していくことを考えていた。解説のようにi-100,i-101,..,i-105を見れば一度のテーブル更新で済む。こういうの難しいな
   あと本当は決め打ち解法したかった。100で割ったあまりでうまく決められそうな気がしたけど、ちょっと確信がなくてDPやってみるかと方針変更した。
3. 地味に2WA -> AC. どちらも@ではなくて異なるor片方が@だけど他方が"atcoder@"のいずれかではなければfalse
4. 二分探索を使うところまで考えた。

2は決め打ちで解きたかったな。ここで時間食っちゃうとコンテスト本番だときつそう
まあでもDPにチャレンジできたということで良しです

あさかつ10/04 コンテストで夜更かしした翌日でも精進していく

#あさかつ考察
10/04

1. 前解いた
2. 前解いて苦戦したので覚えていた。一文字だけ変えるような「良い場合」６通りを総当たり
3. 最小公倍数
4. これ前も解けなかった。今回はなんか無駄にビットで表そうとして、無理だった・・・素直にimos法とかセグ木の練習に使えるか？と思うので復習しよう

あさかつ10/03 三度目（に解く問題）の苦戦

#あさかつ考察
10/03
45分寝坊して参加したので時間気にせず3問解く。一時間以内に収まってはいるはず・・・？

1. Aの位置の最小値とZの位置の最大値を求める
2. 前に解いた。けどボケていて苦戦した。右のマスから順にiマス目までの最小値を持っておいて、それぞれiマス目の数字と比較するなどした。
3. 各文字の数をカウントしておく。一番個数が大きいものをL個とすると、1~LについてxC2をあらかじめ配列combとして持っておく。それを用いてまず一つもボールを取っていないときの場合の数sを求めておく。その後は、選ばれたボールの個数がxとすると、s - comb[x] + comb[x-1]でO(N)

今日ARCか。参加したいと思ってはいるが・・・昨日ACLBCをやっていてセグ木の話題が出てきたから、せめて勉強ぐらいはしておきたいんだよなあ・・・今日いきなり使えるかは別としてだけど
最近は、AtCoderの公式生放送とか、競プロYoutuberのかつっぱさんhttps://www.youtube.com/channel/UCqqeYOh1gk_TJ16sxazWhUg
の動画などを気が向いたときに拝見しています。もともとYoutube見るの好きなので、息抜きとキョウプロの知識向上を同時に図れるのでいいと思っています。
ゲームもそうだけど、実況しながら解けるのってすごい。自分は苦手ですが、実況しながらできるぐらいになると余裕をもって解けるようになるのかな。案外自分の思考がクリアになって悪くないのではという気もしています。

あさかつ10/02 転ばぬ先の丁寧な考察（をしたい）

#あさかつ考察
10/02

1. 0 <= sum < 20か否か
2. 4WAの後AC.　百の位だけ変えればいいとずっと思っていて。正直提出画面のテストケース名から類推しましたごめんなさい。ていうか6条件だからすべて列挙すればよかった
3. WA. 解説を読んでACを通した。（続く）
   （続き）N = 1のとき先頭に0を許すということと、M = 0になるような場合を考察できていなかった。
   今回は2,3二問とも考察の雑さが露呈した回だった・・・昨日久しぶりにチーター本をパラパラ読んでいて、やっぱ考察は丁寧にやらないとだめだよなあ～とぼんやり思っていたところだった・・・

二完厳しいな～～
アルゴリズムとかデータ構造うんぬん以前のレベルではある。きちんと手を動かして問題を理解し、いろんなケースを想定しておくのが大事だって本で読みました・・・
なんなら全部列挙すればよかった問題たちだったしね。
雑にキョウプロやっているのが露呈した回でした・・・

あさかつ10/01 場合分けは丁寧に

#あさかつ考察
10/01

1. x[:-8]
2. でかい数取ってくればsum(a)-n最大値取れそうじゃねって思って通した。Πa_i - 1か
3. 前解いた。
4. WA. BXAみたいなやつが答えに影響してくることは分かったが、そこの場合分けの考慮が足りなかった。

いやー4番の単純な考慮の足りなさ、悔しいな・・・時間の問題ではなく思いつかなかった。
頭のBの数、末端のAの数、先頭にB末端にAを持つ文字列の数というよく考えたらアンバランスな分け方をしていた。少なくとも解説のように先頭はBだが末端はAでない、先頭がBではないが末端はA、先頭にBかつ末端はAのように綺麗な場合分けから考察を始められれば違ったかも。

いわゆるMECEに場合分けしようっていうやつ？
5番も問題だけ読んだ。こういういかにもグラフな問題が解けるとキョウプロやってる感じがある。
解説だけでも眺めるかと思ったが公式解説は見当たらなかった。
他の人の回答をチラ見したがheapを使うのか？ダイクストラ法？
この今日の5番の問題気になる。
https://atcoder.jp/contests/code-festival-2014-morning-easy/tasks/code_festival_morning_easy_c

あさかつ09/29 DPは解けたけどBFSは解けなかった

#あさかつ考察
09/29

1. 両端を除いてmin(B[i-1],B[i])
2. 前解いた
3. 全工程行った場合をO(N)で求めておいて、一つ省いた場合の増減をO(1)でN回つまりO(N)で求められる
4. dp.というか、単純な漸化式で配列を埋めていく
5. TLE。とりあえず愚直に求める解を書いてみた。
   5の解説を読んだ。
   https://img.atcoder.jp/agc033/editorial.pdf
   解説の言っていることはわかる。まだ自分には幅優先探索をきれいに当てはめて解くことができないということだろうな。
   最初に全体をみて、「＃」の文字をキューに入れていく。幅優先探索だから、新たな点はappendして、取り出すときはpopleft。
   良く分からない処理を書いてしまったが、解説や解答例を読めば読むほど幅優先探索の出番って感じ。何回目の動作でたどり着く点なのかを、h,w,cみたいにキューに持っておく。
   幅優先探索とかもそうだけど、まだまだデータ構造に関して知識も経験も足りていない。
   今回みたいにキューを使って処理の優先順位を含めてうまくかけるというようなことを実装できるようになりたい。
   DPが解けたとか書いているけどまあDPというか一次元配列に情報をメモしていくって感じ。

あさかつ09/27 大寝坊しがち期

#あさかつ考察
朝間に合わない期到来。20分遅刻で参加

1. 解説を読んだら3桁という条件を見逃していた。
2. 適当に条件分けしたら通った。A,B一枚ずつの代わりにC二枚を買うべきかと、A, Bの一枚の代わりにC二枚を買うべきかどうか。
3. 前解いた
4. 時間切れAC. ソートして累積和。（続く）
   i番目のモンスターは累積和[i]*2>大きさ[i+1]ならi+1番目のモンスターと合体できる。大きい順にみて行って、まず一番大きいモンスターは上記の条件に関係なくOK、上の合体操作ができなくなるところまで数えればよい。

なんか雰囲気で解いたら解けてしまった回だった。ただ時間内では三完ではある。

あさかつ09/24 エラトステネスの篩について学びたい

#あさかつ考察
09/24

1. min(x-1,n-x)

2. 二重ループで文字列の部分列を一つだけ取り除いた残りの文字列を作ってマッチング

3. A, B ともにソートする。解説では大きい順にみていっていたが、小さい順にソートしてACした。人数の少ないグループから順に、小さい部屋から割り当てていった。

4. WA. 解説を読んでなんとなく理解した。エラトステネスの篩については要勉強。コンテスト中の考察としては、まず単純に総当たりをしては間に合わないなと考えた。その後数字の小さいものから順に割っていくことを考えれば、例えば8, 16, 24みたいな部分集合で16と24が一気に×つけれると思った。でも
   なんかそれは計算量減らすところまではいかなそうだと思った。dpの配列でどんどん倍数をメモって行けばよいのか。正直計算量については把握できていないし解説を流し読みしただけだが勉強にはなった。

エラトステネスの篩ってちょくちょくツイートで見かける。
今回の解説を見ればdpみたいなメモ用の配列をもっておいて倍数でふるいにかけていくみたいなものか？
あとは計算量の見積もりも大事そう。