2022年1月12日水曜日

Codeforces Round #764 (Div. 3)

　pretest全完。全部通ると良いなぁ。→通っていました。

コンテスト後のツイート

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

2022年1月10日月曜日

トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)

　AB二完という過去最低（灰パフォ相当は初めて！）の成績。


C - Final Day

　今までの合計点でソートして大きい方からK番目の値が基準になる。今までの点数+300がそれ以上かで判定。
　基準値を得るところで、ソートしたものではなく元の数列を見ていたためWA。そして、コンテストが終わるまでそれに気付けなかった。多分、質問に「"in the top K" means……」という文章があったため、「上位 K 位以内」の解釈がおかしいのかな……と疑っていたためだと思う。
　自分のコードも何度も見直したつもりだったが、誤読の可能性の方が高いと思っていたため見直しが浅くなっていたのかもしれない。

D - Linear Probing

　最初、左右を管理するリストを付けばできると思ったが、それだと1ケースTLE。(1, x)というクエリが繰り返しくるとき、左右の管理だけでは難しい。
　なので、Union-findを使えば良いと思ったが、上手い実装を思い付けなかった。

　冷静になれば、xとx+1をUnioinするとき、x+1側の最大値を得る配列を用意しておけば簡単に実装できる。

E - Integer Sequence Fair

　問題を開いてすぐ、この記事を見に行った。
　これで良いのだが、pow(a, b)がa=b=0のとき1になるというのに注意せねばならなかった。このコーナーケースは盲点でした。
　今回、コンテスト中冷静じゃなかったけど、Dまで普通に解けていたとしても気付いたかどうか……。

F - Stamp Game

　解説放送を見てAC。
　実装の簡単さのため、縦横ともSparse tableを使った。

　二次元Sparse tableの復習もしようと思ったけど、横向きにSparse tableを作っておき、縦方向へは、それぞれのnodeについてSparse tableを構成、というので良いのかな。（そう考えればそんなに混乱しなそう？）

G - Digits on Grid

　解説放送を見てAC。
　DPのキーとして何を使うかが重要だが、「同じ数字を取りうるものの集合」を使えば良いということですね。

　ところで、この問題が類題な気がする。前に解説を読んでも理解できなかったのだけど、今なら解けるはず？

　ACできたらその旨を追記します。　→　ACできました！　なお、行列累乗で扱っている行列の行数が解説のものと1違ったので、少し違うことしているみたいです。

H - Histogram

　解説放送を見てAC。

・まずAでソート
・愚直なDPを書く
・式の形を見ると累積和が使えそう
・累積和を取ってまとめるとConvex Hull Trickが使える

　という流れ。難しいけれど、典型的な処理を繰り返せば解けるという意味で、解けなくてはいけない問題だと思う。

　式を見ても累積和に気付けなかったこと、Convex Hull Trick (CHT)の具体的な処理を忘れていたことは反省。ただ、Convex Hull Trickの書き方は結構使い回せるようなので、使うと分かったら以前の提出を参考にするようにしたい。
　今回の提出やDPまとめコンテストZの提出で、最小値の場合を書いている。
　ライブラリ化するのも有りか。
時刻: 0 件のコメント:
ラベル: ,

2022年1月9日日曜日

AtCoder Beginner Contest 234

　Gを除く七完。Hは嘘かと思いつつ投げたが、実際は正しい解法だったよう。

コンテスト後のツイート

G - Divide a Sequence

　解説AC。
　二乗のDPにはでき、式を書いてみると、maxとminは分割できることには気付けた。あとはなんらかの方法で高速化するのだろう、とは思ったが、stackを使った高速化は思いつかなかった。

　もらうDPで書いたとき、DP[i]の更新で必要なのは、各jについて、j～iについての最大値とDP[j]の値。
　この「j～iについての最大値」という配列は、jについて単調減少になっているため、そこに一つ要素xを付け加えたとき、変更されるのは後ろいくつかがxになる、というだけである。

　なので、[最大値, 最大値*DP[i]]というのをstackに突っ込んで置き、そこに新たに加わる要素xがstackの最後の要素より小さければただ付け加える。大きければ、最大値がxより小さいものたちについてmergeし、差分計算をしていけば良い。

　stackによる高速化は定石の一つなので、思いつかなかったのは反省。

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

2022年1月8日土曜日

yukicoder contest 326

　Dまで四完。

コンテスト後のツイート

No.1803 Remainder of Sum

　解説AC。
　初手で実験し、それを元に、MをNとの大小で場合分けするという方針はあっていたのだが、その後が詰められなかった。
　$M\leq N$のときの立式で間違っていたのは良くない。
　また、最後1とつないで辻褄合わせをするんだろうとは思ったのに、なぜかそれは大きい数字で行う気がして、2～$M-N$という小さい方で行うと思わなかった。

