2023年6月28日水曜日

Codeforces Round 880 (Div. 1)

　A一完のみ。

コンテスト後のツイート

B. Lottery

　こたつがめさんの実況放送を見てどうにか理解した。

　この解法に思い至れなかった要因は、当たりの位置をずらすことを考えていて、「何番目を買うとしたら当たりくじの位置はどこからどこまでか？」という考え方を全くしなかったこと。その後の考察も難しいけど、少なくともこれはどちらも考えてみるべきだった。

　PyPyだとTLEしたためRUSTに直したが、そこでも苦戦した。特に、

・RUSTのbinary_searchで、その要素が複数個入っていたときは、そのうちどのindexをわたすか分からない（多分。自分で実験した限りはそうだった）

　というのを知らなかったため原因に気付かず大変だった。今度RUSTで二分探索を使うときは気を付けよう。

C. Twin Clusters

　こたつがめさんの実況放送で理解。ただ、実装は乱択で通した。

　区間xorの値が同じになるのが二つあれば、それを使って答えが作れるのだろう……とは思っていたが、0が一つだけある場合はそれを除いて考えて良いということが分かっていなかった。そうすると、端点が同じ（[l, r]、[l2, r2]でl=l2の場合）な場合に答えが作れるということも。
　これを思い付いていれば、乱択しようと思えたかな……。

　乱択じゃない解法については、鳩ノ巣原理を利用したいという気持ちを強く持てば下半分と上半分の桁で分けようと思えるのかな、と感じた。
　ただ、この鳩ノ巣原理はかなり余裕があるからできているわけで、それなら乱択で通るよね、という気持ちになった。


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

2023年6月26日月曜日

TOYOTA Programming Contest 2023 Summer（AtCoder Heuristic Contest 021）

　最終順位319位で、予選通過はダメでした。（ツイッターで317位と書いてしまったけどまだジャッジ中だったみたい）

コンテスト後のツイート


　解法は、ツイートの通りで、

・大きい順に、経路のコスト（置きたい段との差をコスト）を求めるDPをしてコストが小さいものを採用、としました。

　ただ、これは勘違いしていたせいです。ツイートを見ていたら同じ勘違いをしていた人が何人かいたけど、

・各数字が、0,1,2,..と並べたときと同じ段にならなくてはいけない

　と勘違いしていました。それで最初言ったような解法になってしまった。


　アルゴリズムの問題でもそうだけど、誤読とか、勘違いとかを一度してしまうと修正するのは難しい。
　今回は、最初に「適当に上下で値が入れ替わっていたら交換しまくる」というのを提出しているので、それでOKだったことを振り返る余裕があれば気付けたはずなのだけども……。まあそんな余裕はなかった。


　ただ、この勘違いがなくても、上手くできたかどうか。

　今回は、「13426585点が取れる貪欲アルゴリズム」を思い付けるかどうかが鍵だったが、これで上手くいくというのはそれほど明らかじゃない気がした。
　さらに、その改善ともなると、うーん。Kiri8128さんの解説の評価関数も全く思いつかなかった。これを実装したら確かに改善したけど、自分で思いつけたかというと……。

　ただ、コンテスト中、順位表で上位に同じ点数の人がたくさんいるのは見て、「何か簡単な解法があるはず」とは気付いていたのだから、とにかく色々な貪欲を試してみるべきだった、とは思う。

・小さい数字から試す
・上の二つのうち大きい方と交換

　というの自体は両方とも考えたことはあったのだから。

　それで自分の点数より伸びるとは思わなかった（ことと、勘違いしていた）から試さなかったのだけれど、それでも実装してみて、他にどんな解法やパラメータがあるか探らなくてはいけなかったのだろう。

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

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）

　Eまで五完。

コンテスト後のツイート

F - Virus 2

　解説AC。

　（感染した日, 感染した場所からの最短距離）を持つダイクストラでやった。これだと、「l日以降でx以上の数字がXに表れる一番最近のindexはどこ？」に答える必要があったので、セグ木二分探索を使った（使わなくてもできるらしいが、よく分からず……）。

