2023年8月29日火曜日

Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

　Eまで五完。

コンテスト後のツイート

F. Exotic Queries

　Mo’s algorithmを使うのかと思ったが、違っていてびっくりした。これっぽい、と思った解法が違っていることは少ないので。

　解説AC。

　えー、解法を理解するのも、それを平面走査に持ち込むところも非常に苦しんだ。

　a=A[i]となる隣接するindexがxとyだった（つまり、A[x]=a, A[y]=aで(x, y)にA[i]=aとなるものはない）とき、xとyの間に、aより小さいものがあれば答えが一つ増える、というのが発想の元なのは分かるが、ここまで分かってもどう定式化すれば良いかが難しい。

　その後、この問題が平面走査で解けるということを理解するのも難しかった。

　典型の組み合わせだということは分かるが、あまりコンテスト中に解けるビジョンが見えない……。

　また、PyPyだとTLEが取れず、chatGPTを利用してC++に直してACした。

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

2023年8月28日月曜日

ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）

　Eまで五完。 

コンテスト後のツイート


F - Nim

　桁DPだという情報を得てAC。

　何か数学的に上手い方法があるのではと考えてしまったが、

・xorの計算でそんなに上手い方法があることは少ない
・xorの計算なら桁ごとに考えるのが定石

　といったあたりを踏まえれば桁DPを考えるのは自然だった。
　桁DPと分かれば解法はすぐに思いついたこともあり、これを考えられなかったのは反省。なお、実装でバグを埋め込み修正にかなりの時間がかかってしまったけど、これは仕方ないかなぁ。

G - Rearranging

　この問題の解説を参考にしてAC。

　コンテスト中、この問題にはたどりつけていたので、焼きなましをしようなどと思わず真面目にフローで解こうとしていればACはできていたと思う。

　自力で思いついていないというのは身に着いていないということではあるのだけど、まずは類題に気付けるのが重要だと思っているので。
時刻: 0 件のコメント:
ラベル: ,

yukicoder contest 402

　AB二完だが、Bは乱択で通しておりひどい。線形代数の復習と思ってC以降も通したい。


No.2442 線形写像

　基底を考えれば良かった。
　1, 2, 4, 8,……の値を考えて、それと整合するかを調べれば良い。

　この解法は言われてみれば当たり前に思えるのに、全く思いつかなかったね……。

No.2443 特殊線形群の標準表現

　自力AC。
　ちゃんと問題文を読めば何も難しくない。累積積を取るだけの問題。

　ただ、決して難しい問題文ではないのだが、この量の数学的な文章を読むのは結構大変。そういう意味で数学的な能力が問われていると思う。
　特殊線形群ってなんだっけ？　などと考え出すと問題文が頭に入ってこなくなる。ちなみに今回は、逆行列が簡単に求まるように、行列式を1にしただけなんですね。


No.2444 一次変換と体積

　解説AC。

　行列式が（二次元なら）平方四辺形の面積になるということを知らなかった（か、忘れていた）。解説でもその部分の詳細に触れていなかったけれど、検索したらたくさんでてきて知らなきゃいけないことだったのか、となった。

No.2445 奇行列式

　検索したら転倒数の偶奇と偶置換/奇置換が一致すると見てAC。
　この事実（定義として採用されることもあるみたい）も忘れていたが、自然な性質なので覚えておきたい。

　公式解説の方法はよく分かっていません……。
時刻: 0 件のコメント:
ラベル:

2023年8月26日土曜日

Codeforces Round 894 (Div. 3)

　全完だと思ったが、Fがシステムテストで落ちた。

コンテスト後のツイート

F. Magic Will Save the World

　bitsetで実装したのだが、DPの添え字が一つずれていた。なんでこれでpretestをACするんだろう……。

　0桁目は「0」を表すので桁が一つずれる。
　五個目までの有無を調べたいなら、(1<<6)-1をかけなくてはいけないし、k.bit_length() -1が取れる最大個数になる。





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

2023年8月23日水曜日

Codeforces Round 892 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Maximum Monogonosity

　解説AC。
　絶対値を外すDPらしいと聞いたのに理解できず、けんちょんさんのブログを見てAC。

　分かってしまえば難しくないのだが……。
　とりあえず、絶対値を外すと聞いたのに絶対値をmaxに変える変形ができなかったのは反省。
　この問題のように、

・|A|=max(A, -A)

