2024年8月25日日曜日

yukicoder contest 441

　ABの二完。


No.2844 Birthday Party Decoration

　ひどかった。

　正しい解法を実装しようとしたが答えが合わず（マイナス方向に進むときの計算をミスっていた）。
　プラスとマイナス両方へいく場合を、（プラス側に行く場合の距離, マイナス側へ行く場合の距離）をソートし、累積maxを用いて計算しようと思ったが、その場合の総距離の計算を間違えていた。（大きい方は二倍しなくて良いと勘違い。）

　どのようなテストケースでWAが出ているかを見て、やっと気づいてAC。

No.2845 Birthday Pattern in Two Different Calendars

　解説AC。

　貪欲で良いと勘違いし、WAになっているテストケースを見ても何で落ちているか分からなかった。言われてみればmod M-1での分解を考えるという典型なのに全く思いつかなかったのはまずい。

No.2846 Birthday Cake

　解説AC。

　LCMを使ってDPするのは考えたけど、除いて良い数があると思えず、別な方法も思いつけずで解説を見てしまった。
時刻: 0 件のコメント:
ラベル:

2024年8月20日火曜日

AtCoder Grand Contest 067

　A一完。

コンテスト後のツイート

C - Divisibility Homomorphism

　解説・解説放送を見てAC。

　コンテスト中の考察は全く間違っていた。

・1 3

　がNoだと気付くのが第一歩で、そこから上手く考察を繋げていかなくてはいけなかった。

　こういうのが答えになりそう！　と思いつけば（証明できなくても）ACにたどりつける問題ではあるけれど、逆に、一旦間違った方針に進むと方向転換の難しい問題だったと思うので、どうしようもなかったか。




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

2024年8月18日日曜日

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)

　D1までとF1で五完。

コンテスト後のツイート

F2. Court Blue (Hard Version)

　自力AC。F1と同じ方法でできた。

　F1では、nに一番近い素数を基準にDFSしたわけだけど、それに加えて、mに一番近い素数を基準にDFSしたらAC。nowをmin(p-1,m)から小さい方へ動かしていき、(p,now)からxのプラス方向やyのプラス方向にどこへ行けるか調べていく。それで、x成分がnにたどりつけたら探索をやめる。
　これをx,y逆転させてもう一回やる。

　これでACできたけど、n=mの場合と違い、正当性はやや怪しい。

（追記）正当性は大丈夫そう。n<mでnに一番近い素数を基準にするときが問題なのだけど、mがある程度大きいなら、mに近い素数をpとして、(n,p)にたどりつけるので問題ない。nとmが近いときは、上記の方法で多分大丈夫。


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

2024年8月17日土曜日

Educational Codeforces Round 169 (Rated for Div. 2)

　Eまで五完。

コンテスト後のツイート


F. Make a Palindrome

　解法ツイートを参考にAC。

　コンテスト中に三乗で解く解法は思いついていた。
　配列Aにおける値は、

・配列Aの左端右端の要素が同じなら消す。違うなら、小さい方を合体させて答えを一つ増やす。これでO(配列の長さ)で求まる。

　で求められる。

　この計算量を落とす方法が分からなかったが、累積和を使って特徴づけできる。

　「両端の要素が同じなら消す」という操作をできるだけ増やしたい。a, b, c, dをindexとして、(a, b)から両端を消すことで(c, d)へもっていくことにすると、累積和Sについて、

・S[b]-S[a]=S[d]-S[c]

　が成り立つ。これを変形して、

・S[a]+S[d]=S[b]+S[c]

　なので、二つの累積和の和が同じ物を集め、index i, jについてj-iが小さい方から見ていくと、(z, w)の後に(x, y)がきた（S[x]+S[y]=S[z]+S[w]が成り立っている）なら、DP[x][y]=DP[z][w]=(z-x-1)+(y-w-1)のようにして全ての値を求めることができる。
時刻: 0 件のコメント:
ラベル:

2024年8月15日木曜日

Codeforces Round 966 (Div. 3)

　Gまで七完。Hが解けず。……と思ったが、Cがシステムテストで落ちた。

コンテスト後のツイート

C. Numeric String Template

　sの長さがnじゃなかったら即ダメ、と返すようにしてAC。その事実自体は気付いていたけど、こういうcaseが作れるの気付いてなかったなぁ。

H. Ksyusha and the Loaded Set

　解法はあっていた。
　A[0]とA[1]の間の区間をセグ木に入れるのを忘れていた。こんな単純なことだったとは。

　まあ、こういうときはランダムテスト書くしかないかね。書こうか迷ったんだけど、ちょっと時間が足りなそうだった。（ランダムテストは書かず、テストケースを見てACしました。）

　

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

2024年8月12日月曜日

AtCoder Beginner Contest 366

　Dまで四完と失敗。

コンテスト後のツイート

E - Manhattan Multifocal Ellipse

　コンテスト中の方針でAC。

