ツイートすること(2021/03/01〜週)

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 反例をくれる人歓迎しています。

 

問題概要

atcoder.jp

 

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コード

atcoder.jp

 

まあ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 おつかれ