　を用いて絶対値を外すだけで道が開ける問題は結構ある（たとえば、この問題を思い出した）。とりあえず絶対値は外して、maxの式にして考えるくらいの気持ちで良いかもしれない。
時刻: 0 件のコメント:
ラベル: ,

2023年8月22日火曜日

Codeforces Round 893 (Div. 2)

　Cまで。


D. Trees and Segments

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

　結構難問だと思う。

・ある場所で切って、それより左で0の連続区間、右で1の連続区間を作ろう

　と考えるのが難しい。

　その後は、計算量を考えずに答えを求めると、計算量削減部分は累積maxを取るだけなので解法で迷うところはない。
　ただ、結構変数が多く処理も多いため、整理して考えるのが難しい。
時刻: 0 件のコメント:
ラベル:

2023年8月21日月曜日

キーエンスプログラミングコンテスト2023夏（AtCoder Beginner Contest 315）

　Fまで六完。

コンテスト後のツイート

G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

　自力AC。コンテスト中考えていた方針であっていた。

　拡張ユークリッドの互除法で各iについてB*j+C*k=X-A*iとなる(j, k)を一組求めた後は、j, kの増減がそれぞれいくつになるか考え、j, kが1～Nの範囲にあるという条件を丁寧に考えるだけである。
　そう思っても実際に実装するのは非常に大変だった。こういうのは紙に書いてからやった方が良いのかなぁ（普段はpaintでお絵描きしています）。ただ、計算が必要なわけでもないし、紙に書くほどのものでもない気もするんだよね。
時刻: 0 件のコメント:
ラベル:

2023年8月13日日曜日

AtCoder Beginner Contest 314

　Fまで六完。

コンテスト後のツイート


G - Amulets

　解説放送を見てAC。

　コンテスト中に、i番目までのモンスターまで倒すことを考えるなら、アミュレットは各タイプに関する攻撃力の和が大きいものから選べば良いことは分かっていた。なので、各Kに対してNを二分探索するTLE解法は思いついていた。

　そこまでいけば、後は差分計算するしかないはずなのだが、なぜ思いつかなかったのか。Kそれぞれの場合について求めるというのも差分計算を示唆する書き方である。

　Kではなく、モンスターの数で差分計算するという部分にちょっとした発想は必要だけど、（分かってしまえば）そこまで難しい発想とは思えないのだけど……。

　なお、実装にも苦労した。

　こうやってsortedcontainersを使ったので、手元でもsortedcontainersを使えるようにした。

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

2023年8月12日土曜日

yukicoder contest 401

　Dまで四完。


No.2411 Reverse Directions

　解説AC。

　考察要素より実装要素の方が難しい問題なのに、考察もできていなかったことを反省。

　どこかで行ったり来たりして時間をつぶすのだろうなぁ、とは思ったのに、反転する部分でそうするのが最適だと分からなかった。

　それが分かったなら、時間をつぶせる場所まで行けるか？　そこで時間をつぶせるか？　を調べれば良いが、実際に条件を書こうとすると結構複雑で、解説を読んだ後なのにWAを出してしまった。

No.2412 YOU Grow Bigger!

　タグの「全探索」を見て解法が分かった。
　何を全探索するのだろう、と思ったら答えが2以下になると気付けた。

　ただ、実装したらWAが出て、問題文を読み直したら、上下左右だけでなく斜めも動けることに気付いた。

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

2023年8月9日水曜日

Codeforces Round 891 (Div. 3)

　全完。Eでやや苦労した以外は順調だったと思うのだけど、それほど良い順位じゃないのは、うーん。

コンテスト後のツイート

　EとFでdictやCounterを使いたくなり、Hack対策をするのが面倒くさかった。
時刻: 0 件のコメント:
ラベル:

2023年8月7日月曜日

Codeforces Round 890 (Div. 2) supported by Constructor Institute

　A, B, E1の三完。Cが解けなかった！

コンテスト後のツイート

C. To Become Max

　解説AC。

　最初、二乗が通らない制約だと勘違いしていて、途中で二乗が通ると気付き、足す区間[l, r]の全探索を考えていた。
　が、これは筋が悪い。累積和との差分を使ったりすればコストが求まる気がしていたが、途中で膨らんだりした部分があるとコスト計算が正しくなくなる。このことにコンテスト中は気付いていなかった。