　最小全域木を作る、という気持ちになれなかったのが良くなかった気もするので、アルゴリズムの手法をちゃんと抑えるのが大事かね。

No.1804 Intersection of LIS

　解説AC（あまり考えずに解説を見た）。

　なるほど。
　共通部分を考えるとき、最大と最小をまず考える（今回は、辞書順最大・辞書順最小）のは定番ですね。
　一度それを考えてみるのは大切だし、証明できなくてもこれを投げてみよう、くらいのことはしても良かったか。
時刻: 0 件のコメント:

2022年1月7日金曜日

パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)

　Fまで六完。

コンテスト後のツイート

G - Balls in Boxes

　解説放送を見てAC。

　この問題（ブログ内の記事）の類題だったが、身に着いていなかった。配り方に帰着するというのは覚えていたのだけど、実際にどうやるのかが難しい。

　他にも、これやこれが類題だった。

　積の和を求めるのはなかなか難しくて、配り方へ帰着するしかない（ことが多い）、ということは頭に入っているのだけど、実際に解こうとすると頭がこんがらがってしまう。
　今納得できているけど、次回出たとき解けるかはあまり自信ないなぁ……。

H - Minimum Coloring

　解説放送を見てAC。

　フローを使いそう、とはコンテスト中も分かったが、その後のグラフの構築は大変。「容量下限付き最小費用流」のグラフの構築の仕方は勉強になった。とはいえ、しっくりきたかというとそこまでいっていないのが難しい……。一応納得したつもりではあるのだが。
　snukeさんのブログ記事にも大体同じ内容があるので、分からなくなったときはここも参考にしたい。

　なお、自分が元々持っていた最小費用流ライブラリだとTLEしてしまったので、少しだけ高速化した（それでもギリギリだった）。
　他の方のライブラリと同じことをしているつもりなのだけど、まだ若干遅いのは何故だろう。
時刻: 0 件のコメント:
ラベル: , ,

2022年1月5日水曜日

AtCoder Beginner Contest 233

　Fまで六完。

コンテスト後のツイート

G - Strongest Takahashi

　解説放送を見てAC。
　全然DPを考えなかった。「行か列かで分割して良い」ということに気付くかどうか、というどちらかというと発想の問題ですね。

　Codeforcesで既出で、以前コンテストに参加していたものの未ACの問題でした。今回ACできて良かった。

Ex - Manhattan Christmas Tree

　解説放送を見てAC。並列二分探索に関するアルメリアさんの解説も参考にしました。
　「並列二分探索」というのは、何か自分の知らない特別な手法なのかと思っていたのですが、並列に二分探索するだけでしたね。怯える必要なかった。

　ただ、放送を見てしばらく、なんで並列でできるのか分からず困りました。分かってしまえば当たり前なんですが。
　最初理解できなかったのは、「答を決め打って二分探索」、という意識があったせいかな……。今回のような問題だと、データ構造を使い回して並列化できるのですね。

　各クエリごとに二分探索はできるけど、あまり賢い方法はなさそうなときは、並列二分探索を疑おう。
時刻: 0 件のコメント:
ラベル: ,

2022年1月4日火曜日

M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)

　Fまで六完。

コンテスト後のツイート

G - Modulo Shortest Path

　解説放送を見てAC。

　snukeさんも解説中に言っていたけど、私がコンテスト中に考えたのもフローだった。「フローが上手くいかない」と気付かないと厳しい。、そう気付けるようになるためには、もっとフローの練習を積まないといけないか。

　上手くグラフを作ればダイクストラでいけそう、と気付くためには、制約に注目するのが重要。「$A_i, B_i < M$」の制約の意味（和が2*Mを超えない！）に気付けば思いついてもおかしくないかな、と思う。
　

H - King's Tour

　一応自力AC。

　コンテスト中に考えたことは、
・(a, b)を通らないように周囲を一列、もしくは一行ずつ埋めていく。
・(a, b)からマンハッタン距離が遠いところを優先して通るように埋めていく。

　の二つ。

　一番目、二番目の片方ずつだと半分程度WAになったが、二つを組み合わせた（一個目で作った答えの途中から二番目を使う）らWAが二個まで減った。

　さらに、二番目で使っていた評価値「マンハッタン距離」を、max$($abs$(a-x),  $abs$(b-y))^2+$マンハッタン距離にしてみたらAC。

　Hackケースがあるかもしれないけど、それほど良い方法もない問題らしいので、まあ。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)