suzuken日記

【注意】解説ブログじゃないです。

日記【3/22~3/28】

3/22

 

SRM 489

 

Easy 1完

 

Easy

ワーシャルフロイドみたいのを考えると、任意の3つの点どの順番にやっても結果が同じである必要があることがわかる(証明は怪しい)

なので任意の3点を決め、next_permutationで全探索して判定する。

 

Med

 

座標(0,0)から1を表向きにした状態でサイコロ転がして、ある座標(x,y)に到達した時と経路の途中で1が表向きにこないような経路は何通りあるか。

 

プログラミング関係ない...。

 

サンプルの答えも全部2で明らかに嘘解を狙った問題。

場合わけしか考えられないし、証明もできそうになかったので萎えて終了(は?)

 

 

 

APちょっと勉強

 

 

 

最近ABCでボロ負けしてて典型力に自信がなくなってきたので1年ぶりにけんちょんさんの蟻本記事を埋めようと思った。

 

解説AC

yukicoder.me

 

どう見てもDPなんだが複雑な実装方針しか立たない。

典型なら解説開いてもいいかな... kmjpさんの記事を拝見する。

縦横で見たときに、縦か横の少なくとも一方は01交互に現れる必要がある。したがって縦横でdpをし、最終的な結果から一松模様の時の重複分を引くと答えになる。

めちゃくちゃ綺麗な答えで感動した。とはいえこれ典型?答え見るの早すぎん?

大反省。

 

 

3/23

atcoder.jp

わからないので答えをみる。

自力でできるべきだったと後悔する。

 

 

SRM 490

Easy 1完

 

Easy

 

ax+by=c c|gcd(a,b)という性質を考えるとなんとなく予想できる。

gcd(a,b)の倍数であってn未満の等差数列の平均を求めれば良い。

何故かn,mの大小が関係すると思って時間ロス。もったいない。

 

Med

問題文長い上に情報量多い。しばらく頭が働かなくなる。実質無量空処 。

終了10分前くらいになんとなく理解するも勘違いとバグがあり間に合わない。

問題理解したら、言われたこと実装してください問題なので頑張れば通る。(最大値見積もりミスって1回落とす。)

 

Hard解けるらしい。これも文字量多かったので後回しに...。

 

APぽちぽち

 

Moを履修。

雰囲気はわかったので明日もう一度仕組みを勉強する。

 

 

Codeforces Round #696 (Div. 2)バチャ

ABC 3完

 

A

割とむずい。

012を後ろと被らず、かつできるだけ大きくなるように貪欲に決定する。

 

B

最小ってのを見逃してtest case1で落とす。

それぞれの差がd以上になるように2つ素数を選びかけたものが答え。

 

C

最大の値は大きい方から選ばないと全部消えない。

最初の値だけ決定すれば良いので、最初の数列の最大値とペアになれるものを全探索して調べる。

 

D

前と後ろから見てswapをするかどうかを調べれば良いと思ったけど、通らない。

落ちるケースはわからないけど考察が十分でもないのでまあ...。

 

APぽちぽち

f:id:suzuken_w:20210324022911p:plain

100問解きました

 

最近解けるべき問題が全然解けない...。

まあ落ち込んでいる暇があるなら精進すべきなんだよね。

 

 

3/24

 

SRM 491

easy 1完

 

easy

なんかめっちゃ時間かかった(場合わけをミスってた)

 

Med

すごい嘘方針に突っ込む

実際は重複分を前計算してn^3のdpで全部調べれば良い

 

Easyはもっと速く解くべきだったし、Med解けるべきだった...萎え

 

APぽちぽち

 

抽象化 Rerootingを書く。めっちゃ便利。

atcoder.jp

復習をした。あんまり理解していなかったことがわかった。

 

codeforces.com

upsolvingをした。

 

あとはのんびり過ごした。

APぽちぽち。

 

こうして書くと1日大したことしてないことが判明する。萎えた。

明日はやるべきことを今日より増やしてみる。

 

3/25

 

その日に書かないとほとんど忘れます。

 

SRM 492

Easy 遅解き1完とかだった気がする

 

Easy

直線なので2点固定して試す。

それでも見つからない場合はn-1

 

Med

結構面白い問題だった。全域木を考えるっぽいんだけどまだupsolvingできてない。

 

二乗の木DPを履修 計算解析の話だった。

 

こどふぉdiv3

A

なんか列と行ミスったりして時間かかった。

B

dpした。

C

n^5をやって時間かかった。

set使ってO(n^2 log n)

D

解法浮かぶのに時間かかった。

そして、なんかWAがでた。

この考え前もやったよね?

E

mex的なのイメージしながらset使って書いた。

F

偶数ならrとc両方+1、奇数ならr+1をする。

場合わけをする。変な実装して1WAしているけどそんなに難しくないはず。

(本番はF,Gが逆転してた)

G

スライド最小値的なことを考えて実装。

場合わけが嘘で2WAする。

 

A~Eまでが遅すぎる。流石にやばいと思った。

 

APぽちぽち

 

日記はその日のうちに書こう(2回目)

 

3/26

 

SRM 493

太陽🌞

Easy

