suzuken日記

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

日記【4/12~4/18】

4/12

生命情報処理の課題でDPが出てたのでコード書いて解いた。競プロは学業の役に立つ。

月曜日の授業+明日の予習ビデオを受けた。

あとはAPの勉強してたら1日が終わってた。

 

4/13

対面授業。対面+四時間分授業があってかなり疲れた。

2年次ディジタル信号処理かなりサボっていたのもあってかなりやばめ。AP終わったら復習頑張る。

 

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2746&lang=jp

昨日やってなかったので...

まあこれは言われたことをやる。

 

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1161&lang=jp

めっちゃ誤読&バグ埋め込みをした。

Case 1とかの書き方気をつけて欲しい。(古い問題だから書式が壊れてたりするのかな?)

計算量解析的な意味では難しいが、実装・方針はそんなに難しくはない(実際この前のABC400で類題が出るほど)ので400点はないんじゃないかな?

投票の点数の平均が高いのでまあ...。

 

ICPCの問題、誤読しがちだし結構バグらせる。定期的に練習しておいたほうがいいかもしれない。

APは午後問ちょっとやった。勉強時間少ないので不安。

 

4/14

 

APの午後問を解いた。セキュリティは7~8割が取れるようになった。システムアーキテクチャは全然やってないのでちょっとまずい。たくさんやっておきたい。

 

実験レポようにTeXをいじる。同じ階層にあるのに画像挿入できず。いろいろいじってたら何故か表紙が消えたりして意味がわからん。環境が原因だと思うがTeXに対してかなり嫌悪感抱いた。高校の卒論で使ってたのにね。

 

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1367

1日1問

なんでこれ200点なんだよ。他のに比べて実装軽すぎ。

 

あとはAPの勉強をした。

 

4/15

健康診断行った。

奇跡的に高校の友達に会えたのでくっちゃべった。

それくらい。

APの勉強やろうと思ってたら夕方になってた。時間の使い方下手すぎ。

 

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2340

解いた。誤読して超難問になってた。正しく読めたらめっちゃ簡単。流石に100点でいいでしょ。

 

APの午後問5問くらい解いた。

まじで安定しない。

 

4/16

APにむけて頑張る。

午前の問題をやってそのあと午後の問題を解いた。

組み込みシステム開発、情報システム開発は結構取れた。

あとTUPCの問題をupsolvingした。

 

atcoder.jp

枝かりの勉強になった。

とはいえ実行時間厳しい...。

 

4/17

 

atcoder.jp

久しぶりに見たら解けた。

APの午前対策。

AP前日だけど学生最強コンがあるのででる。

 

学生最強コン

ABCDEF6完

 

A

ちょっとむずい。式変形。

B

setで管理。

C

[A,B]の中にiの倍数が2つ以上ある含まれるようなiの最大値。

区間で引き算して1WA。

D

一瞬止まった。

よくよく考えると倍数となってしまうのは1つしか存在しないので(P-1)*(P-2)^(N-1)

E

全然解かれてないので一旦飛ばす。

 

バーガーの問題+水diffにあった問題(名前忘れた)+場合わけ

を合わせたような問題。

k>20は存在しない。L-1レベルについては偶奇で一意に求められる。

L-1レベルの文字列の長さがMの時、i番目とM-i番目の文字は一緒でなければならない。

これはUnion Findで管理できる。

この操作をk回やる前に文字列の長さが1になるなら存在しない。

求めてできた0レベルの回文については回文にならないように決める必要がある。

この時の文字列の長さがMの時、任意のiについてi番目とM-i番目の文字がUnion Findで同じグループなら回文にしかできないので存在しない。

そうでない場合はDPにより回文にならないように求める。

0レベルのどの文字とも同じグループにならない文字については最小となる文字を割り当てる。

 

この操作でk=0の時の処理が正しく行われなかったので

k=0の時は 

|S|=1なら存在しない

Sが回文なら1

Sが回文でないなら0

が答えとなる。

実装量は多いが典型処理をごっちゃにした問題なので頭を壊さずかけた(main内で100行くらいあった)。

 

F

チーム戦の解ける枠でよく見る。

こういうのは変更の差分を考えれば解ける→あってた。

