2024年5月31日金曜日

AtCoder Regular Contest 177

　Cまで三完。

コンテスト後のツイート

D - Earthquakes

　連結成分ごとに分けて考えて良いということを元に考察し直してAC。
　「連結成分ごとに分けて考えて良い」ことさえつかめていれば、後のステップは「その柱が倒れたとき、その連結成分に含まれる柱が全て倒れる確率」を求めるという方針で良く、結構シンプルだった。

　ただ、実装は大変で、答えが0になるときの処理をどうするかでかなり困った。どちらかというと考察より実装にウェイトのある問題だったと思うので、考察で詰まったのは良くない。

時刻: 0 件のコメント:
ラベル:

2024年5月28日火曜日

Codeforces Round 946 (Div. 3)

 　Fまで六完。G、コンテスト後に考えていたけど結局自力で解けず。

コンテスト後のツイート


G. Money Buys Less Happiness Now

　コンテスト後も考えたけど分からず、こたつがめさんの放送の振り返りを見てAC。

　DPの高速化や、Cを小さい順に使うことばかり考えてしまった。


時刻: 0 件のコメント:
ラベル:

2024年5月26日日曜日

東京海上日動プログラミングコンテスト2024（AtCoder Beginner Contest 355）

　Dまで四完。

コンテスト後のツイート

E - Guess the Sum

　解法ツイートなど見てAC。

　質問回数の最小値を求めるのが本質なのだが、インタラクティブ問題なこともあってそれに気付きにくい。
　最短距離を求めると思えたら難しくないが、問題の見た目からセグメント木を何かする問題に見えてしまいやすい。そう思うと解けなくなってしまう。

　同じ罠にハマった人が多かった模様。

　これ、発想力の問題だから、ARCで出して良かったのでは？

F - MST Query

　解説AC。

　制約に重みが10以下とあるのは気付いていたが、どう利用すれば良いか分からなかった。順位表で多く解かれていたのを見て、もっと汎用的な方法があるのだろうと思い、検索に時間をかけてしまった。
　Link-Cut treeについても勉強しないとね。
　



時刻: 0 件のコメント:
ラベル:

2024年5月18日土曜日

yukicoder contest 430

　A一完。Bが全然思いつかないのは頭が働いていないせいだと思い、寝てしまった。


No.2758 RDQ

　解説AC。なんか、思ったより難しかった。

　やれることが約数列挙くらいしかないので、約数列挙して何かしようと思うのは良いが、何をすれば良いか分からなかった。
　約数ごとにやろうと思ったら、クエリごとにindexの二分探索で答えが求められるとは気付いかなかった。

No.2759 Take Pictures, Elements?

　自力AC。

　Aの各要素についてLISTを作り、二分探索により解いた。「移動候補が複数ある場合、左右でもっとも近くにある場所への移動が最適」なことを利用している。

No.2760 not fair position game

　自力AC。
　いわゆる真似っこ戦略で解けました。
時刻: 0 件のコメント:
ラベル:

2024年5月14日火曜日

AtCoder Beginner Contest 353

　Fが解けず六完。

コンテスト後のツイート

F - Tile Distance

　K=2の場合をケアしてAC。
　Kが小さい場合に問題が起きそう、とは思ったから時間があれば解けたと思うので、Gに時間がかかり過ぎたのが敗因。

　ただ、K=2の場合をケアしたつもりがWAが二個でてしまい困った。
　これは、最初の方にしたK=2の場合は嘘になる考察をコードに入れっぱなしにしていたせいだった。考察に漏れがあったなら、コードも見直さないと。


時刻: 0 件のコメント:
ラベル:

Kotlin Heroes: Episode 10

　Fまで六完。またもT-shirts圏に入れず。

コンテスト後のツイート


H. Composite Spells

　各魔法について、その魔法を使ったときのHP増減と、その途中のHP増減の最小値（つまり、最大ダメージ）を持って計算していけばOK。

　コンテスト中この方針で書いたがWAが出て、何が原因か分からず迷走してしまった。

　コンテスト後、解法ツイートを見て、LongをBigIntegerに直したらAC。

　Kotlinって標準で多倍長整数使えると知らなかった。
　Longで収まる範囲の問題しか出ないと思い込んでいたのが敗因。Longで収まると思い込んでいたからoverflowは考えなかった。