　ダイクストラすることは明らかで、どんな解法でもできそうに思えるけど、実際に実装しようとするとつまる……みたいな問題だと思う。
　多分、解説見なくてもごちゃごちゃやっていれば解けたと思うけど、素早くこなすためにはどうすれば良いのかね。

G - Approximate Equalization

　解法ツイートを見るとツイートで書いた内容で大体あってそうで、

・x+1にした個数をもってDP

　だけ持てば良かった。

　それだと次の数字が何か分からない（一意に定まらない）気がしてしまったが、累積和を取っておけば、そこまでで使ったxやx+1の個数が分かっているため、差分計算で求まり、一意に定まる。
　制約を見ても二乗DPできそうなので、ツイートした内容のところまでいけば、正しい解法に至ることはできそうなのにねぇ。うーん。

　なお、解法が分かったつもりで実装しようとしたら、再度、「やっぱり次の数字は分からないのでは？」と思ってもう一度再考してしまったし、その上、一番最後にx+1を使う場合を考え損ねてWAを出したりした。

　解けなきゃいけない問題だったと思うのに、この様はまずい……。
時刻: 0 件のコメント:
ラベル:

2023年6月24日土曜日

yukicoder contest 394

　AB二完。

コンテスト後のツイート

No.2359 A in S ?

　解説は見たけど自力（？）AC。

　コンテスト中、「X, Yの条件がなければimos法だなぁ」と思い、XとYの条件があっても、それらをまとめて計算すれば計算量が落ちるのかも？　と思ってheapqを使って（小さい(index, X)から処理するためにheapqを使った）書いたがTLE。heapqを使わずに書けそうなので、そこからlogは落とせると思ったが、計算量に自信がなかった（のと、BでRUSTに直してACしたので、この問題もRUSTに書き直そうか迷っていた）ため書き直さなかった。

　解説を見たら、それで実際計算量が落ちると書いてあったので、書き直してACしました。
時刻: 0 件のコメント:
ラベル:

2023年6月19日月曜日

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

　Fまで六完。ジャッジが詰まったためGを解けなかったけれど、時間あったら解けてたっぽい。

コンテスト後のツイート

G - Return to 1

　コンテスト中に書いたのでほぼ合っていて、コンテスト中DFSで書いたもの（1caseだけTLE）をBFSに直したら通った。
　ジャッジが詰まっていたせいもあって適当に書いてしまったけど、BFSじゃないとTLEするのは当たり前でした。
　
時刻: 0 件のコメント:
ラベル:

2023年6月17日土曜日

yukicoder contest 393

　Dまで四完。


No.2354 Poor Sight in Winter

　一応自力でAC。

　二分探索＋ダイクストラでいけるんじゃないか？　とは問題を見てすぐ思った。

　ただ、a→bのルートに明かりを配置したとき、同時に別のc→dというルートがいけるようになることがある。だから、正当性が怪しい気がして実装せず考え込んでしまった。

　コンテスト後、「とはいえ、a→bのルートに明かりをx個配置したとき同時にa→cもいけるようになったとしたら、a→cもx個でいけるようになるな」と思い、やや正当性に自信が持てなかったものの実装したら（REやTLEを経て）ACした。

　なお、解説を見ると「明らかに，同じ明かりを二度使うことは最適ではありません．同じ明かりを二度使う場合，1 回目に使用してから 2 回目に使用するまでの間を省略できるからです」と書いており、それはそうか、となった。

No.2355 Unhappy Back Dance

　自力AC。

　角度が同じものを列挙すれば良いとは思ったが、三乗かかる気がして悩んだ。
　ただ冷静になると、それほど工夫は必要なく、「一点を固定し他の全ての点に対して角度を求めたものをdictに入れておく」で二乗でいけた。

No.2356 Back Door Tour in Four Seasons

