2025年1月18日土曜日

yukicoder contest 455

　Bまで。A,Bは制約の違う同じ問題なので、実質一完でした。


No.3004 ヤング図形

　自力AC。

　二項係数と階乗の数の積で表すところまでは問題ない。問題は、制約が大きいため、それを愚直に計算しては間に合わないところ。階乗たち（F[i]とする）を陽に持っては間に合わないため、どのようなF[i]を何個かければ良いか、または何個割れば良いか？　を持てば良い、というところまでは分かったが、これでもTLEだった。

　コンテスト後、冷静になれば、どのような入力でTLEするかに気付ける。

1
2 5

　を、Combi(10,8)*Combi(8,6)*Combi(6,4)*Combi(4,2)*Combi(2,0)を計算し、5!で割る、と計算しようとしていたが、これだとm（この入力だと5）が大きいとき間に合わない。

　この積が実は、10!を2=で5回割ったものだ、と気付きAC。

　うーん、コンテスト中にACできなくてはいけない問題でした。
時刻: 0 件のコメント:
ラベル:

2025年1月14日火曜日

AtCoder Regular Contest 190 (Div. 1)

　A一完。

コンテスト後のツイート

A - Inside or Outside

　ACしましたが、after contestでWAが出ました。

　ソートの仕方がまずくて、[a,b],[a,c]と、左端が同じものがあるとき、包含関係の判定がおかしかったのが原因でした。
　本番中にWAが出ていたら気付くのに非常に苦労した気がする……。運が良かった。
　

B - L Partition

　解説AC。解説放送も見ました。

　コンテスト中に考えていた再帰では間に合わなそう、ということで、何か方針転換しなくてはいけなかったのだけど、そういうとき、二項係数を考えるのは定石の一つ。考えなくてはいけない方針でした。ただ、解法ツイートなどを見てそう言われても全然思い浮かばなかったので、解くのは厳しかったかもしれない。

　また、二項係数の和を順に求めていくところも、（多分やったことはあると思うのだけど）記憶にありませんでした。

C - Basic Grid Problem with Updates 

　解説放送を見てAC。

　コンテスト中、スタートとゴールからDPして、差分計算をどうにかすれば良い……というところまでは考えていた。

　あとは、それらを用いて答えがどう表せるかが分かれば良かった。ただ、各クエリごとにmin(H, W)使って良いということにも気付いていなかったので、正解に近かったという感じではないが。

　ただ、Bよりは惜しかった気がするので、こっちに集中すべきだったかもしれない。

D - Matrix Pow Sum

　解説AC。解説放送も見ました。

　難問に思えた。実験すればある程度分かるという意見も見たけど、あまり思いつきそうにないなぁ……。

　ただ、解説放送で言及していたように、行列をグラフの経路数と見て行列の累乗をn歩進むときの行き方と捉える（たとえば、ここが参考になる）という考え方は身に着けておきたい。
　特に、「隣接行列をn乗してできる行列の各要素は、その行番号から列番号への頂点までを、そのグラフの辺をちょうどn回使うルートの総数」である。
時刻: 0 件のコメント:
ラベル:

2025年1月12日日曜日

HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)

　Eまで五完。

コンテスト後のツイート

F - Dangerous Sugoroku

　コンテスト中の方針でACしたが、実装に非常に苦労した。というか、自力じゃデバッグできず、ACしているコードとランダムテストで比較した……。

　区間で管理する方針が良くなかったのだろう。
　どこへいけるかをlistで持った方が実装しやすかったようだ。

G - Simultaneous Kagamimochi 2

　Eの正しい解法を理解し、セグ木を使うと知れば後は難しくなかった（添え字で少し苦労したけど）。

　この問題がどうこうというより、Eで間違った考察をしていたのが敗因。


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

2025年1月9日木曜日

Hello 2025

　Cまで三完。

コンテスト後のツイート

D. Gifts Order

　けんちょんさんの記事を参考にAC。

　セグ木を使うのは第一候補だったのにこれを思いつかなかったのは良くない。可換性が成り立たないとセグ木が使えそうという判断が鈍ってしまうようだ。気を付けよう。

E2. Another Exercise on Graphs (hard version)

　こたつがめさんの放送の振り返りを見てAC。

　ワーシャルフロイド法で、一辺を変更するときは辺の二乗の計算量でできることは覚えておきたい。
　妙に制約が厳しい気がするけど、クエリ問題だから仕方ないのかな。（と思ったら、公式解説の方法はもっと速いらしい）

G. Secret Message

　証明は難しいが、「十字のマスのうち一マスを塗れば良さそう」というところから発想することは可能だったか。
　ただ、制約が厳しく、二次元配列を一次元に直さないと通らなかったので、コンテスト中にACするのは厳しかったかもしれない。
時刻: 0 件のコメント:
ラベル: , ,

2025年1月8日水曜日

AtCoder Beginner Contest 387（Promotion of AtCoderJobs）

　Cを飛ばしてFまで五完。

コンテスト後のツイート


C - Snake Numbers

　桁DP（もしくは、それに近い）方法でやっていた人が多そうだったけど、コンテスト中に考えた場合分けの方針のままでAC。
　ただし、場合分けに苦戦し、かなりの時間がかかった。解けることは分かったけれど、桁DPで書いた方が混乱は少なそうです。

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

2024年12月31日火曜日

AtCoder Beginner Contest 386

　Eまで。

コンテスト後のツイート


F - Operate K

　最長共通部分列のDPと同じようにDPすればACできた。コンテスト中はなぜもっと捻った方法を取ろうとしてしまったのか……。（Sのindex iまで使い、K回まで操作を行ったとき、Tをどこから操作できるか？　と考えていた）
　大いに反省。

　ただ、面倒がってDPをCounterで書いたらTLEし、RUSTのHashMapでもTLEだった（TLEが増えた）。こういうの、ちゃんとリストで書かないといけないんですね。


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

Educational Codeforces Round 173 (Rated for Div. 2)

　Dまで四完。


E. Matrix Transformation

　解説は理解したが、貪欲でAC。

　公式解説の方法は、「ある操作の後に別の操作がある」という条件がいくつも現れるので、グラフにし、トポロジカルソートしてループがないか探すというもの。

　しかし、貪欲に、行と列の操作を交互に31回行って一致すればYes、としてACしているコードがあった。
　確かに、上記のような条件は、min(行の数, 列の数)しか現れないので、n×m≤1000 という制約があるため、これで良い。

　コンテスト中は貪欲方針を書いて、二回しか回さずにWAを出していた。貪欲でいけるかも？　と考えるのは良いけど、正当性も全く思いついていないのでダメですね。
　また、bitずつやらなくても実装できるところを、bitずつやって定数倍が遅い実装になっていたのもまずい。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)