2023年7月30日日曜日

ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)

　ABCDFGの六完。

コンテスト後のツイート

E - Tangency of Cuboids

　100*100*100の小立方体に分けて考えれば良いという解法ツイートを見てAC。

　コンテスト中は、ある断面で切って区間スケジューリング問題みたいに解く方針を考えていたが、それだと辺のみが共有する場合がうまく処理できなくて困ってしまった。
　こういう方針でも解けるらしいけど、どうやるんだろう……。
　


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

2023年7月29日土曜日

Codeforces Round 887 (Div. 1)

　Bまで二完。Aがすぐ分からなかったが、Bを解いた後戻って考えたら分かった。

コンテスト後のツイート

C. Ina of the Mountain

　解説AC。解法ツイートでpriority queueを使うなどと言われても分からなかったが、公式Editorialが丁寧だった。

　（A[i]=kのものはA[i]=0に前処理した上で、）

・A[i]かA[i]+kのどちらかを使うと思って良い。
・登りのときだけコストがかかると考える。そうすると、次の戦略が最適：下りはとりあえず下っておくとする。下りを後で登りに変更することを考えると、-xの下りを登りに変更した場合、k-xのコストがかかることが分かる。なので、登るとき、「今までの下りのうちのどれかを登りに変更するか、ここを登るか」これらのうちの最小値を選べばよい。（ここでpriority queueを使う）
時刻: 0 件のコメント:
ラベル:

yukicoder contest 399

　ABの二完。Cを考えているときに体調が悪くなり撤退。

No.2394 部分和乗総和

　自力AC。

　しばらく分からなかったが、形式的ベキ級数に思いを馳せたら解けた。

No.2395 区間二次変換一点取得

　自力AC。

　各indexごと独立なので、各indexについて何回クエリが適応されているかだけ見れば良い。
　問題文を理解するのがちょっと難しいけど、理解してしまえばBやCより簡単では。
時刻: 0 件のコメント:
ラベル: ,

2023年7月28日金曜日

Codeforces Round 888 (Div. 3)

　Gが解けなかった。

コンテスト後のツイート

G. Vlad and the Mountains

　並列二分探索を使わないでも解けるというツイートを見てAC。

　しばらく考えて分からなかったのが、並列二分探索で解けるということに気付いて喜んで実装したらMLEやTLEが出て、残り時間が少なかったため定数倍高速化を試したがACできなかった。

　落ち着いて考えれば、「start時点の山の高さ+e」までの高さの山を結んだときstartからgoalにたどりつけるかさえ調べればよいため、並列二分探索は必要なかった。
時刻: 0 件のコメント:
ラベル:

2023年7月23日日曜日

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

　Fまで。

コンテスト後のツイート

G - One More Grid Task

　解説AC。

　「最大長方形」のアルゴリズムを使うのかな、とはコンテスト中に考えたのに、（検索したら）最大長方形のアルゴリズムはヒストグラムの形にしか適応できないことを見て、この問題には適応できないと思ってしまった。
　「i行より上の部分だけを見る」として最大長方形のアルゴリズムを適応する発想がなかった。

　最大長方形のアルゴリズムを使うかもしれないと思ったのなら、もうちょっと使える形に変形できないか考えないと。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Round 886 (Div. 4)

　pretestは全完。あまり迷うところもなかったので、GがHackされ、FでシステムテストでTLEしていて驚いた。

コンテスト後のツイート

F. We Were Both Children

　Pythonでset（Counter）を使うとHashを衝突させられる案件でTLEしていた。
　何の気なしに、Counter(A)と書いてしまった。
　Counter(sorted(A))に直してAC。

G. The Morning Star

　これもF同様Counterのせいで落ちていた。
　ただ、sortしただけでは通らないケースが入っており、座標を1ずらしたらACした。

　CodeforcesではsetやCounterを気楽に使ってはいけないってことですね。うーむ。



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

2023年7月22日土曜日

yukicoder contest 398

　ABの二完。


No.2387 Yokan Factory

　自力AC。

　答え二分探索＋ダイクストラ。解法は分かったのに睡魔に襲われて実装できなかった。しかし、いくら眠くてもこれを実装し切れないのはですね。

No.2390 Udon Coupon (Hard)

　自力AC。

　最も効率良いものをたくさん買った後、残りをDPすれば良い……というのは、この問題などを解いていたため知っていた。
　それなのに、三分探索で良いのでは？　などと混乱してしまいWAを出したのはダメ。
時刻: 0 件のコメント:
ラベル:

2023年7月18日火曜日

freee プログラミングコンテスト2023（AtCoder Beginner Contest 310）

　Fまで六完。

コンテスト後のツイート

G - Takahashi And Pass-The-Ball Game

　解説を読んだけど、ダブリングの解法がすぐには理解できず、解説放送も参考にしてAC。

　ダブリングでいけそうということは分かっても、実装するのが難しい問題だった。
　ダブリングでさくっと求められるのは、「xさんのボールがy回の操作後どこにあるか？」だが、ダブリングの途中で二回の操作を一回にまとめていかねばならないため混乱しやすい。

　ダブリングをこういう風に使ったことがなかった気がするので、ちょっと新鮮だった。

