2023年11月25日土曜日

yukicoder contest 413

 　A一完。Bでハマってしまった。


No.2542 Yokan for Two

　自力AC。この後のCodeforcesをやっている途中で気付いた。
　コンテスト中は、制約からDPだと思うも、最後に切った位置とかもたなくてはダメだから解けない……などと悩んでいた。

　最初と最後どちらに使うかを決めれば、後は自由に決められる。なので、普通にDPできる。
　思いつかなかったのは悔しいが、ARCのAとかで出てもおかしくない問題だと思うので、ratedじゃなくてここでハマって良かったと思うことにしよう。

No.2543 Many Meetings

　自力ACはしたが実装に大いに苦労した。

　区間スケジューリングは考えたのだが、あるミーティングの次のミーティングを選ぶ部分を平面走査的に考えたのが苦労した原因か。
　そこでdictを持ち出したりしたため、後のダブリング部分の実装も面倒になってしまった。

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

2023年11月24日金曜日

AtCoder Regular Contest 167

　二完遅解きで青落ち。
　Bで、多倍長を利用してそのまま計算しても通ったという話を聞き、そうしていれば青に落ちることはなかったのでは、とは思うものの、それで通ると判断できなかったのも実力ですね。

コンテスト後のツイート

C - MST on Line++

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

　難しい。
　各辺のコストが何回ずつ使われているか？　を計算しようという方針自体は最初に思いつくものだが、どうやって計算すれば良いかが難しい。

　最初のとっかかりは、「一回最小全域木を作るとき、各コストは高々二回しか使われない」というところだろう。これに気付けば、0～2回それぞれの回数使われるときのpermutationの個数を考えようという方針が湧く。
　しかし、これを思い付いた後も各条件を見つけるのが大変だし、その後詰めるのも難しかった。
時刻: 0 件のコメント:
ラベル:

2023年11月21日火曜日

ALGO ARTIS プログラミングコンテスト2023 秋 （AtCoder Regular Contest 168）

　Bまで二完。Cは方針はあっていたので悔しいが、こういうのを詰めるの時間がかかってしまうんだよなぁ。

コンテスト後のツイート

C - Swap Characters

　自力AC。コンテスト中に書いていたコードをもう一度眺めてみたらどこを修正すれば良いか分かった。

　まず、A、B、Cの個数だけ見れば良いことは分かって、その上で、

・"A"を何個交換するか決める（aとする）。さらに、"A"と交換する"B"の個数を決める（bとする）。このとき、"A"と"C"の交換する個数はa-b個。

　これで"A"と何かを交換するのは終了。

・元々"A"があった位置にある"B"、”C"内で交換する必要はない（どの位置と交換するか選べるので）。ただ、元々"A"があった位置にある"B"や"C"の個数を増減させたいことはあるので、何個増減させるか決める。

・あとは、今までで交換していない"B"と"C"の交換を考えればOK（他のものについては、交換した後の場所で自由に動かせる）。それらを何個交換するか決める。

　この手順で探索して、各ステップで「何個ある中から何個選ぶのか？」を二項係数で書いた掛け算していく。それだけといえばそれだけなのだが、手順が複雑だと時間がかかってしまう。

D - Maximize Update

　解説放送を見てAC。

　コンテスト中、区間DPか？　とは少し考えたけど、具体的にどうやれば良いかは全く分かっていなかった。言われればなるほど、という感じではあるけど、判定問題もそう簡単に解けた気はしないので、Cに集中して正解か。





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

2023年11月12日日曜日

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)

　Fまで六完。Gも解けなくてはいけない問題でした。

コンテスト後のツイート

G - Cut and Reorder

　解法ツイートを見てAC。

　bit DPだとは思ったが、どういう遷移なのかパッと分からず時間を浪費してしまった。Aの番号が小さい方から使っていくという、自然な遷移を考えれば良かったのだが。

　一番の難所であるはずの、メモリの制約が特殊だというのも気付いていなかった。適切なbit DPの遷移を思い付いていれば、メモリを節約するDPを思い付くのも難しくはない……とは思うものの、コンテスト中にこれができたかは分からない。

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

2023年11月11日土曜日

yukicoder contest 412

　Bまで二完。


No.2535 多重同値

