https://atcoder.jp/contests/abc282
ABC282を走った。
D:二部グラフ判定をDFSかBFSでして頑張るやつ。問題をうまく読めなかったりした。
E:ぱっと見で分からなかったので解説を見たら確かに全域木だった。
x^y+y^xの見た目に印象を持っていかれてグラフに帰着ができなかった・・・
後久しぶりにプリム法を書いた。クラスカル法はまだやってないからそのうちやる予定
8/10,8/11
ようやく復帰です(昨日出し忘れたので昨日の分もまとめて)
次の手番の人が後N個残っている状態で最大何個取れるか、にする事で先攻後攻を関係なしに計算できるようにするの、すごい
DPと考えつくにはどうすればよかったんでしょうか(N,Kの小ささからN*Kかなと思うべきだった？)
bitDP。自分としては難しかった。後最後に10**9を超えないだろうと誓約をよく読まずに出してしまった。よくない。
- 全てのテストケースに対する の総和は を超えない。
- 全てのテストケースに対する の総和は を超えない。
がすこい大事な問題。
(高橋くんがいる場所、青木くんがいる場所)という一つの点とみなして、二人のいるマスの0,1が違う状態を保ち続けられる状態移動を辺として引いてグラフを構築してやれば、ただのBFSに帰着できる、というやつだった。
~7/20
部分を見てどの様に影響するかを考える問題。
また、木は一点を決めればそこから見て根付き木になることと、木で最短経路を求める際に、一つの辺に対して、どちらの頂点側の要素かでグループ分けして何回この辺を通ったかがわかるということも覚えておきたい。
これ、ソートするだけなのにぱっとソートが思いつかなかったのやばい
こいつもやり直したが、普通に主客転倒を履き違えてた。
後、埋め込みテク(100個ずつぐらい飛ばした値を求めておいて、それを使って値を求める)はシンプルに勉強になった。
区間DP。知らなかった。知ればなるほど！という感じ。
後、初期値と探索できない場所の値を変えないと、探索していないと勘違いして延々と探索するというミスをしていたのが×、注意。
区間dpの慣らし、こっちの方が難しい。
だるま落とし(ICPC)
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp
これも解き直した。前は特殊な問題だな〜程度に考えていたけど、今回はしっかり区間dpを意識して解いた。
範囲の一番外側の部分が消し合えそうなら、内側が全て消せてるかの判定が必要、で引っかかったのでメモ。
典型は星5まではせめて7月中に終わらせたいという気持ち。
7/17
期末テスト勉強やら課題やらで時間が取れなさすぎる・・・
明日から星5までを中心に落とします
現在34/90
■
freee Programming Contest 2023（AtCoder Beginner Contest 310） - AtCoder
家族と出掛けていて出ることしかできなかった上に、D,Eを解けず3完に・・・
Dは単純に再起でよかったのに実装で変なことしたのを反省と、Eは状況を持ちながら進むやり方を思いつけなかったところがダメだった。
7/14
授業の合間に簡単目のを倒していた
両側からLISしてうまく管理
https://kenkoooo.com/atcoder/#/contest/show/22e4bbb2-2505-4d8c-b0f2-062a470aef88?activeTab=Problems
寝る前にとやったけど4問目で詰まってしまったので眠いから明日解き直す。
7/13
084 - There are two types of characters（★3）
忙しくて出来ず、慌ててこれだけやった。
本当は区間DPのやつとかやりたかったので、明日やります。(サボってはいけない)