　xに対して、x方向に関するマンハッタン距離の和を求める関数を得なくてはいけないが、そこでミスがあった。
　ただ、それを修正しても、二分探索で上限・下限を求める方針だとTLEし、尺取りに直さなくてはいけなかった。

　解けなくてはいけない問題だったのは確かだが、実装もやや面倒だし、簡単というわけでもない気がする。こっちよりFがACできなかった方がまずい。

F - Maximum Composition

　解法ツイートを参考にAC。

　コンテスト中、うまくソートする問題だろうと思い、

・C(Ax+B)+D>A(Cx+D)+B

　を変形して、

・BC+DとAD+B

　の大小比較を考えれば良いというところまでは書いた。なんでそれで解けなかったんですか？　そこで式変形は止まっている……。

　さらにいうと、昔、この問題はオンサイトで自力ACできているのに、今回解けなかったのはひどい。
時刻: 0 件のコメント:
ラベル:

2024年8月10日土曜日

yukicoder contest 440

　AとCの二完。Bが解けず。


No.2836 Comment Out

　全く思いつかなかった。

　「数を増やす操作」を繰り返したものが最大だと思い込み、たとえば、N=5なら、

・5 4 3 2 1

　とか

・2 4 5 3 1

　みたいな列が最大だと思い込んでしまった。（それ以下のものは全て作れる）

　しかし、この判定が意外と難しく、そこで間違えていると思ってしまった。（今でも、やり方が分かっていません）

　実際の解法は単純でした。実験コードをすぐ書くべきでしたね。
　Ratedコンテストならもっと早く実験していると思うのでACできただろうと思うものの、多分実験コードを書いたのはWAを二個くらい出した後だし、ACするまでに時間かかっただろうな……。

No.2838 Diagonals

　自力AC。

　これは、（実験せず）頭の中で考えて正解を導けた。嬉しい。


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

2024年8月8日木曜日

Codeforces Round 964 (Div. 4)

　全完。

コンテスト後のツイート




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

2024年8月5日月曜日

AtCoder Regular Contest 181

　ACの二完。

コンテスト後のツイート

B - Annoying String Problem

　解法ツイートを参考にAC。

　Sの一文字目がTの何文字目にあたるのか？　を調べる方針は良かったし、TがSの繰り返しだろうというのも当たっていた。
　そこまでくればgcdで周期を考えるのは自然なはずだが、これを思い付けなかった。うーん。

　また、Tの長さを計算したら負になる場合がある、ということに気付かずWAやREを重ねてしまった。
　考察は後一歩だった気もするが、ここに引っかかることを考えるとACは遠かったね。

D - Prefix Bubble Sort

　概ね自力でAC。（コンテスト後にツイートなどは見たけど、あまり参考にせず解いた）

　xという操作を適用すると、「x以前にあって、転倒数への寄与が0より大きいものたち」は、indexが一つ下がり転倒数への寄与が一つ小さくなる、ということには割合すぐ気付けた。
　が、実装が上手くできず、Aが広義単調増加であることをどう使えば良いかも迷った。長いこと遅延セグ木でどうにかならないかと考えていたけど上手くいかず、Aが広義単調増加ならクエリに関するimos法でできると気付けた。（これが公式解説の方法だった）

　700点にしては簡単で、時間があれば自力で解けたとは思うけど、Cの後こっちを解いていれば解けたという気はあまりしない。
時刻: 0 件のコメント:
ラベル:

2024年8月3日土曜日

yukicoder contest 439

　Aしか解けず。


No.2828 Remainder Game

　解説AC。

　結構長い時間かけて考えても分からず、解説を見たら、誤読に気付いた。A_1～A_5の値（のmultiset）を求めなくてはいけないと考えていたが、和さえ求めれば良かった。
　それなら自力で解けた気もするが、実際に考えたわけではないから分からない。

No.2829 GCD Divination

　普通の期待値DPなのに時間がかかってしまった。（答えが合わず、解説も見た）

　なお、コンテスト中に解けなかったのは、全てのNについて答えを求めないとDPが回らないと勘違いしたため。約数だけ調べれば大丈夫ですね。

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

2024年8月2日金曜日

日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

　Fまで六完。

コンテスト後のツイート

G - Last Major City

　解説AC。（解説放送も見た）

　最小シュタイナー木を履修した。分かってしまえば難しくない。Kが高々10というところから3^NのDPと気付ければ自力で思いつくことも可能だったか？


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

Educational Codeforces Round 168 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Level Up

　SortedSetをセグ木上の二分探索に直してAC。
　自分のセグ木二分探索のライブラリの書き方が変だったので、修正に時間を要したけど、どう書くのが良いのだろう？

　とりあえず、セグ木の演算が足し算で、
・sum(0, index)がある値以上になる最初のindexを返す
　というセグ木二分探索は実装した。

　一般的には何を二分探索で求めるようにすれば良いんだろう？

　



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