何故か場合わけで頑張ろうとする。

実際は一回で移動可能な場所を列挙して調べれば良い。

 

Med

これ結構面白かった。

距離がi以上→i文字前まで調べれば良い。

Kが高々7なのでかなり枝かりが利く。

 

 

この前のABC-Fを復習した。

 

GCJをやった。

 

APぽちぽちした。

 

なんか最後の方雑になってしまった。

とりあえずAPがやばい。

 

3/27

 

UTPC

give us+tsubasaさんのチームに入れてもらった

 

A・Jの実装・考察、Hのhackを担当した

 

A

最初競プロモードに入れてなくて読解に時間かかる。とりあえず無駄ペナしないよう心掛けた。

B

dpしそうだなとなるが怪しい実装しか浮かばないのでとりあえず飛ばす。

 

H

tsubasaさんがなんかバグらせてたらしい。適当にテストケース作ってたらhackできた。

 

J

チームメンバーは小さい方から埋めること考えてたけど、-1するなら大きい方から埋めた方が楽じゃないかとなる。それに上から合わせるのは損しない。→hackされる。

tsubasaさんがBを分割してく案を出してくれる。

この案と上から合わせる案を合わせると行けることに気づく。実装して投げる→WA

なんか色々ミスあって修正していくとテストケースのAC数が増える。(マラソン開始...

Aで使われなかったものの処理が必ずできるとは限らないことに気づく。使われなかったものについて処理して投げると通る。

 

他の問題についてはチームメンバーを全力で応援してました。

気づいたらかっつ君が通してたり、メンバー内でどっちが先にACするか競いあったりしてて面白かった。

 

 

ABC 197

1783 → 1772

ABCDE5完

 

ABC 省略

D

なんか詰まった。中心を原点に持っていって回転する方法しか浮かばない。

こんなめんどくさい方法で通しているの自分くらいだろ...。→想定だった。

数学問だとかなり遅くなってしまう...。

 

E

めっちゃ誤読する。(狭義単調増加と思ったり、全てとって0に戻るってところを読み飛ばしていたり)。

種類ごとに必ずどっちかの端で終了するのでDPする。

 

F

全然詰められないのにかなりの人が通している。どうせ既出→既出でした。

しょうもないバグを埋めて間に合わなかった。

 

 

反省

焦って誤読したときは一旦落ち着いて丁寧読む。Eでのムーブがかなり戦犯だった。

 

うーん。そろそろレート上げないとまずいですね...。

 

APやって寝た。

 

3/28

朝起きて応用情報少しやった。

 

SRM 494

 

Easy 1完

 

Easy

全部試す。

Med

変なdpしか浮かばない。そして何故か急激な眠気に襲われる。寝ながら考える。

 

Med 切り倒す部分に関しては差で求まる(確かにすぎて🦀になった)

なので独立して差分について期待値を求める。

和の期待値は期待値の和(期待値の線形性より)

 

 

SRM 487-Hard upsolving 

x-1 orx*mが1回の操作でできる

(x-1)*m+m=x*mなのでその分を引いてdpする。

 

このへんの時間何してたんですかね?応用情報やればよかった。

 

ARC

1772 → 1791

ABCD4完

 

A

2が関係しそうなことはわかったけど本番証明できなかったので実験した。

素因数2がなければ約数は奇数しかない。

素因数2が1つなら偶数の個数は( 奇数の約数の個数 ) * 1となり同じになる。

素因数2が2つ以上なら偶数の個数は(奇数の約数の個数 )*(素因数2の個数)なので偶数の約数方が多くなる。

 

 B

Second sum的なことを考えたけど無理ってなってた。

数え上げなので何か固定したい→最小値を固定して考える→昇順で最小値がai、最大値がajである時 j-i個の要素は2^(j-i-1)通りの入れ方がある。

それをうまくやればO(N)で処理できる。

 

C

これも何か固定したい→数列の最大値。

1からMまでを素因数分解し、素因数ごとに重複組み合わせをする。

 

D

bitごとに偶数個ならできる。そして和がMである。

これについてDPをする。計算解析がむずい。

本番は枝かりしてn=5000,m=5000が爆速なので投げた。ループの区間ミスって1ペナ(結構でかいミスなのに1ケースWAだった)

 

E

既出らしい。

本番は適当にやって通らないかなをした。

 

Bまでが遅くてC解いてから出そうとしてたけどCもかなり遅くなってしまった。

せっかくCまで解いて投げないのもったいないので順位表見ずに投げた。

C出した時点で+-0だったけどDが割とスッと解けたので助かった。

Dのペナはもったいない。

 

APは現状200問解いた。かなり少ない方だと思う...。

 

 

今週の反省

考察スピードがかなり落ちている気がする。焦りとかが出始めているのである程度解いてから提出でもいいかもしれない。(ただこの戦略atcoderでしか得しないので慣れるのは避けたい)

ABCとかやってて思ったけど最近、解ける枠の考察が遅い。

来週は

・こどふぉバチャを何本かやる

・典型知識を入れて「知らないので解けませんでした」を避ける

・高校数学の計算問題ちょっとやる

・応用情報過去問 合計500問

を目標にします。