3/1
散髪&外食していた
upsolveしないとっていろいろ考えていたけどどれも進展なし
これをやるって絞らないと自分の場合効率悪いことがわかったので明日からは順番にやる
3/2
CGR E,Fを通した
Eの実装そこそこめんどいしF普通にむずかった
3/3
人生を進めた
5hの簡単枠のupsolve*3をした
今度こそ畳み込みを理解できたか？まあ前よりはといったところ
明日も引き続きupsolveかな〜
CODE FESTIVAL 2017 qual B - F Largest Smallest Cyclic Shift
editorialと違う気がしたので記事2個目
厳密じゃないです、ごめん(書けないので)
※全く証明にはなってないです。
代わりにまともに示してくれる or 反例をくれる人歓迎しています。
問題概要
a,b,cが全て存在する場合、f(T)はaで始まるので、もともとaだけの文字列があり、aとaの間にbまたはcをだいたい同じ個数ずつ挿入していきたい気持ちになります。
また、abcというsubstringの代わりに、acbというsubstringを作ってもf(T)が小さくなることはないことがわかります。
この考察をベースに考えます。
A%BでAをBで割ったあまりを表すこととします。
入力の和をNとします。
① 文字が1種類のとき
自明
② 文字が2種類のとき
aがA個、bがB個、cが0個とした問題が解ければ、a,b,cのどれが0個のときでも同様に解くことができる。
BがAの倍数のとき
(aを1個)+(bをB/A個)+(aを1個)+(bをB/A個)+...とするのが最適である。
BがAの倍数でないとき
(aを1個)+(bをfloor(B/A)個) という文字列xをA-(B%A)個 (=X個とする)
(aを1個)+(bをfloor(B/A)+1個) という文字列yをB%A個 (=Y個とする) 作り、
a->x, b->y, A->X, B->Yに置き換えて②を解いたものが最適である。
A+B>A=X+Yより、常にA+Bが減少していくので最大でもN回②を解けば終わることはわかる。(実際はgcdっぽいからlog？)
③文字が3種類のとき
aがA個、bがB個、cがC個とした問題を解くことを考える。
CがAの倍数のとき
(aを1個)+(cをC/A個)という文字列xをA個作り、
a->x, b->b, A->A, B->Bに置き換えて②を解いたものが最適である。
これは、abcよりacbの順のほうがf(T)が大きくなることと関係している。
以下、CがAの倍数でない時を考える。
Z=C%A, rem=A-Zとする。
Bがremの倍数のとき
(aを1個)+(cをfloor(C/A)個)+(bをB/rem個)という文字列yをrem個
(aを1個)+(cをfloor(C/A)+1個) という文字列zをZ個 作り、
a->y, b->z, A->rem, B->Zに置き換えて②を解いたものが最適である。
これは、cをほぼ同数ずつaの直後に入れたくて、cが少ない方(floor(C/A)個の方)が辞書順では弱いのでそっちをbでできるだけ強化したいという感じ。
BがAの倍数でないとき
X=rem-(B%rem), Y=B%remとする。
(aを1個)+(cをfloor(C/A)個)+(bをfloor(B/rem)個)という文字列xをX個
(aを1個)+(cをfloor(C/A)個)+(bをfloor(B/rem)+1個)という文字列yをY個
(aを1個)+(cをfloor(C/A)+1個) という文字列zをZ個 作り、
a->x, b->y, c->z, A->X, B->Y, C->Zに置き換えて③を解いたものが最適である。
A+B+C>A=X+Y+Zより、常にA+B+Cが減少していくので最大でもN回③を解けば終わることはわかる。
ACコード
まあACしたのでたぶんあってます
まとめ
解説記事を書いてる人を尊敬します
ツイートすること(2021/02/22〜週)
2/22
出かけた
昨日のE通した 実験ゲーだと思ったら考察をしなくなる癖があって、低難易度の実験ゲーだとすぐに見えるからいいんだけど難易度が上がると+αの考察がないと実験結果からエスパーしにくいので気をつけましょう
ARC087-F Squirrel Migration AC
時間かかった やったことある考察の詰め合わせという感じでいい復習になった
SRM 490 med 271/550 AOJ-ICPC カス
SRM 491 med 445/600 うってかわってまとも
2/23
upsolveいろいろ
ついでにKUPC 2012-K XOR回廊を通した
線形代数ゲーやるたびになにか学んでる気がするけどこいつ学んでる内容毎回同じじゃないか？
mod2での掃き出しの整数対応バージョン(bit演算でやるやつ)を書きました(笑)
2/24
5hやった
AOJ-ICPCの経験が活かせてうれしかった(か？)
SRM 微減
chal稼げたのはよかったけど同時にそのtopcoder様のジャッジののんびりさのせいでmedが落ちたので残念ですね
50^5 /2ぐらい頼むよ
2/25
SRM 492 med 165/550 最初ずっと嘘をはやしてた おすすめ
SRM 493 med 351/450 無
SRM 494 med 422/500 無
SRM 495 med 310/500 実装手間取った
SRM 496 med 420/500 簡単だけどまとも
SRM 497 med ???/550 構 文 解 析 100年後にやるかも 正直読解に失敗しているし飛ばしたい
2/26
無
周りの環境が安定していないとこういう日もある
有になりました
CODE FESTIVAL 2017 qual B - F Largest Smallest Cyclic Shift AC
ついでに解法記事を書いた (あってれば)結構おもしろい解法だと思う
AGCに向けてやってるけど銅diff埋めはつらいよ〜〜〜〜〜
2/27
ABC 出ました
crtを何もわかっていなかった
あとFで流量INFにしてたけどこれだめらしかったです、反省
CGR前にCFのレートが返ってきて嬉しい
これは2700タッチ間違いなし
5hでボコボコにされてぐったり
人類には早かったみたいなやつで心折られまくり
2/28
CGR13 出た -126 ワーストらしい
さすがに反省すると
AB よし
C 最初ペナ出すのはまあ仕方なくて、解決せずDに行って即実験したんだけど、これがよかったのか微妙 Cが頭に残り続けて集中力2割減するぐらいなら愚直を書くのもアリだったのかもしれない 思ったより時間かからなかった
D 実験してもよくわからなくて操作の意味を考えるとわかった 遅すぎ
E あんまり考えていない テストケース弱いのを期待して悪あがきでFを最後に書いたが悪あがきをEでやったら通ってたらしい まあ書きたくない見た目をしているからその判断は無理そう
F こっちに時間を使った N回(1個)vs(N-1個)をやる方針で失敗 定石だとこれだと思っていたけどどうやってもlog回が出てきそうな状況にならないから捨てるのもありだったのかも けど0以外の結果が返ってきたら勝ち、ぐらいまで来てしまうと正解方針だと思ってしまうだろ
G 問題文短いしどうやら読んでおくべきだったらしい 読んでおくべきだったって反省すること多いしとりあえず全部読むが正解の可能性はある
C,Dでそれぞれ2000人以上AC出てるのに1時間以上かかっていて大失敗だと思うんだけどそれでも3桁順位だからよくわからず いやむずいと思う
3月 AGC,SRM,SRMぐらいしか現状rated予定がなくて悲しい
まあ模擬地区とアジアとチーム練はやるだろうしあとDDCCとUTPCもあるしそこまで少なくもないとも思う
upsolveキューに高難易度が大量に入っていてぶっ壊れていてかなりヤバい
ツイートすること(2021/02/15〜週)
2/15
いろいろ復習をしたいと思います
ちょっと進みました
2/16
高速ゼータ変換,高速メビウス変換,添字and,or,xor畳み込みを書きました
理論はほとんどわかっていない
subset convolutionもそのうちやりたい
SRM 472 med 370/600 rng問題 類題見たことあった
SRM 473 med 468/500 ACだけなら無だけどeditorialが面白い
2/17
ブログへの避難を1ヶ月以上続けてたら"そういう"話題に首を突っ込まないことに慣れてきたので最近はTLを見ているしツイートもしている
このブログはまあツイッターonlyのときと比べて自分の負担になっているわけではないので未来の類題探し用として続けていこうという感じ
引き続き畳み込みを勉強している
昨日よりマシな理解になった もういいか
あとFFTはわかった やっとすぎる
なんか補間でもいいよねみたいなモチベはわかるんだけど、あとはなんかこうするとこうなってぐちゃぐちゃぐちゃ→うまくいきましたすげー(完)というイメージになってしまった
2/18
1問upsolveをした
SRM 474 med 334/500 いい問題な気がした
SRM 475 med 180/600 数論に弱すぎる 勉強になった おすすめ
SRM 476 med 165/550 草まみれ
SRM 477 med 451/500 うん
今日のは結構面白い寄りだった
2/19
SRM 478 med 203/500 面白いです おすすめ
SRM 479 med 254/500 手書きにしたら無限にバグった ライブラリは必要
SRM 480 med 347/450 無
SRM 481 med 447/500 無
SRM 482 med 187/500 擬似コードが意味不明でやる気なくしてた
SRM 483 med 371/500 うん
SRM 484 med 255/550 定数倍改善で通してしまった editorialのが天才 おすすめ
SRM 485 med 165/500 5hでほとんど同じのを見た じゃあなんでWA出したんですかねえ
まずまず
rngさんの問題だけ難易度が違いすぎない？と思うんだけど 他は8割がた見た瞬間解法わかるし
あと15問で500まで埋まるぞ～
明日はABC
賞金欲しすぎ
2/20
昼 5h
夜 ABC 賞金はもらえませんでした 問題の感想はありません
さらに夜 SRM埋め
SRM 486 med 362/450 まあ
SRM 487 med 365/550 そんなに難しくないけど結構すき
SRM 488 med 395/500 うん 本番1位のスピードっぽくてうれしー
SRM 489 med 393/500 editorialなくてわからないけど星ついてないし自分もこれはそんなに
無限ローディングが続いたので終了
明日はARCです 銀パフォだせば念願の2600
2/21
ARC 微増
増えたから良いです
無限場合分け取れなかったのは悲しい
1個だけのと2個以上つながってるのとでグループ付けするところに気付けなかった
ツイートすること(2021/02/08〜週)
2/8
睡眠
2/9
AIM Tech Round 5 (rated, Div. 1 + Div. 2) (virtual)
14:40〜
https://codeforces.com/contest/1028/standings
106位(本番86位)(パフォ2528)
ABCDE5完
前半から結構難しかったと思うけど詰まり過ぎて時間が残せなかった
2/10
昨日のバチャのF通した アハ体験
ARC093-F Dark Horse AC
一生4^Nにハマり続けて戻ってこられなかった
設定がめちゃくちゃ好きです
銅diff6問目
Codeforces Round #500 (Div. 1) [based on EJOI] (virtual)
https://codeforces.com/contest/1012/standings
39位(本番29位)(パフォ2724)
ABC3完
B ABC131-F
C dpで、状態が5通りぐらいになる
D ヤバすぎ thanks for explaining the "simple cases analysis" for Div1D 草
無限場合分けを丁寧にやると通ります
復習が早く済んだので2本目
Codeforces Round #499 (Div. 1) (virtual)
https://codeforces.com/contest/1010/standings
91位(本番74位)(パフォ2520)
ABCD4完
これをDiv.1に置くなよみたいなABCDに重実装のEだった
5hコンで見たzでソートして(x,y)をsetに突っ込むとy以上だとngみたいなのを管理できる、ってやつだと思ったんだけどそこそこ進んで落ちてしまった
ベズーの補題を学んだ
2/11
昨日の2本目バチャのE、lower_boundの位置を間違えていてif文を足したら通った、涙
Codeforces Round #497 (Div. 1) (virtual)
https://codeforces.com/contest/1007/standings
614位(本番485位)(パフォ1726)
Aのみ
A 1ペナ大反省 そのうえにぶたんいらんし
B 難しい
yosupoさんのツイートを見て完全に理解して通した なんかこういう解法Random LISに似たものを感じませんか？
2本目
Codeforces Round #488 by NEAR (Div. 1) (virtual)
https://codeforces.com/contest/993/standings
20位(本番17位)(パフォ2864)
ABCDE5完
C 適当に枝刈り信じたら計算量落ちてた
D めっちゃむずい けどdiff2500かあ
E 慣れてきた
さすがに4時だし昼もバチャしたから今日はやめておくか
明日はDiv.2あるし(出ないけど)、夕方と21時過ぎぐらいにバチャ2本できたらいいけどまあ寝不足だしARCの前日だし多めに寝るのもそれはそれでよし
2/12
CFで不正疑惑をかけられていて最悪の睡眠&起床
Codeforces Round #477 (rated, Div. 1, based on VK Cup 2018 Round 3) (virtual)
https://codeforces.com/contest/966/standings
121位(本番96位)(パフォ2370)
ABC3完
B かなり頭壊れてしまった
C 何も思いつかないので信じてbinary trieを貼りました xorだし上のbitから考えて無理だろこれって言ってたけど下から考えるとうまくいくのか、すごい
D クリークがあるときに困ってたんだけど時間切れだっただけでそこまでの考察は合ってたっぽい 前3問で詰まってこうなるのはかなり残念
D 通した こういう問題結構好きです
CFが5時からメンテっぽいからここからのバチャはなし ここ3日ぐらいわりと充実してた
2/13
今回は調整&準備万端だぞと言って仮眠からJOIの難易度7,8を解いていい感じに頭を起こしてARCへ------------> +9でした
B,C,Dどれもペナ吐いててもおかしくなかったし悪くはないのかな Bを包除で脳死でできたのとかCFバチャで最近見たやつのおかげ感あるし
Eできなかったのはカスだけどまあもう1段階実力上がればアベレージが相当あがるんじゃないでしょうかという期待を
だらだらして気持ちをリセットしてSRMへ
微負け 制約許せねえ
1000をそのうち復習
2/14
5h
爆睡
ツイートすること(2021/02/01〜週)
2/1
メモ
AC済み B
OK判定 F,I,J,M
残りA,C,D,E,G,H,K,L
4問除いて今日中にやるぞぐらいの気持ちでいたけど昼寝してた まあ夜は長い
yokohamaの2019もそろそろやっておきたいし今月はコンテスト+復習がメインになりそう AOJ-ICPCもやらないといけないんだけども
ABC190やった Dでlenを全探索してペナを吐いてしまった まあサンプルチェックしたらペナ自体は防げてそうだけど普通に間違えてるのダメそう
5hのC 通した これ最初に考えるべきだったわ
5hのE 通した 物理定期的に見る
5hのG 通した 勉強になった
5hのK 通した これむずいでしょ、似た考えやったことあるはずだからなんか形によって気付きやすさが変わったりしていそう メモリアクセスでTLE しょーもない
明日早いし寝ないと Dはだいぶ時間が空いてしまいそう
2/2
5h ノーコメント
2/3
5h ノーコメント
春休み2ヶ月間がんばるぞ
頭が疲れすぎて何もできなくなった 普段何をしているんでしょうか
2/4
今日はマイナスでした
前回のSRM、ライブラリを移せてなくて順位落ちてもったいなかったのでちょっと埋めてよく使うやつだけついでに再整備しようと思いまして
SRM464 med 427/550 無
SRM465 med 260/600 苦手すぎ 勉強させていただいた
2/5
5hコンのupsolve、ソロで2,3日あればできるラインまでをやるだけでもなかなか重い
1問やりました
2/6
ABC191 賞金目当てを除くと8回ぶりのABCリアタイ参加 どうしてこんな回を引いてしまうんでしょうか
何問か解いてSRM
SRMの前のウォームアップでmedを4問やった
SRM 466 med 461/500 うん
SRM 467 med 487/500 無
SRM 468 med 397/500 普通
SRM 469 med 150/500 大苦戦 辞書順最小の復元一生できない
SRM 799 あったまった 赤復帰
med解けたのは非常に気分がいいです
明日はCF Div.1
AtCoder橙,CF IGM,Topcoder赤を同時に達成したことはないからうまくやりたい
部分点こえー
寝られないので続行
SRM 470 med 422/500 制約優しい
SRM 471 med 435/500 うん
2/7
考察はしたものの1問も解けずCFへ
CF 700 あったまった
hackがうまくいったのはあるけどそれなくても+50ぐらいでいい感じ
レート更新待ち
このままの勢いでARCもね ワンチャン強くなってることを信じたい(が、競プロに使う時間を増やすほどそんなことはないことを思い知らされてしまう悲しさ)
ツイートすること(2021/01/25〜週)
1/25
AGC007-C Pushing Balls 通した
㊗️AGC-A,B,C全埋め Tableの見栄えが一気に良くなって気分がいい
感想としてはdiff2700以上のやつはだいたいどれもむずかった
Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) (virtual)
https://codeforces.com/contest/1017/standings
44位(本番36位)(unratedになったためパフォはなし)
ABCDFの5完
全体的に問題文がわかりにくいしFもしょーもないしクソセットじゃね？まあEが嘘だったんですが
C ARCでみた ついでにdilworthを復習した
E 回転がそんなにないと思ったけど嘘っぽい これだけ有名っぽい見た目で検索しても出てこないのびっくり
F メモリきつくしてみました、解決法を知っていますか？だけでかなりしょーもない気がする
editorial : The statement is complicated、じゃあないんだよね
KANのセットにあまりいいイメージがないな(しかしLGMなので僕の負けです)
1/26
死んでたら終わった
1/27
バチャのEを通した
この判定方法初めてみた 勉強になった
Codeforces Round #503 (by SIS, Div. 1) (virtual)
https://codeforces.com/contest/1019/standings
136位(本番105位)(パフォ2420)
AB2完 うーん
Aはすぐわかったのに配列サイズミスってもったいない Bはなんか実験しすぎて単純に時間かかった
C sccしてindeg=0のやつを塗ってそこと辺があるやつは無視して→…でできる気がしたけど全然証明できてないしAC数が察しだったからやめた
D こっちをメインで考えた 2点固定すると条件がその2点と並行なある直線上に点があるかになるからなんか偏角ソートしてがんばるんですかね、わからず
C 通した
これまじで天才 実質AGC 全人類やってほしい
D 通した
まあ初手だけでも見えてたのはよかったかな これ以外ないだろという気もしますが
明日明後日は試験ですがDiv.1どうしてこんなところにいれるんだとなっています
試験終わったら仮眠とって夕飯食べてABCでもやって頭起こしてDiv.1出て試験勉強を少しって感じでいく
#501以降のDiv.1があと1個
#401以降のDiv.1があと30個
1/28
試験、死〜ん(笑)
ABC189 やった
むずすぎ
Fは何も頭を使わなかったのでなんか誤差とか何も考えずにやってWAを踏み続けた
EはDIv.1出てなかったら解けていたかどうか怪しい
CF 698 出た
C未証明でカスですがレート上がりました
そこそこAC数出たタイミングのstatusをみてTL怪しい人すら0人だったので信じてしまった
1/29
徹夜で試験出て生活崩壊
なんかやる
ARC069-F Flags AC
銅diff5個目
当時は知らないけどもう典型な気がする、noshiさんありがとう
masさんの見て自分も数えてみたら、実はratedだと残りはARCが19問、ARC-likeが12問だけらしい
ついでにAGCは90問(!?!?)、AGC-likeは24問
1/30
明日までのレポートが突然実質今日までになったのでそれをやります
やった
競技プログラミングは役に立たなかったし、レポート課題も競技プログラミングに役に立たなさそう 無駄すぎ
今日、ボーッとしてる時間に考察した以外なにもしていない
明日は5h ABC簡単らしいから起きたらそれで目を覚まそうかな
1/31
時間がなさそう、残念
5h おつかれ