今日の精進 2020/06/03
Educational Codeforces Round 57バチャ
ABCDの4完
A:l,l*2を出力
B:左端、右端の連続アルファベットだけに注目
同じなら(左の連続数+1)*(右の連続数+1)
異なるなら(左の連続数+1)+(右の連続数+1)-1
右と左どこで区切るかみたいなことを考えると数え上げしやすかった
C:式とか図をいじいじしたら正n角形は180/n *(1,2,....,n-2)の角度を作れることがわかったので全探索
n = 180のときに178度まで存在してて179度はn = 360のときにできるらしいので計算量大丈夫
D:名前出したら警察がくるDP
dp[i][4]で0は何も持ってない、1はh持ち、2はha持ち、3はhar持ちのイメージで遷移
https://codeforces.com/contest/1096
青~黄diffバチャ
1完
A:joeチャンネルで出た問題だったので解法覚えてた
式変形するとS[r] - r*K >= S[l] - l*Kを満たすペアの数を探せばよくて
set使って座圧した後にBITを使って条件満たすものを数え上げる
https://kenkoooo.com/atcoder/#/contest/show/e749c884-d16b-482a-a603-5e9df223a3b8
復習
最小値がmidを上回ってるかどうかで二分探索
highがokライン、lowがngライン
midがokならok側の領域を減らしたいのでok=mid
上回ってるなら移動できる
確認はBFSで移動していけば大丈夫
今日の精進 2020/06/02
51回目
— pitsu (@pitsu_kyo_pro) 2020年6月2日
ABCの3完
Educational Codeforces Round 17https://t.co/SNBb14fSdk
A:これ計算量大丈夫なのか....sqrt(10^15)....大丈夫やんけ
kが10^9でも約数がそんなにあるものないやんけ....はぁ....
B:aを全部やってbを全部やって余ったものをcで小さいものから
使っていく
c:左から使える範囲をposで求めていって右から使える範囲をposで求めていって左で使えるまで使ったとき右でどれだけ使えるかを二分探索していく
bより大きいサイズが来たときやばい(3WA+1時間吸われた)
青diffバチャ
ABの2完
A:こういうのはとりあえず折れ線で考える
a-bが負になるやつは状態を下げれるから先に使いたいよね
なので先にこいつら使う
使う順番は最大値が大きくならないようにしたいからaが小さいものを優先して使う
a = bはa-b使い切った後に使うのが一番よさそう（他の場所渋くない？
a-bが正になるやつの処理困った
最終地点考えたとき最後に使うやつは上に飛び出てほしくない
なのでbが大きいやつを先に使うか～～
->AC
a-bが正になるやつの処理雑すぎたので解説ちゃんと読む
B:各地点iでセグ木で最大値を左側、右側で調べて二分探索
二分探索でj番目とiの間の最大値はh[i]であればその場所はokダメならngにしてやる（めぐる式
https://kenkoooo.com/atcoder/#/contest/show/9819ad78-8f0d-4490-986f-0b12d6a96e9d
さっきのバチャの復習
僕が考えたこと
今見てる地点のものが最初に出せないならそれ以降のやつも絶対最初に出せない
なのでそれ以前のうちどれか一つを出さなきゃいけない
それまで見てたものの個数を掛け合わせる（以前に引いたものがあったらそれはカウントしない）
添え字で頭崩壊（悲しい
この記事が僕のやりたいことをきれいに実装しててよかった
今日の精進 2020/06/01
昨日のF
一か所から伸びる遷移は3本あって
1.部分集合に含めない
2.部分集合に含めるけど足さない
3.部分集合に含めるし足す
一つ目と二つ目はstartとgoalが一緒だからdp[i+1][j] += dp[i][j]*2でいいのか
HCPC個人戦バチャ
Aの1完....
A:スタート地点からいけるBFSで自分の位置より一番低いところに行くようにする
https://kenkoooo.com/atcoder/#/contest/show/3bfedc78-18e0-4104-bc02-01c2d7a8097a
さっきのバチャのB
どっちで終わるか判定して各コマを除いたときゲームは終了しているか全探索
青~黄diffバチャ
Aの1完
A:dp[i][m][bit]で
i番目まで
最後に見た種類はm種類目
今まで見たものはbitが立ってるもの
https://kenkoooo.com/atcoder/#/contest/show/a5a42f33-d776-4588-8c57-03aa6faa9887
復習
頂点を二部グラフに分けたとき、塗った結果は一意に定まる
2部グラフに分けた後に、間にある辺は全部塗っても奇数長の閉路はできない
なので絶対間の辺はオレンジに塗る
間の辺を繋げても連結になってないものは同じグループ内の辺を繋げても閉路は絶対できない
なので塗らなきゃいけなくなって二部グラフ崩壊
だから頂点を二部グラフに分けたときに連結になってるものを数え上げて最後に/2
これはNim数に帰着できるらしい
この記事がわかりやすかった
今日の精進 2020/05/31
ABC169
ACDの3完(笑)
https://atcoder.jp/contests/abc169
A: A*Bを出力
C: long doubleでA,Bを入力してA*Bをlong long型に入れて出力
D: Nを割り切れるものを全探索して割り切れるだけ割った後にk*(k+1)/2<=(割れる回数)kの最大値を足してく
Codeforces Round #646 (Div. 2)
ABCの3完
A: 無限場合分け
B: iより左は0(1)右は1(0)みたいにO(n^2)
C: xの次数が1だったら先行勝ち、違ったら(N-2)%2が1なら先行勝ち
今日の精進 2020/05/30
50回目
— pitsu (@pitsu_kyo_pro) 2020年5月30日
ABCDの4完
Educational Codeforces Round 39https://t.co/GqEuBUWMtT
NOMURAコン
ABCの3完
https://atcoder.jp/contests/nomura2020
課題許さねぇ
今日の精進 2020/05/29
49回目
— pitsu (@pitsu_kyo_pro) 2020年5月29日
ABDEの4完
Educational Codeforces Round 40https://t.co/r530proqkJ
昨日えでゅふぉD(Hackで落ちたので)
https://codeforces.com/contest/1359/problem/D
青diffバチャ
1完
うーーーーん
https://kenkoooo.com/atcoder/#/contest/show/2cc10eaa-2759-4174-b7f7-422e77a9b202
復習