　自力AC。

　コンテスト中、上手い式変形があるのか？　と考えて分からないまま眠ってしまい、起きたらDP(メモ化再帰)でいけると気付いた。眠いとき、簡単なことでも思いつかないのは仕方ないですね。
　ただ、その後の実装で添え字など間違えて苦労したのは良くない。

　そして、解説を読むと、式変形でも解けると書いてありました……。

No.2536 同値性と充足可能性

　自力AC。

　Union-findでつないだ後、二部グラフの判定をやればOK。
　問題内容を正しく理解できればあとは典型だけど、結構面倒くさいね。

No.2537 多重含意

　自力AC。

　古典命題論理で、p_1→p_2→……→p_nが（p_1⋀p_2⋀……⋀p_n-1）→p_nと同値だということを知っていれば簡単。
　簡単に解けるのならコンテスト中に解けよ、とは自分でも思ってしまうが、問題文を読んでなかったからねぇ。
時刻: 0 件のコメント:
ラベル:

2023年11月6日月曜日

トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）

　56位。短期ヒューリスティックとしては悪くない順位なのだけど、もっと上にいけたはずなので悔しい。

コンテスト後のツイート

　本当に上位の解法は、「各山ごとにソートする」だったようだ。これは全く頭に上らなかったわけではないけど、あまり検討しなかったから仕方ない。

　自分の方針でももっと上位にいけた、というのが悔しい。

　まず、RUSTに直すところ。
　エラーメッセージもないのに、実行しても何の出力も返ってこないので不思議に思っていたのだが、こんなミスをしていた。

　いやー。くだらないミスなんだけど、意外と気付きにくいか？　どうしたら気付けたのかなぁ。


　ただ、本質はもう一つの方です。

　ツイートの「焼きなまし」における遷移は、「x以上を山yに移す」を「x以上を別のランダムな山rに移す」に変更するというのだけ行っている。その後、スコア計算を愚直に行い、改善されていたら採用、もしくは、焼きなましの条件式を満たしていたら採用、としている。

　その条件式が間違っていた。

　なぜこんなミスを……。

　思い返すと、まずPythonで山登りを書いて、焼きなましに直す際、RUSTに直そうかな、と思ってちょっとだけ書き、「いや、もし間に合わなかったら嫌だからPythonのままで改善するか試そう」と思ってPythonでも焼きなましを書いたんだよね。

　そのとき、RUSTの焼きなましの式を見ながら書いたから、コピペでなくちょっと自分で直す必要が生じて、それで間違えたのだろう。

　その後、そのPythonの式を見てRUSTに直したから、間違いがそのまま残ってしまった、と。


　とはいえ、焼きなましの意味を理解していればこんなミスはしないはずですよねー。
時刻: 0 件のコメント:
ラベル: ,

2023年11月4日土曜日

yukicoder contest 411 オムニバスコンテスト

　Dまで四完。


No.2529 Treasure Hunter

　自力AC。

　各行にある宝の個数を決めれば、次の行に宝を0/1/2個おくそれぞれの配置の個数が決まる、という大胆予想をして実装したら当たっていた。

　コンテスト中も一度こうじゃないか？　と考えたのだけど、違う気がして再度別の方針を考えてしまった。実装が簡単なので、ratedコンテストならとりあえず実装してACはできていたと思う……。

　一個以下ならこの予想は当たり前なのだけど、二個のときが分からなかった。
　公式解説を見ると、立式してみれば証明できるみた。うーん……でもこれは予想した後でないと考えない立式＆証明なので、この予想を思い付いた時点で実装してsampleが合うかを実装して調べるべきでしたね。

　一旦考えたことを、あまり検証せずに捨ててしまうのはダメ。

No.2530 Yellow Cards

　自力AC。

　もっと高速化できるみたいだけど、O(N*K)で良いのならDPで良いですね。

No.2531 Coloring Vertices on Namori

　自力AC。

　閉路の部分はDPをし、他はK-1をかければOK。これはすんなり解けた。

No.2532 Want Play More

　自力AC。珍しく再帰で実装した。

　全問通してみると、一番難しかったのはE問題だった（writerの名前を見たら予想できたはず……）ようで、全完するチャンスが十分あった回だったのですね。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)