あとはBITで頑張るって感じなのだけどこういう問題時間かかりがち。こどふぉとかでもよく見るのでこれを気に上位の実装を参考にしたい。

 

G

行列木定理らしい。知ってたし、結構最近にたい焼きも解いているのに使いこなせなかった。あとで勉強します。

 

こどふぉとかチーム戦の実装重めの問題が出るとdiffが高く出るのかな。

EF思ってたよりdiff高かった。Eに関しては偶然できたってのもある気がする。

 

午前がちょっと不安なので過去問を難問か解く。

 

4/18

 

AP本番。午前は過去問であまり見たことない問題が連発したり知識が抜けたりして最初焦ったが3回くらい見直ししているうちにいくつか思い出したので割といけた。

午後で爆死したのは予想外だった。原因は決めた分野に固執したことだと思う。組み込みシステム開発と情報システム開発は過去問やった感じ取り問だったのだが、結構難しくて計算も変な値しか出ず終了した。焦っているうちに見直しする時間が消えて終了した。体感6割超えてない。

答えをチラ見した感じ思っていた以上にはあっていそうだったけど見直ししなかったため凡ミスも結構あった。めちゃくちゃ運良くて6割ぎり超えのレベル。

午後が想定以上にできなさすぎて午前の自己採点せずに放置している。

 

まじで午後で爆死すると思ってなくてかなり萎えた。萎えすぎてARCブッチして課題消化してました...

ARC出なかったこと後になって後悔したが課題の諮問が3日後に控えていることに気付き割とARCブッチせざるを得ない状況だったことに気づいた。

 

ところでAP解いてて思ったのだが、Aと同じクラスタ含まれるものと書かれた場合にAを含めるかどうかとか、1ヶ月の日数、一年の日数(ここに関しては読み飛ばしている可能性もある)は暗黙の了解としていいのだろうか。今回そういうのが多くて解いてて結構困った。問題についての質問がNGであったので解決できなかった。

 

APについてはいろいろ思うところあるのだがマイナスなことしか浮かばないのでこれ以上は言わないことにする。まだ結果は出てないので確定はしてないが、もし秋受ける時は午後問は今回の5問+経営とか最悪国語力で殴れる問題を対策するようにしたい。

 

 

 

 

日記【4/5~4/11】

4/5

 

先週日記書かずに1週間を過ごしてしまった...。

 

学校の授業を受ける。なんかあまりやる気が出ないけど、課題を早め早めに忘れずに頑張る。

 

応用情報の受験票が届く。

割とまずい気はしているのだが午後どうやって対策していいかわからない。

 

今日やった過去問は7割超えた。ただ割とうろ覚えで答えて当たったのがいくつかあったので十分とはいえない。このまま続ければ本番6割超えはいける気がする。問題は午後。

ところで競プロ全然やってない。水曜日は空いている時間見つけてバチャやります。

 

4/6

久しぶりの対面で疲れた。

家帰ってから頭痛で何もできず悲しかった。

 

少し寝たら考察してた問題が解けたので通す。

atcoder.jp

 

授業受けるだけで時間と体力取られる。

応用情報が18日にあるのにコンテストが16,17,18にあり、健康診断もここに入っている。やばすぎ。優先順位がdiv1<<学生コンなので応用情報の進み具合で判断する。

 

明日は

・APの午後対策を本格的に始める。

・実験レポを進める。

・授業課題を終わらせる。

 

4/7

atcoder.jp

 

あとは課題とか色々やった気がする。この日書くの後回しにしてたらやったこと全て忘れてしまった..。毎日書かないとだめですね...。

 

4/8

なんか応用情報もやばいし競プロも全然してないしやばい

とにかくやばい

 

atcoder.jp

操作がどのように行われるのかが読み取りづらく誤読しまくった。

なんか通らない。コーナーを踏んでいる気がするんだけどわからない。もう少し考える。

 

 

 

今日は全休だったのでのんびりしてしまった。図書館籠るべきだったけど図書館利用時間が区切られててめんどくさい。

 

