2022年10月30日日曜日

トヨタ自動車 プログラミングコンテスト2022（AtCoder Heuristic Contest 015）

　水パフォは出たものの、AHCでレートを上げられなかった。

コンテストへのリンク
コンテスト後のツイート

・一手先のコマをどこに置くか？　と考えて盤面を傾けるのが本質だった。言われてみれば確かに。
・モンテカルロ法を使うのは悪くないらしい。使い方が悪かった模様。
時刻: 0 件のコメント:
ラベル:

2022年10月29日土曜日

yukicoder contest 366

　Cまで三完。Dを思いつかず終了。


No.2112 All 2x2 are Equal

　自力AC。

　市松模様に塗り分ける。(i+j)%2==0であるマスを左上から順番に塗り、その後、(i+j)%2==1のマスを右下から逆に塗っていけばOK。

　お絵描きしていたら偶然思いついたが、偶然としかいえない。

No.2113 Distance Sequence 1.5

　最大値に着目すれば良いというツイートを見てAC。

　ゲームの問題になっているが、差がK以上の組があるとまずいのはほぼ明らかなので、数え上げの問題。
　どう数えるかで困っていたら、最大値に着目というツイートが目に入ったため解くことができた。
時刻: 0 件のコメント:
ラベル:

2022年10月28日金曜日

AtCoder Regular Contest 146

　AB二完で終了。

コンテスト後のツイート

C - Even XOR

　解説AC。

　コンテスト終盤、Sの要素で場合分けする、という方針を思い付き、N=4までは実験コードと結果が一致した。そのとき考えていたのは、

・相異なる3要素がSに入っていれば、それ以外の要素一つが禁止になる

　というものだった。偶然N=4までは一致したが、これは間違い。

　線形独立性を考えるのがポイントで、正しくは、

・x個の要素がSに入ったら、x個のうち一つを0に平行移動させ、それと線形従属な$2^{(x-1)}$個が禁止になる

　だった。

　コンテスト中書いていたコードを少し変えれば通った……という意味では惜しかったが、線形独立性は全く思いついていなかったので本質が分かっていなかったという意味では惜しくなかった。

D - >=<

　珍しく自力AC。

　できるだけ小さくしたいので、ANS=[1]*Nから始めて、条件p, x, q, yについて、ANS[p]>=x となる部分があればANS[q]=max(ANS[q], y)もしくはANS[q]=max(ANS[q], y+1)と、条件を満たす最小値へ更新していく。

　今更だけど、CでなくDへ行くべきでしたね。題意を理解するのにちょっと時間がかかる問題なので避けてしまったけど、ちゃんと検討すべきだったかなぁ。
時刻: 0 件のコメント:
ラベル:

2022年10月27日木曜日

AtCoder Regular Contest 148

　Dまで四完。このコンテスト終了時、AtCoderのAC数がちょうど3000になった。

コンテスト後のツイート

E - ≥ K

　解説放送を見てAC。

　数列Aを小さい順、もしくは大きい順に見て、DPか何かで計算……みたいな方針を考えたが、これだと上手くいかない。

　今回は、

・大きい方か、小さい方か、どちらかなら並べ方が一通りに定まる

　というもの。

　上から見れば/下から見ればOKというものではないので気付きにくく、違う方針を検討してしたくなるけれど、こういう風に「上手い順番で見れば計算できる」こともあると押さえておこう。
　
時刻: 0 件のコメント:
ラベル:

2022年10月24日月曜日

Codeforces Round #829 (Div. 1)

　Cまで三完。Dは解法はあっていたけど制限時間が厳しく通せなかった。

コンテスト後のツイート

D. The Beach

　自力AC。
　ツイートした通りで、空きマスから適切にダイクストラをすれば良い。

　コンテスト後、Rustで通したが、書くのに30分以上かかっている。もう少し速く書けるようになりたいね。PyPyで通している人はいるけど、ちょっと技巧的な気もするし、それでもギリギリなので、他言語への書き換えが素早くできると良かった。

　このコンテストは、based on Moscow Team Olympiadということなので、PyPyじゃ制限が厳しい問題が出題される可能性は高いと思っていた。この問題は制約を見ればPyPyでは厳しそうと分かる。Rustで時間内に書き切る自信があればRustで書こうとしたはずなので、もうちょっと慣れて、速く書けるようになりたい。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 365

　調子が良くなかったとはいえ、一問も解けずに終わった。復習しましょう。


No.2103 ±1s Game

　解説AC。

　（コンテスト終了後）解説とほぼ同じことも考えたのだが、それで良いのか確信が持てずに愚直を書いたりしていた。

No.2104 Multiply-Add

　解法は自力で分かった。

　ユークリッドの互除法の要領で(a, b)→(x, 0)に、(c, d)→(y, 0)にしたとき、xとyが一致していればOK。(a, b)→(x, 0)→(c, d)のように変形すれば良い。

　ただ、最初から片方が0のときの場合を考えておらずWAを出してしまった（テストケースを見て気付いた）。気を付けねば。
時刻: 0 件のコメント:
ラベル:

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

　Eまで五完。

コンテスト後のツイート

F - Fishing

　一応、自力AC。

　イベントソートという方針は合っていたが、同時に出入りがあったり、0秒ちょうどに出ていくものを忘れていたりしていた。

　また、PyPyで通すのは結構厳しく、FractionをソートしたりしてはTLEが取れない。出入りする時間にある程度大きな整数をかけて誤差を小さくし、tupleを一次元化してからソートしたら通った。

G - Security Camera 3

　解説放送を見てAC。

　コンテスト中、フローだと思ったし、「燃やす埋める」のスライドなどを見に行ったりしたがグラフを構築できなくて、うーん。

　ただ、この問題は、二部グラフの最小点被覆と見るのが分かりやすかったか。けんちょんさんのqiitaの内容はしっかり抑えたい。

　また、グラフ構築の際、

・何を頂点にし、何を辺にするか

　を考え、

・上手くいかなかったら逆（今まで頂点にしていたものを辺に、辺にしていたものを頂点に）も試してみる

　などをすれば解けた気もする。

　類題を解いておこうと思って、これを解いたが（一応、解説は見ないで解けたが）かなり苦戦した。フローのグラフ構築は難しい。
時刻: 0 件のコメント:
ラベル: , ,
登録: 投稿 (Atom)