　ちらっと解説を見たけど大体自力でAC。

　扉の順番を決めれば、そう進むときの場合の数は求められる。それを使って総和を求めるという方針。
　解説ではΣ計算を使っているけれど、DPの気持ちで考えた。

・DP[扉]＝その扉に至るときの場合の数（それが夏の扉なら、どこかの春の扉→ここ、という感じ。その手前の季節の扉までの行き先を指定する）

　として、ある夏の扉を使っていく場合の数を考えたとき、春の扉たちの場合の数の和がその値になる。……ということは、春夏秋冬それぞれについて和を取って良い、ということになる。

　なお、扉の総数を求めるとき、modで割ってしまいWAを出した。ベキ乗する値にmodを取ってはダメ！
時刻: 0 件のコメント:
ラベル:

2023年6月14日水曜日

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）

 　Fまで六完。


Ex - Constrained Topological Sort

　解説放送を見てAC。

　これは自然な条件を積み重ねていけば解法へたどりつける問題だった。粘れば自力でも解けたかなぁ……。
時刻: 0 件のコメント:
ラベル:

Educational Codeforces Round 150 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Fill the Matrix

　横に何マス繋がっているか？　が何個ずつあるかを分かれば良い。
　それは最大長方形のアルゴリズムを使えば解ける……という情報を得てAC。

　スタックを利用して最大長方形の面積を求めるアルゴリズムが頭に入っていなかったのが一番の問題だった。実際、「最大長方形」という文字を見てもピンと来ず、検索してどういうアルゴリズムだったかを思い出したら解法が分かった。

　典型アルゴリズムを頭に入れておくのが大事。
時刻: 0 件のコメント:
ラベル: ,

2023年6月12日月曜日

ALGO ARTIS プログラミングコンテスト2023（AtCoder Heuristic Contest 020）

　途中までは結構良かったものの、後半伸ばせず188位でした。

コンテスト後のツイート


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

2023年6月11日日曜日

yukicoder contest 392

　全く提出していないけど、一応コンテスト中に問題は読んだので参加（？）


No.2343 (l+r)/2

　解説AC。
　"010101……"に帰着されることはまあ確かに、という感じだが、その後がびっくり。

No.2344 (l+r)^2

　解説AC。

　ある操作回数後のmod 2^xが分かれば、もう一回操作した後のmod 2^(x+1)が分かるというのが凄い。
　M=1ならパスカルの三角形を使えそうなのは分かるので、「mod 2^xについて良い性質が成り立ちそう」と考えたくなるのは分かる。とはいえ、そこから思い付くのは難しいが……。

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

2023年6月8日木曜日

日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）

　Eまで五完。

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


F - Damage over Time

　自力AC。

　答え二分探索。どの呪文を優先して使うかは、$t_i*d_i$が大きい順にソートしておく。さらに、同じ$d$なら長い$t$のものだけを使うといった枝狩りもする。

　あとは、時間Dの間に最大何ダメージ与えられるか？　を計算できれば良い。

　次の呪文に移るべきタイミングは計算できるので、x日～y日までで何ダメージ与えられるか？　が求まればよく、これは、全体（$t_i$日全てダメージを与えたとき）から、実際はダメージを与えられない日が最大何日・最小何日かを計算し、その平均を引けば良い。

　コンテスト中もこの方針で考えていたが、最後の立式で混乱し、一時間考えてもサンプルが合わなかった。が、今やったらあっさりACすることができて不思議な気持ちになった。
　時間が経って頭が整理されたのかなぁ。


 G - Bags Game

　解説AC。

　区間DPを高速化すれば良いという方針自体は（自分は解説を見てしまったが）分かりやすいが、実装がとにかく大変だった。

　添え字を合わせるのがしんどいだけでなく、自分のセグ木による実装だとPyPyでは通らず、RUSTに直してなんとかACした。

　方針は簡単だがACするのは非常に厳しい問題なので、AC人数が伸びなかったのもよく分かる。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)