　あるindexをmまで上げるのに必要なコストは？　と考えて、このmを二分探索で解くのが正しい解法だった。これもそれぞれO(n)かかるので、二乗＋二分探索のlogで解ける。
時刻: 0 件のコメント:
ラベル:

2023年8月5日土曜日

yukicoder contest 400

　Dまで四完。

コンテスト後のツイート

No.2403 "Eight" Bridges of Königsberg

　解説AC。

　（入次数）-（出次数）が影響するのは分かったが、連結成分数がどう関わってくるのか分からなかった。

　これ、分からなかった原因は、上手い例を構築できなかったせいだとおもう。

　極端な例を作ろうとして、入次数が出次数よりとても多い（または少ない）グラフばかりを想像して、入次数と出次数が同じグラフを考えなかったのがまずい。
　イコールというのも極端な場合ですね。これを考えなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

2023年8月4日金曜日

Codeforces Round 881 (Div. 3)

　Eまで五完。


F1. Omsk Metro (simple version)

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

　実装はしなかったけど、当時F1の解法は分かっていた気がして、それを思い出すために見たつもりだったのだけど、こういう思考をした覚えがないから間違えていたのかもしれない。

　どちらかというとF2のために見て、解法は理解したのだけど、F2はPyPyだと通らなそうなので一旦放置します。
時刻: 0 件のコメント:
ラベル:

2023年8月3日木曜日

Educational Codeforces Round 152 (Rated for Div. 2)

　Dまで。

コンテスト後のツイート

E. Max to the Right of Min


　まとめると、

・(l, r)のlを固定
・lを固定したとき、l以降の累積max、累積minを取っていれば、rから左へ見ていったとき累積maxのindexが累積minのindexより先に現れたらその(l, r)が条件を満たす。
・累積maxや累積minの差分更新はstackを使ってできる。

　あとは二分探索を使って実装した。（こたつがめさんは遅延セグ木といっていたけど、二分探索の方が自分には分かりやすかったので）


　考える方針としては、lを固定するか、最小値を固定するか、くらいしかなさそうなので、lを固定することは考えたはずなのだけど、累積maxや累積minさえ分かれば良いということにも気付いていなかった。
　それは、ちゃんと図を描いて考えましょう、くらいしか言えなそう。どういうrが条件を満たすのかよく図を見て考えるしかなさそうですね。
時刻: 0 件のコメント:
ラベル:

2023年8月2日水曜日

Codeforces Round 889 (Div. 1)

　A1とCの二完。

コンテスト後のツイート

B. Earn or Unlock

　bitsetを使うと解けるらしいという情報を得てAC。

・問題が部分和問題に似ているので、DPするしかなさそう。
・（コンテスト中は）PyPyによるACがなく、C++でも実行時間が長いものが多い

　ということから、コンテスト中もbitsetの利用は疑ったはずなのだが、良い方法が思いつかなかった。


　実際は、部分和問題のときと同じ要領でDPテーブルを持てば解ける。
　DP[i]=1で、ちょうどindex iまで使える状態、ということを表すとすると、

・初期状態はDP[0]=1、他は0
・DP[i]=1のとき、iまでの累積和-iが答えの候補。
・DP[i]=1のとき、index i以降で1となっているものについて、DP[i+A[i]]=1と遷移させれば良い。これは、DP>>=i, DP|=(DP<<A[i]), DP<<=iのように表せる。

　となり、解ける。

　なお、現在はPyPyでのACもあるが、bitsetを書くのが簡単そうだったので久しぶりにC++を使ってみたら、昔ほど書くのに抵抗ない気がした。VSCODEを使ったら、いつのまにかボタン一つで実行できるようになっていたのも嬉しい（前はできなかったのに、なぜ？）。


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

2023年8月1日火曜日

AtCoder Grand Contest 063

　AB二完。

コンテスト後のツイート

C - Add Mod Operations

　解説AC。

・差に注目すべき。各差が一致するように移していけば良さそう
・大きい数個を小さい方に移せる

　ということには気付いていたのに、最大値一個を0にすることで差を調整していくことができると気付いていなかった。
　random解を生成してしまったせいもあるのかな……。ソートしてから考えることができるとは気付いていたので、せめてソートした後でrandomを試すべきだったかもしれない。

　なお、引っ掛かったというツイートをいくつか見ていたにもかかわらず、x<yを満たさない出力をしてWAを出したのは反省。

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