時刻: 0 件のコメント:
ラベル: ,

2024年5月13日月曜日

Codeforces Round 944 (Div. 4)

　最後の問題が解けず。


H. ±1

　2-SATという情報を得てAC。

　この前のABCでは2-SATじゃないかと嘘考察してハマったのに、実際に2-SATが出たら解けなかったのは情けない。
　ただ、最初見たとき2-SATは疑ったので、時間があって落ち着ければ解けていたと思う。
時刻: 0 件のコメント:
ラベル: ,

2024年5月7日火曜日

yukicoder contest 291

 　ABの二完。Bで唖然とするようなミスをして、Cも分からぬまま終了……。


No.1478 Simple Sugoroku

　自力AC。

　ワープを使う場合、「後ろx個へワープで辿りつけたらそこからは歩く」という戦略を取るのが良く、このxを全探索すればOK。

No.1479 Matrix Eraser

　フローの練習で解いた。自力でグラフは構築したがTLEが取れず、他の人の提出などを見てAC。

・start→縦でまとめられるもの→(i, j)→横でまとめられるもの→goal

　というグラフを考えたが、これだとMLE・TLEしてしまった。
　（i, j）の部分は省略することが可能。また、A[i][j]の値ごとにflowを流せば良いので、H+Wの大きさのflowをHW回流す感じで解ける。
　こうすればACできた。

　ただ、言語とかDinic法の実装とかで工夫したら最初の方針でもACできたはず。そういうライブラリも持っておきたいね。
時刻: 0 件のコメント:
ラベル: ,

Educational Codeforces Round 165 (Rated for Div. 2)

　Dまで。

コンテスト後のツイート

E. Unique Array

　解説AC。

　このG問題の類題で、似た解法で解ける。

　各要素が唯一である区間を長方形と思って管理するところまでは同じ。その後、それを使って貪欲に処理していく。

　最近解いた問題なのに、コンテスト中も、今復習しようとしたときも全く思い出さなかったのはひどいのでは。
時刻: 0 件のコメント:
ラベル:

2024年5月5日日曜日

AtCoder Beginner Contest 352

　Eまで五完。

コンテスト後のツイート


 F - Estimate Order

　解説AC。

　重み付きUnion-findで連結成分ごとにまとめた後、bit DPする。bit DP部分をDFSっぽくやって高速化した。

　コンテスト中もまずbit DPできないか考えたはずなのだが上手くいかない気がし、2-SATでいけると勘違いして突き進んでしまった。「どれか一つが真」って条件は2-SATで表せないですね。

　色々ひどかったけど、2-SATの復習は多少できたかもしれない。

G - Socks 3

　解説AC。

・前半の、期待値を場合の数に置き換えるパート
・後半の、場合の数を多項式の積で表し、形式的べき級数で計算するパート

　どちらも典型なのだが、身に着いていない。


　どちらかというと、後者は問題演習を積めば身に着く気がするので、前者の方がより身に着けたい内容か。期待値を、「i回以上である確率P_i」の和で表すという方法は覚えておきたい。
時刻: 0 件のコメント:
ラベル: ,

2024年5月4日土曜日

Codeforces Round 942 (Div. 1)

　B2まで。CombinedじゃないCodeforces Div. 1はちょっと避けたりしていたけど、今回は参加。レートが落ちず良かった。

コンテスト後のツイート


 C. Fenwick Tree

　解説AC。

　各成分の、k回後に対する寄与が二項係数になるということに気付けなかった。それが分かればすんなりAC。

　なお、コンテスト中考えていた解法だとΣのベキ乗の係数が必要そうになったのだが、その方向でも正しい答えを得る方法はあったらしい（が、理解できていない）。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 943 (Div. 3)

　時間ギリギリ全完でした。

　G2の方針自体はもっと速く思いついていたんだけど、これで計算量が良いかで迷い、またSortedSetを使わなくては実装できないのか？（使ったらTLEするのでは？）　といったあたりでも迷って時間かかってしまった。
　あと、並列二分探索でできないか？　などとも考えた（できなかった）。

　実際に実装してみたらACでした。

コンテスト後のツイート







時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)