競プロに関しては学生コンまでにACL使って解ける問題はある程度触れておきたいと思った(多分出るでしょ

 

何もなさすぎて日記が雑になっているように感じる。

 

ECR91がスカスカだったので解いた。

codeforces.com

 

大きい方から貪欲

 

codeforces.com

 

distinct←本質

パターンを列挙ちゃんとしないと無限ペナします。

 

codeforces.com

マージテク

実装サボって計算量がやばそうなUF木投げたら通った笑(多分これもマージテクみたいな感じでlogになっていると思うけど)

 

F明日やる。

 

AP午後問題 セキュ2問とプロ2問解いた。セキュは知識詰めれば戦えそうな気がした。プロは見直しに時間かけるようにすれば満点近く取れるはず。

 

To do

・実験進める

・応用情報午前1回分

・午後問4問解く

AtCoder Library Practice Contest埋め

・ECR91-F upsolving

 

4/9

To do全然進まなかったけどやる気あるんか?

何故か思いつきでAOJ-ICPC1日AC

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1249

 

誤読しまくった上に実装が300行ぐらいになってめっちゃ時間とかした。

もうやめようかな

 

To doは今週中に解決したい。

 

応用情報知識が入ってなさすぎてかなりまずい。

ただ、午後問は知識入れてればある程度対策できそうな問題が多いように感じたので諦めずに頑張りたい。

選択分野は

プログラミング

データベース

組み込みシステム

開発情報システム開発

 

明日GCJらしい。全然練習してないので自信がない。

 

4/10

 

GCJ最後制約覚えてたら予選突破できたかもしれない...。たらればなのでわからないけど。

とはいえちょっと引きずった。

AGCまで午前問と午後問。午前あまり安定感ないのまずい気がする。

午後はデータベースができなさすぎてまずい。

 

AGC

AB2完

A

差分に注目すると解ける。max_elementとするところをmin_elementにしててWAを出してしまう...。

B

中央からpriority_queue使って貪欲に選ぶのが良いことがわかってから方針を詰めるのに時間かかってしまった。なんなら最初セグ木でやろうとしてた。

スタートで中央のどっちかは取る(取らなかったとしてもあとで後ろの値と交換すれば良い)のでスタート固定の2個入れて1個捨てるを中央から処理する。2つのうち残ったものの総和が大きいほうが答え。

 

こどふぉdiv1っぽさを感じた。

 

4/11

APの勉強で出れなかったdiv3をバチャでやった。

div3 

全完

ABCD 省略

E 区間の総和について最大から減らしていくとできる。この処理は高々N^2回

F   昇級するか今の状態で稼ぐかをシミュレーション

G NlogNなら定数倍高速化でぎり間に合いそう→まさかのO(NlngN) 想定解

 

Eで計算見積もり雑にしてしまって時間食ってしまった。

あとちょっとしたペナ(n/2をn-2と打ってたり)を減らすよう心掛けたい。

 

ABCまで午後問

データベース以外は頑張れば可能性ありそう...。

 

ABC

ABCDE 5完

 

n-1

B

reverseして回文判定→回文でないなら末尾に0を追加を100回(だいぶ余裕をもった)繰り返す。

C

Rが整数なのでx*x+y*y<=d*dを満たすdについてceil(d/R)が答え。

d<Rの時は2になる。(1ペナ)

D

むずい。

文字の種類数が10より大きいなら存在しない。

あとは10!通り全て試す。

E

LIS on Tree解いたことあればすぐ解けるはず。行きがけに加算し、帰りがけに減らす。

そうすると1からi番目に来た時点ですでに同じ色の頂点を通っているかがわかる。

F

崖になってた。

 

ポリアの数え上げ定理は蟻本以外で一度も見た事なかったので後回しにしてた...。

蟻本一周したほうがいいなと思った。問題は時間。

 

div2は来週にし、応用情報の勉強に集中。

 

 

日記【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問

を目標にします。

 

 

 

 

 

 

 

 

 

 

日記【3/20~3/22】

 友人に真似て1週間日記を書くことにした。ちなみに書くと決めてから書くまでに3日くらいかかっている。

 

ただの殴り書きなので形式とかはテキトー 

 

3/20

 

SRM 486 バチャ

Easy 1完 

Med システス落ち

 

Easy

Pay to winみたいな感じ。+は2倍だし、*はもっと少ない

-はおそらく制約的に必要ない

 

Med

誤読した。dpで上界と下界を持てば、Lの要素はdistinctなので今操作している部分列を簡単に求められる。あとは再起的に計算する。

誤読でサンプル合うなや

 

Hard

問題が良くわかりません。

点をつないで2つの領域にした時、2つのうち大きい方を自分に割り当てるのだがその領域をなるべく小さくしたいって問題だと思った。

その解釈だとサンプル1が合いません。終了。

 

 

SRM 802

Easy げき遅1完

1399 -> 1358 

Easy

確率の問題。うまい方針が浮かばずげき遅で解いた。

余事象考えた方が楽かなと思いその方針で考えた。

包除しないといけないことに気づく。

オーバーフロー怖かったけどなんとかシステス通った

 

Med

読んだ。面白そう。ただ、状態が結構あって色々考えているうちに終了した。

 

あとは応用情報技術者試験 過去問道場をぽちぽち

こんなにゆっくりやって間に合うんですかね?

 

計画的に行動するようにした方がいいと思った。1日のうち20時間くらいは無をしてたように感じた。

 

3/21

 

反省を活かして朝スケジュール書いた

 

SRM 487 バチャ

太陽☀️

Easy

わからなくて、最小費用流を書いた セグフォして落ちた

 

Med

 

得点の期待値Eは E=(m-n)*2/k+(m-2*n)/k=  m/k

 

あとは満たす答えがあるかを判定すれば良い。

k>=4の時、全部満たす。証明うまくできてないけどグラフを書けばおそらくできる(?)。

 

k=3の時、困った

 

良く考えると3^10*n^2全探索で間に合う。

 

 

ABC 176

 

ABCD4完  1804->1873

 

A 全部試す

B   stringで受け取り小数点より上を出力

C  10^6試して上半分下半分連結したものがN以下か試す

D 全探索 バグらせたので蟻本引っ張ってきて写経

E 計算量落ちない 飛ばす

F うっかりbitset投げたけど当然落ちる

 

upsolving 

E

 min(c,max(b,x+ai))の形にする。すると合成写像ができる。

 

 AP道場 ぽちぽち こんなにゆっくりやって間に合うんですかね?(2回目)

 

 

もう何もわからない。引退しても他に何もないのでもっとギアを上げて頑張る。

 

 

3/22

 

FFTを書く。verifym問題通らない。

 

SRM 488 バチャ

太陽☀️

Easy

期待値の問題。わからなくて解説開いたら典型問題だった。(涙)

 

 

FFTを書く。verify問題通らない。

面倒なのでatcoderのconvolutionで通す。あとで勉強する。

 

ARC115

A解けずnosub...

 

A

誤読して任意の組で同じ正答数のものが存在しないような問題の答えを求めると思っていた。鳩の巣原理や!って思ったらサンプル2合わず終了。

 

そして英文を読み、誤読に気づいた後も偶数-奇数=奇数ができずに終了。これは小学校でやりましたよね?

 

B

これも割と難しく感じた。

差分が不変なのでそれをチェックし、最小となる列をもとに構築する。

 

C

約数を管理してmexを求める。約数が多くても127個でありほとんどの場合それより少ないので間に合う。

 

ABC茶diffかよ...

 

 AP道場 ぽちぽち これ間に...

 

 

今週の反省

最近は停滞とかじゃなくて普通に一色下パフォ出しているしかなりまずい状況になっている。メンタルが終わっているのも要因かもしれないけど、知識不足や数学力がかなり足を引っ張っている印象。今週は蟻本と数学をできるだけたくさんやり知識を蓄えるようにしたい。

 

 

 

 

 

 

 

 

 

 

Educational Codeforces Round 97 (Rated for Div. 2) 感想

ABCDの4完

A

2*l>rならok

B

0101... 1010...の2つの場合を考える

この時、0でないといけない場所が1または1でないといけない場所が0である場合が連続する部分を区間で反転させれば良い(ちゃんと証明はしてないがどんなにそれ以外で分けてもその回数以上になる)

C

dpで書く方が圧倒的に速いがdpがぱっと浮かばなかったので最小費用流で書いた。

D

左から見て行った時、単調増加なら今見ている頂点に子をつける。そうでない場合次の頂点にいく。次の親に行く際、今見ていた親と同じ深さにある頂点が存在しない場合深さが一つ増える。

 

本番値更新の場所がミスっていて5ペナ履いた。ペナを履いた際は自分のコードがどのように動いているのか確認してから次の提出を行うよう気をつけたい。

 

E

a[i]-iのLISを求めることが終了10分前に気づいたが、焦りやいろんな考察で頭の中がぐちゃぐちゃになり解法が浮かばなかった。考察に時間をかけたものは書く前に考察したことを一旦整理するよう心がける。

 

感想

初速はよかったが後ろの方は焦りすぎてひどいことになってしまった。こどふぉに置いて初速がよかった経験があまりないため対処法を考えてなかったからだ思われる。

初速が良いときは順位表をあまり見ないようにしたい。(もちろんAC人数は適宜確認する。)

 

 

おまけ

前回のばちゃの復習

f:id:suzuken_w:20201028230116p:plain

 

E

二次元累積和&にぶたんで頑張る。

頑張る。

 

 

F1,F2

解説AC。

(ずれる前の得点)<(ずれた後の得点)

(ずれた後の得点) <(ずれる前の得点)

この2つが対照的であることに気づければ良い。

よって(k^n-(得点が変化しないものの個数))/2で求められる。

得点が変化しないものの個数について

隣会うものが同じ時、点数に変化しないものの選び方がk通り。

異なる時、点数に変化しないものの選び方がk-2通り。

あとは組み合わせ計算。

 

 

 

Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3) バチャ