　コンテスト中は行列累乗なんかを考えたりしていて的外れでした。

Ex - Negative Cost

　解説放送を見てAC。

・ナップザック問題で重みが大きいときどうするか？

　という問題の解法を知っていないと解くのが厳しかったと思う。
　最大効率に着目するのは直感にも合致していて、確かにそうだな、という感じ。

　この問題に帰着しようと思えたのなら、帰着する部分は思いつけなくはなさそう。


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

Codeforces Round 885 (Div. 2)

　BCDの三完。

コンテスト後のツイート

A. Vika and Her Friends

　解法ツイートを見てAC。

　市松模様に分けたとき、自分と同じ場所に来る可能性があるのは、同じ色の場所のみ。
　自分が動いた後、敵は自分の動きを見てから移動できるので、敵が同じ色の場所に一人でもいたら捕まる。

　読解がやや難しくて、最初問題を読んだときは勘違いした（一手後に捕まるかを判定するのかと思った&「敵は自分の動きを見てから移動できる」を読めていなかった）が、最後は正しく理解していたのに分からなかった。
　「敵は自分の動きを見てから移動できる」というのを正しく読めたのに解法に反映させておらず、よく分からないけど敵が二人いたらダメなのかな、などと考えていた。

　コンテスト中の立ち回りとしては、すぐに理解できなかったら飛ばすのが正解だったと思う。飛ばすのがちょっと遅かった気はするけど、まあ良いか。

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

2023年7月15日土曜日

yukicoder contest 397(群論コンテスト)

　ABDの三完。

No.2381 Gift Exchange Party

　解説AC。

　こういう問題で、iからA[i]に辺を張ったグラフを考えるのは典型。Pが素数なので、そのグラフにおけるサイクルが全て1かPになれば良い。

　コンテスト中は、Pが素数だということを読み飛ばしていた。が、このグラフすら考えていなかったのは反省。サイクルが～みたいなことをぼんやりと考えていたはずだが、何を考えていたのだろう……。

　また、実装はTester解説の方法でやったが、累積積による高速化が必要なことに気付かなかったりして手間取った。
　DPでやるのが簡単なのですね。今まで使っていない最も小さな数に注目するのが良いのか。それならPが素数じゃなくても解ける。形式的ベキ級数でも扱えるらしい。

No.2383 Naphthol

　バーンサイドの公式について、高校数学の美しい物語を参考にしながらAC。

　modを取っているのに、（*pow(4,mod-2,mod)とせず）4で割っていて答えが合わず困ったのは恥ずかしい。
　
時刻: 0 件のコメント:
ラベル: , ,

2023年7月3日月曜日

AtCoder Regular Contest 163

　AB二完。

コンテスト後のツイート

C - Harmonic Mean

　解説AC。

　部分分数分解を利用するというのを見て実装しようとしたら、全体二倍にするというのを思いつかず苦戦してしまった。

　部分分数分解を利用する方針は全く思いつかなかったので解けなくても仕方なかった……とも思うが、他の方針で（やや強引に）通している人も結構いる模様。それを見るとどうにかして通したかったという気持ちになるが、どうすれば良かったかね。

　コンテスト中は、和が1になるものx個を使って、それらをx倍したものを合併させる。もしくは、3個を2, 3, 6倍したものを合併させる……というような方針を考えていたが、Nが100～150あたりまでしか作れなかった。

D - Sum of SCC

　解説AC。

　問題を見て、主客転倒的なテクニックを使いそう、とは思ったが、グラフを二つに分けて考えるという発想はなかなか難しい。
　SCCをs0→s1→s2→……のように表してみて、この矢印をどこで区切れば良いか？　と考えれば思いつけるのかなぁ。

　また、解説通りのDPをしたつもりが答えが合わずに苦労した。

　解説の一行目の「以下の値-1に等しいです」というのは、A側が空の場合とB側が空の場合をダブルカウントしているため、ということなのですね。
　これを踏まえて、最終的な答えを求めるときも、i（解説のdp内の添え字）の範囲を[0, N)もしくは(0,N]にしなくてはいけなかった。


　が、今回の問題の解法に引っ張られて二乗のDPで解く方法しか思いつかず、oeisを使ってなんとかAC、としてしまった。
　解説（のコード）を見ると、簡単に立式できましたね……。
時刻: 0 件のコメント:
ラベル:

2023年7月1日土曜日

yukicoder contest 395

　ABの二完。


No.2366 登校

　解説AC。

　ダイクストラを使いそうなのは分かるので、どういうダイクストラを使ってどうすれば計算量を減らせるか考える問題。

　疲労度の最小値を求める問題なので、

・DP[座標][時間]=疲労度の最小値

　とするのは自然。ただ、これだと時間をどの範囲で取ればいいか分からないのだけれど、どの地点からもN+M-2歩以内で行けることから時間を絞れる、という考察が必要でした。

　こう書くと自然な考察で解けるので、解きたかったね……。

　そして、解説を読み直しながらこの文章を書いていたら、実装ミスしていたことに気付いたので、再提出＆自分のコードにChallengeにしておいた。
　時間を巻き戻すとき、昔過ぎる時間に巻き戻る遷移を禁じた実装をしていました。


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