2024年9月9日月曜日

トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）

　Eまで五完の上、ペナルティをたくさん出してまずい。

コンテスト後のツイート

F - Cake Division

　解説AC。

　二分探索するのは分かるが、全点から試さなくてはいけなそうで、どうすれば良いか分からなかった。コンテスト中はそこを高速化することは思いつかず、全部試さなくてもいくつか点を試せば良いのかなぁ、というのを提出してWA。
　ダブリングで高速化できるのはなるほど、でした。

　あと、コンテスト中は、全点を試す→二分探索の順番で考えていたことも思いつかなかった原因かも。順番を変え、二分探索→全点を試すで考えるのが重要だった。

　結構難しいが、以前、類題を解いたことがあったことを考えると解けなくてはいけない問題だった。


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

2024年9月8日日曜日

yukicoder contest 444

　Aを解いた後、Bを読んでいたら目が痛くなって撤退。


No.2871 Universal Serial Bus

　解説AC。

　コンテスト後、解こうとしたらWAを量産してしまった。
　二つ罠があった。

・全ての場合に確率が0のとき、期待値は無限になる。

　期待値の定義を考えれば当たり前で、これに気付かないのはまずい。

・「ケーブルを 180度回転させて上下ひっくり返した状態」は左右も反転する！！

　これ。
　testcaseを読んだり解説を読んでもしばらく気付かなかった。コンテスト中ACするのは難しかったのでは。

No.2872 Depth of the Parentheses

　自力AC。
　二次元DPで計算量はKの三乗にはなった。

　evilケースどうやるの？

No.2873 Kendall's Tau

　自力AC。
　「ケンドールの順位相関係数」は初耳でした。

　どういうときに使うのかな～と思ったら、順位の相関を計ると知り納得。（名前が「順位相関係数」だから当たり前なのだけど、定義だけ読んだら分からなかった）
時刻: 0 件のコメント:
ラベル:

2024年9月7日土曜日

yukicoder contest 443

　ABを解いた後、AHCの最中ということもあって疲労により撤退。


No.2864 String of yuusaan

　解法ツイートを見てAC。

　パッと問題を見たとき、周期性があるとは思わなかった。色々頑張れば（周期性がなくても）解けると思ったが、頑張る気力がなく撤退。
　周期性がなくても解けそうな問題だけに、実験しようという気持ちにもあまりなれないから、周期性があると気付くのは難しい気がするのだけど……疲れていてちゃんと考察できなかったからなのかなぁ。

No.2865 Base 10 Subsets 2

　自力AC。
　これは苦労せず解けました。

No.2866 yuusaan's Knapsack

　自力AC。

　やり方は割合すぐに分かったのだが、バグってしまいACまで時間がかかった。「Pythonのlistは参照の値渡しであること」が原因でこれ自体は知っているのだけど、値を渡しているつもりで間違えてしまうと、どこでミスっているか気付くのは大変ですね。

No.2867 NOT FOUND 404 Again

　自力AC。

　解法が桁DPなのは分かりやすい。最近は桁DPは下の桁からやっていたが、今回久しぶりに上の桁から実装した。
　DPの遷移で、"4"が一致しているところから、"40"が一致しているところだけでなく、"4"だけ一致しているところにもいけることに気付けず、愚直を書いて比較して気付いた。
時刻: 0 件のコメント:
ラベル:

2024年9月1日日曜日

AtCoder Beginner Contest 369

　Eまで五完。

コンテスト後のツイート

F - Gather Coins

　セグ木DPで答えを求められるのはあっていたが、復元方法が分からなかった。

　コインをソートした状態で考え、各コインが何回で取れるかという情報を持っておけば良い……というシンプルな方法だった。

G - As far as possible

　解説放送を見てAC。

　貪欲に長いpathを取っていけばいいというのは分かったが、実装が分からなかった。
　木DPでそういうpath分解ができるというのは思いつかなかった。典型のようなので身に着けておきたい。

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

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 件のコメント:
ラベル:
登録: 投稿 (Atom)