ABCD1D2の5完

 

max(0,liの最大-riの最小)

B

qの隣合う数字が異なる時、右の値が答えと同じインデックスになる。

空いているところには小さい方から詰めるのが最適。

C

()()((((...

のように左にk-1の"()"、一番右に"(((...)))"と配置する。

そして、左の値から順に決定するように愚直にreverse操作する。(左端として選ばれる数が1以下であるため、操作回数がNを超えない)

 

書き終えた直後、体感難易度に対してAC数が少なかったので誤読してないかかなり不安になった。

 

D1

詰めきれず、雑にO(M*N^3)を書いて通す。

 

D2

よくよく考えるとaの要素を大きい方からkj個選ぶ時、aを大きい順に取るのが選べるものの中で最大の総和となる。そしてその選べるものの集合の中でインデックスが小さいものから順に取るのが最適となる。したがって、kj個選ぶ時、posjにある値は選べる集合の中でposj番目にaのインデックスが小さい値となる。

これはaをpairなどで(aiの値(大きい順),i(小さい順))となるようにソート、クエリ先読みでkjが昇順にソートしておき、kjが大きくなるたびに要素を追加し、posj番目の値をbitなどで管理すれば達成できる。

 

 

感想

Dはデータ構造使うことはなんとなくわかっていたのにもかかわらず、詰め切るまでにかなり時間をかけてしまった。

途中で考察したことを組み合わせればもう少し早く詰め切ることができたと思うので、詰まった時は考察したことをメモするよう心がける。

 

 

div2 #604 バチャ (感想)

codeforces.com

 

f:id:suzuken_w:20201016185344p:plain

ABCE4完

 

A Beautiful String

頑張る

 

my submission

 

B Beautiful Numbers

1~iの最大距離が長さi以下になってれば良いのでsetで管理

 

my submission

 

C Beautiful Regional Contest

mapで坐圧したあと半分を超えないように配列につめる(配列の中がメダルの候補になる)。

あとは金をとる人数を決めてそれを超えるような銀、銅の人数の決め方が存在するか尺取で調べる。(銀を決めたら銅は配列全体から金と銀の合計を引けば求まる)。

コンテスト中勘違いしまくったせいでめちゃくちゃ時間かかった(大反省)。

 

my submission

 

 E Beautiful Mirrors

エスパーした(カス)

aを逆順にし累積的に期待値を求める。

あとで正規解法確認する。

 

my submission

 

~コンテスト後~

Beautiful Sequence

0と2を先に決めて1,3を埋める。

1が最左の場合などうまくやればできるパターンがいくつか考えられるので頑張る。

 

my submission

 

感想

Cで時間かかったこと、Eでエスパーしたこと、Dが時間ないに解けなかったことは反省。

実装回ではあったがあまりバグらせずに書くことができてよかった。

思いついた途端に実装に走りがちなので、今後重ための実装をするときは実装前に注意点をメモしておく。