2024年11月19日火曜日

Codeforces Round 988 (Div. 3)

 時間ギリギリ全完。
 ARCの後だったせいもあり、序盤やる気が出なかったけど、全完できて良かった。

コンテスト後のツイート


2024年11月18日月曜日

AtCoder Regular Contest 187

 A遅解き一完。

コンテスト後のツイート

B - Sum of CC

 解法ツイートを見てAC。DPでできるのでは? と考えたくなるが、主客転倒で考えなくてはいかなかった。

 階段状になることを利用するのは正しくて、そこから、段に関して主客転倒して考えようと思わなくてはいけなかった。主客転倒はちょっと考えたはずなんだけど、うまく考察できなかった。

C - 1 Loop Bubble Sort

 自力AC。

 実験して、-1がなく最後がNの場合は、pow(2,累積maxの更新回数)が答えになると分かった。
 そこまでも時間がかかったが、その数え上げがDPでできると分かるまでも長かった。

 時間があれば自力で解ける問題だったことは分かったが、コンテスト中に通すためにはどうすれば良いんだろうか。

2024年11月17日日曜日

AtCoder Beginner Contest 380

 Fまで六完。

コンテスト後のツイート

G - Another Shuffle Window

 自力AC。

 大まかな方針はあっていたけど、三つ分けたとき、左同士、右同士の転倒数も足さなくてはいけないことを忘れていた。
 結構本質的な考察ミスなので、コンテスト中に解き切るのは厳しかったか……。

 しかし、解けなくてはいけない問題でした。
 



2024年11月14日木曜日

Codeforces Round 971 (Div. 4)

 G1まで。

コンテスト後のツイート

G1. Yunli's Subarray Queries (easy version)

 そもそもクエリの種類がn種類しかないのにMoを使ったのはおかしかった。
 順番に求められますね。

G2. Yunli's Subarray Queries (hard version)

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

 Div.4だから、という先入観があったからかもしれないけど、遅延セグ木を使うと思いつかなかった。
 典型ではあるかもしれないけど、簡単ではないね。


2024年11月12日火曜日

Refact.ai Match 1 (Codeforces Round 985)

 Eまで五完。

コンテスト後のツイート

F. Palindrome Everywhere

 parityが関係するというツイートをヒントにAC。

・RRとBBが同時にあるとダメ
・Rが一個以下、または、Bが一個以下ならOK

 はコンテスト中に分かっていたが、

・RBBRBBはなぜダメなのか?
・RBBBRBBBRBBは良いのか?
・RBRBBRBBは良いのか?

 などは分かっていなかった。

・RBBRBBがダメなのは、相対位置の偶奇を考えれば分かる。(RBRBや、RBRBBBも同様)
R(x)BBR(y)BBのxからyを考える(x,yから同じ文字の方向を挟む方へ動かせる、と考える)と、xがRをまたぐときyもRをまたぐためxからyへたどりつけない。

・RBRBBRBBは良い。偶奇(Rの間に入っているBの個数)両方含まれるなら偶奇をずらせるので良さそう。

 ただ、さらに、
・「RBBRBB」(Rの間に偶数のものが二つある)が含まれていたら即ダメ、にも気付かなくてはいけない。
R(x)BBRB(y)Bのxからyを考えると、xの左右どちらかがRのとき、yの左右は両方Bなのでダメだった。

 これらが分からなくてはいけなかった。

 WAが出たテストケースから、何文字のとき間違っているか? などを推測しながらやらないと解けなかった。時間があったら解けたかもしれないけど、コンテスト中だったら、ランダムテストを書いて考えなければ解けなかっただろうから、短い時間で解くのは結構厳しいね。

2024年11月11日月曜日

Codeforces Round 986 (Div. 2)

 Dまで四完。Eは実装間に合わず。

コンテスト後のツイート

E. Alice's Adventures in the Rabbit Hole

 ツイートした方法であっていた。

 単純に、トポロジカルソート順にDPの値を更新していく……とかじゃなく、枝分かれしたら、そこから一番近い葉まで一気に値が決まる、みたいな感じなので実装に戸惑ったことが間に合わなかった原因か。
 トポロジカルソート順でも、どこから値が伝搬してきているか? みたいなのを持てばできるとは思ったけど、それもちょっと大変。

THIRD プログラミングコンテスト2024(AtCoder Heuristic Contest 039)

 94位。悪くはないけれど……。

コンテスト後のツイート




トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)

 Fまで六完。

コンテスト後のツイート

G - Count Grid 3-coloring

 解法はあっていた。
 DPをdictで実装したらAC。dict→listに直してTLEを解消することはよくあるけど、逆は珍しい。気付かなかった。


2024年11月9日土曜日

yukicoder contest 452

 一問も解けなかった。ずっと参加していたわけではないけど、Aに30分以上はかけたのにひどい。


No.2953 Maximum Right Triangle

 求めたい点Bの座標は(x,y) + k(-y,x)と表せると勘違いし、WAを重ねた。
 kが実数ならこれで良いのだが、kが整数なら、これで全ての格子点は表せない。gcdを考えなくてはいけないとコンテスト終了間際に気付いたが間に合わなかった。

No.2954 Calculation of Exponentiation

 たくさんWAを出した後にAC。
 こういう問題で、たくさん提出してACするのはあまり意味ない気もする。 

No.2955 Pizza Delivery Plan

 一応自力AC。

 巡回セールスマン問題のbit DPをした後、3^Nのbit DPをすれば良いと気付いた。しかし、forループの順番を間違えてWAを出してしまった。

No.2956 Substitute with Average

 一回WAを出したが、WAが出たtestcaseを見て正しい解法に気付きAC。

 累積和みたいなことをしたい(Zero-Sum Rangesみたいなことをしたい)けど上手くいかないかなぁ、と考えていたら、A_iが30以下という制約の意味が分かった。
 そこまであっていたのだから一回でACしたかったね。(A_iが左のいくつかの要素の平均になっている、ということしか考えておらず、右のいくつかの平均になっている場合を考えていなかった)

2024年11月5日火曜日

yukicoder contest 261

 Dまで四完。

コンテスト後のツイート

No.1172 Add Recursive Sequence


 (以前ちょっと読んで挫折したことがあったはずなのだが……)読みやすく、すんなり理解できた。
 が、実際に実装するとなると累積和の添え字など迷いどころが多くかなり大変。線形漸化式を加算するクエリの問題を見たら、この提出を見に戻った方が良い気がする(かといって、ライブラリにするほどの出現頻度はないはず)。


2024年11月4日月曜日

Codeforces Round 984 (Div. 3)

 Fまで六完。Gはコンテスト終盤に思いついたのだけど、実装する気力が湧かなかった。最初考えていたものを提出したらWAで、ちょっとデバッグがやりにくいWAの出方だったので、実装したとしても間に合っていなかった気がする。

 いつものDiv.3よりやや簡単めで、特にEまでは楽な気がしました。
 Fは、0^1^2^3=0、4^5^6^7=0のように、累積xorが四つ周期になることを利用する知識問題という印象でした。


G. Library of Magic

 二分探索すれば解けそうだが、三つの数字のxorが0だったときが困る。

 が、よく考えると、最上位bitを固定すれば、そこに三つ数字が含まれていてxorが0になることはないし、(同じ数字ではないので)二つが0になることもない。
 なので、解ける……と思ったらWA。

 冷静になると、一回につき二分探索を行う回数が最大60回くらいかかるので、制限回数である150回をオーバーしてしまう。
 "xor 1 n"と聞けば、三個の数のxorは分かるので、二分探索するのは二回にできてAC。

2024年10月31日木曜日

Codeforces Global Round 27

 Cまで三完で過去最悪の成績で紫に落ちた。

コンテスト後のツイート

D. Yet Another Real Number Problem

 コンテスト中の最初の提出を修正してAC。最初に考えていた、dequeを使ってうまく後ろ二つをmergeしていく、という方針が正しかった。

 ただ、mergeの条件が間違っており、修正に10WAを費やしてしまった。ちゃんと立式すれば良いはずなのだが、立てた式で計算ミスをしていたりして……。

 ちゃんとやれば解けたはず、と言っても間違いではないだろうが、実際のACは非常に遠かった。
 

E. Monster

 コンテスト中に提出したもののパラメーターをちょっと変えたらAC。

 コンテスト中は、最大値が10^8なのに、10^5ごとに計算してその付近の上位三つを探索していた。平方分割を意識しているのなら10^4ごとに探索する方が自然だし、その方が適切に探索できるだろう、と変更(上位10個を探索)したらAC。

 7ペナもしているのに、この変更を思いつかなかったのはおかしい。焦って頭が働いていなかったんだろうなぁ。

2024年10月30日水曜日

Educational Codeforces Round 171 (Rated for Div. 2)

 Dまで四完。

コンテスト後のツイート

E. Best Subsequence

 「燃やす埋める問題」というキーワードを見てAC。

 コンテスト中、フローは少し考えたはずなのだが、ちゃんと追及しなかった。
 DPなどでは指数時間の解法しかないときにフローを疑うのは大事で、特に、「燃やす埋める問題」を疑ってみなくてはいけない。

 フローを考えた時間はあったはずなのに、「燃やす埋める問題」ではないかと考えなかったのは反省。





2024年10月29日火曜日

yukicoder contest 449

 Dまで四完。


No.2914 正閉路検出

 解説AC。

 コンテスト中に解けなかったのは仕方ないとしても、解説読まずにACしたい問題でした。
 重み付きUnionFindを使うというのは自然なのに、ちょっと捻った形で出題されると気付けないのは情けない。

No.2915 辺更新価値最大化

 解説AC。

 最短経路問題におけるポテンシャルは、最小費用流のライブラリを作ったときしか勉強しておらず、全く忘れていた。こういうときにも使えるのか。復習になった。

No.2916 累進コスト最小化

 自力AC。

 各cごとにダイクストラをするだけでした。

2024年10月27日日曜日

yukicoder contest 293

 A一問しか解けなかった。ひどい。


No.1492 01文字列と転倒

 一応自力AC。

 Tester解説と同じ方法だと思うんだけど、計算量がよく分からなかった。
 五乗じゃないの? と思ったけど、ちゃんと解析したら四乗になりそうな気もしてきた。

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

 Fが解けず六完。Eが難しかった。

コンテスト後のツイート

F - Avoid Queen Attack

 クイーンを置くごとに、置けなくなるマスが何個増えるか数える……というのはコンテスト中に考えていたが、setで管理すると書きやすいという情報を得て、その方針でAC。
 いや、今思うと、重複をどう処理するかはコンテスト中ちゃんと考えられていなかったね。既におけなくなっている座標をsetで管理するという方針は、実装面だけでなく、重複を取り除くという点でも大切だった。

 ただ、その方針でも実際に実装するのは苦戦した。





2024年10月21日月曜日

yukicoder contest 450

 ABCEの四完でした。


No.2940 Sigma Sigma Div Floor Problem

 解説AC。

 コンテスト中は、各i(<=N)について大体√iの計算時間で計算できるので、それをN回やっても間に合うか? と思ったがTLE。埋め込めばACはできそうだけど実装しなかった。

 解説を読むと、シグマを交換するのが本質だった。
 割る数を固定するのではなく、割られる数を固定すると約数を考える問題になる。

 割る数を固定しても良いところまでいくこともあって思いつかなかったけど、頭の柔軟さが足りないね。

No.2942 Sigma Music Game Level Problem

 一応自力AC。

 セグ木を二本立てれば簡単にできる問題に見えたがWA。配列Lおよび三つ目のクエリの意味が分からないので、どこか誤読しているのかも……と思ってDへ戻ったが、単純な実装ミスでした。
 Aを回数順にしてからセグ木に入れなくてはいけないのにAをそのままでやっていた、セグ木の内部をちょっと書き換えたとき間違っていた、クエリ1でAに何か付け加えるときのupdateの仕方を間違えていた、と三ヶ所。

 こんな短い中で三つもミスしているのは良くないねぇ。

No.2943 Sigma String of String Score Problem

 自力AC。

 DPして部分列の個数を求めて、他の箇所を使うか使わないか決めれば良い。計算量10^8がPyPyで間に合うのか分からないまま提出しましたが、1sもかかりませんでした。

No.2944 Sigma Partition Problem

 しばらく考えた後、これって分割数ってやつでは? と気付き、検索し、ここを参考にしてAC。

 分割数のDPを自力で導出するのは難しいけれど、有名な概念だということはすぐ気付きたい。

2024年10月20日日曜日

AtCoder Beginner Contest 376(Promotion of AtCoder Career Design DAY)

 Eまで五完。

コンテスト後のツイート

↑ツイートのFの位置が間違っています。

F - Hands on Ring (Hard)

 既にあるACコードとランダムテストなどしてAC。

 本質的なやり方は正しかったが、場合分けが足りていなかった(目的地の場所に別の手がある場合、二通り押し出すことを考えなくてはいけないのを忘れていた)り、既に目的地に手がある場合にも押し出すことを考えて答えが減ったりし、非常に苦労した。

 コンテスト後に一時間以上かかっている。本来ならランダムテストを書く時間も必要だったからもっとかかっただろう。解法は分かってもACは遠い問題ですね。

G - Treasure Hunting

 解説放送を見てAC。

 解法を思い付くのは難しいかもしれないけど、解法を教えてもらったとき理解するのは難しくない。
 ただ、実装方針はやや難しい。トポロジカルソート順にマージするのか? などと考えてしまいダメだった。
 平均重みが大きいものから、親と比較し、マージしていくというのが正解。方針が分かってしまえば実装も重くない。

 類題(元ネタ?)というこれも解いておきたい。→ACしたけど結構実装に時間かかってしまった。maspyさんが類題をまとめてくれているので、これも解いておくべきか。

Codeforces Round 979 (Div. 2)

 Dまで四完。Eを考えていたら寝てしまった。


E. MEXimize the Score

 自力AC。

 0から順に、部分列に何個採用するかを考える。

 たとえば、2をk-1個採用したときよりk個採用した方がスコアが上がるのは、0や1がk個以上含まれているときである。

 なので、今までの数字について、全てk個以上もっている場合の数は何通りか? もっておき、それを利用して、k個採用したらスコアが上がる場合の数を計算、和を取る。

 一応、主客転倒の考え方を使っているのだが、最初それをしなくても間に合う気がしてDFSを書いてペナを出してしまった。主客転倒自体は思いついていたため、再度考え直してACした。

2024年10月17日木曜日

AtCoder Regular Contest 185

 AB二完。

コンテスト後のツイート

C - Sum of Three Integers

 解説放送を見てAC。

 FFTは全く考えなかったが、登場回数の配列同士を畳み込めば、二つの配列の和の要素の登場回数になる……というのは初見ではなかったかもしれない(よく覚えていないが)。これは身に着けておきたい。

 ただ、解法が分かった後もACに非常に苦労した。ランダムケースで実行しても何で落ちているのかが分からず、かなりたくさん提出デバッグをしてしまった。

・PythonでFFTを使うなら、配列をnumpy.arrayで書き、np.fft.rfft(A,k)やnp.fft.irfft(f)を使うと速い。
・畳み込み後の要素の値が大きくなることがあるため、np.fft.rfft(A,k)のkの値をギリギリに取るのではダメ。最大値をきちんと見積もる。

 このあたりが問題だった。気を付けないと。

D - Random Walk on Tree

 解説放送を見てAC。

 解説放送で一番難しいといっていたパートは、ChatGPTに「ランダムウォークで、スタート地点からn歩の点にはじめて到達する歩数の期待値を教えて下さい。」と聞いたら、「スタート地点 0 から n に初めて到達するまでの期待値は、1次元ランダムウォークでは次のように表せます:

・En=n^2 つまり、最初に n に到達するための期待歩数は n^2  です。」と正しい返事がきた。

 また、コンプガチャについてはけんちょんさんの記事など詳しいものがある。

 どちらも、自力で導出できると良いけど、覚えておいても良いくらいの内容な気がする。

 なので、対称性に関する考察さえきちんと行ってどんな問題に帰着できるか分かれば、あとは知識(もしくは調べて)で解けたんですね。

E - Adjacent GCD

 解説放送を見てAC。

 約数包除を行うとき、各素数についての他次元平面と考えると分かりやすい、というのは知っていた(が、コンテスト中は出てこなかった)。
 
 で、約数包除のとき、あるxについて、その約数に関する値の総和を取るとxになるような値があると良い。そういうのがあれば、毎回包除をして約数の個数^2の計算時間をかけず、約数の箇所にある値の和を取る/値を書き込むさえすれば、毎回約数の個数回の計算時間で済む。

 それを実現するのが、オイラーのトーシェント関数だった!

 オイラーのトーシェント関数の定義を考えれば簡単に分かることなのだが、はじめて知りました。
 約数包除に関して理解できた気がするので、もう忘れないといいな……。

 なお、今回の問題は、100000までのトーシェント関数の値と約数のリストを予め列挙してACしました。

2024年10月14日月曜日

パナソニックグループ プログラミングコンテスト2024(AtCoder Beginner Contest 375)

  EとGが解けず。

コンテスト後のツイート

E - 3 Team Division

 解法ツイートを見てAC。

 部分和問題に近いからDPだろうと思ったのに、どういうDPをすれば良いか見えなかった。だからといって、フローを疑ったりしていたのはダメ。

 DP[Aの和][Bの和]=そのときのペナルティ

 のようにすれば良かった。Bの総和に制約があるのも不思議なので、そこからDPを見破ることもできたはず。

G - Road Blocked 2 

 解法ツイートを見てAC。

 スタートとゴールからダイクストラして必要な可能性のある辺を求めるところまではOK。あとは橋を探せば良かった。

 何度もランダムに進ませればどの辺が必要なのかは分かるのでは? と思ったが、片側だけ二方向に分かれていく木を考えればすごい低い確率でしか到達しない頂点は作れて、それ以外の頂点を別の一つの頂点につなげる……みたいにすれば、そこから出た辺は非常に高確率で通りますね。


2024年10月11日金曜日

丸紅プログラミングコンテスト2024(AtCoder Regular Contest 183)

 Bまで二完。

コンテスト後のツイート

C - Not Argmax

 解説放送を見てAC。

 区間DPだと気付くことさえできれば難しくないと思う。問題はどうやって見つけるかだが……。手を動かして実験すれば見えてくるのかなぁ。

 なお、メモリ制限が結構きつい。各[l, r]に対してどのindexがmaxを取れるか? を愚直に持とうとすると、500^3の配列が必要になり、PyPyだとMLEした。あとちょっとメモリを減らせばいいだけなのだが、そこに結構苦戦した。




2024年10月7日月曜日

キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374)

 Fまで六完。

コンテスト後のツイート

G - Only One Product Name

 解説放送・解説を見て、けんちょんさんの記事も参考にAC。

 SCCして、DAG の最小パス被覆に帰着、という解法はちゃんと勉強していれば思いつけそう。(コンテスト中、自分も一瞬フローでは? とは思ったので。その後違う方向に行ってしまったけど)

 ただ、実装が難しい。SCCで頂点と頂点とを同一視できても、そこから出ている辺は同一視できない、というあたりが混乱を招く。

 たとえば、AとBには両向きの辺があり、CとDには両向きの辺がある。さらに、AからCへ、BからDへそれぞれ辺があるとき、この二つの辺は区別しないといけない。

 このあたりに注意するのが非常に難しく、たくさんのWAを重ねてしまった。解法を詰めてからやればできるのかもしれないけど、解法の概要が思い浮かび、細かいところは実装しながら詰めよう、とすると非常に難しい気がした。

2024年10月4日金曜日

Codeforces Round 974 (Div. 3)

 G以外六完。

コンテスト後のツイート

G. Milky Days

 自力AC。

 dequeを使って古いミルクを管理していけば良い。たいして難しくはないのだが、二度も誤読した。

・一度目の誤読:古い順に飲むと誤読
・二度目の誤読:milkがmに足りないとき、消費しないと誤読

 誤読したせいで非常に長い時間(一時間以上。二時間くらいかも)かかってしまった。
 





2024年9月30日月曜日

Codeforces Round 976 (Div. 2) and Divide By Zero 9.0

 遅刻して参加。Cまで三完。


D. Connect the Dots

 dが小さいので、dとその余りごとに分けて、各i in [1 , ... ,n]に対して、各dについて[x , ... ,y] が同じグループでiがその中に入るなら、xとiをUnion-findで繋げる、とやっていけば良い。
 コンテスト時間ギリギリに実装し終わったのだが、d>=2だと勘違いしておりWAでした。そこを修正したらAC。Ratedでこんなことしたら酷いのでUnratedで良かった。

AtCoder Grand Contest 068

 一問も解けず。

コンテスト後のツイート

B - 01 Graph Construction

 解説を見てAC。

 何も思いつけなかったのは仕方ないのだが、愚直っぽい方法で上手くいきそう、と考えたのはダメ。メタ読みみたいになるけど、AGCなのだから何か上手い方法があるはず……と追求すべきだった。
 愚直っぽい方法は、遅くても、最初に上手くいかなそうな例が見つかった時点で捨てるべきだった。




2024年9月29日日曜日

AtCoder Beginner Contest 373

 Fまで六完。Fは未証明だったけど、この制約だと正当だったかも?(w=1や2がたくさんある場合が問題だけど、それはカバーできてそう)

コンテスト後のツイート

G - No Cross Matching

 解説AC。

 最小費用流の方法でACした。
 自分の最小費用流のライブラリはひどいと思っていたが、TLEが出たため久しぶりに見直した。多少は速くなったか。

 ただ、今回のテストケースではたまたまACできただけで、簡単にTLEするケースは作れる模様。うーん。



2024年9月28日土曜日

Codeforces Round 973 (Div. 2)

 Cまで三完。


D. Minimize the Difference

 解説AC。

 問題文で与えられた操作を用いて、広義単調増加にすれば良い(逆に、A[i]<=A[i+1]となったらそれ以上操作はしない)だろうことにはコンテスト中に気付いていた。

 どういう操作でそれを実装できるかが分からなかった。

 これは、[値, その要素の個数]を持って、配列の値を見たら後ろの要素とマージしていく……とすれば実装できる。
 マージすることは思いつくけど、ランレングス圧縮のようなことをすると計算量が減るとは気付かなかった。
 この方法を思い付けなかったのは悔しい。

E. Prefix GCD

 自力AC。

 直感的に正しそうな貪欲を実装したらそのままACだった。証明も、こんな感じかな? と思ったもの(ちゃんと証明はしていない)で良さそうだった。

yukicoder contest 448

 遅刻して、Aが分からず0完。


No.2902 ZERO!!

 自力AC。コンテスト後、横になって考えていたら気付いた。

 N!ではなく、一般のNについてこの値を求めることを考えていたら、約数の個数を求めることとかなり似ていることに気付いた。

 たとえば、$N=2^8*3^{10}$のとき、約数の個数は(8+1)*(10+1)個だが、今回はそれに加えて、(8/2+1)*(10/2+1), (8/3+1)*(10/3+1),  (8/4+1)*(10/4+1), ... といった値を加えれば良い。

 

2024年9月26日木曜日

AtCoder Regular Contest 184

 Aしか解けず。

コンテスト後のツイート

B - 123 Set

 解説放送を見てAC。

 解説を見ると、ステップは多いものの一つ一つの難易度は高くない。解けなくてはいけない問題だった。(実装が終わるか、という話はあるものの、少なくとも解法の概要は自力で分かるべきだった)
 が、コンテスト本番では最初のステップすらできていなかった。2や3でギリギリまで割った値が異なれば互いに影響しない、ということには気付いていたが、それを考察に生かせていない。

 Aを解いて気が抜けてしまったというところもあったと思う。最後まで気を抜かずにやり切るようにしたい。

C - Mountain and Valley Folds

 解説放送を見てAC。

 山折り、谷折りがどのようになるか? というのが掴めれば、それ以降の考察は結構自然に思えた。
 ただ、自分では山折り、谷折りの挙動が掴めなかったんだよね……。解説放送の最初に話していた、半分折り返せばできるんじゃない? とは一応考えたが(それも形にできなかった)。

2024年9月25日水曜日

日立ヴァンタラプログラミングコンテスト2024(AtCoder Beginner Contest 368)

  Eが解けなかった。

コンテスト後のツイート

E - Train Delay

 解説・解説放送を見てACしたが、ACした後も自分のコードが正しいか自信が持てず乱択で比較したりしてしまった。(正しかったよう)

 出発時刻が早い列車から見ていこうというのは良いが、それ以外に何を持てば良いのかが難しい。
 各駅ごとに、(本来の到着時刻, 遅れたときの到着時刻)を全て持ってそれら全てについて調べればもちろん良いのだがそれでは計算量が間に合わない。

 ある列車について、その発車時刻より以前に本来の到着時刻があった列車全てについて調べ、遅延に原因する列車が特定できたとき、(調べた範囲の他の列車については忘れて)その列車についてのみ覚えておけば良い。ここが重要。

 なぜそれで良いのかが整理できなかったのだが、それ以降の発車時刻のものは、今回遅延原因だった列車とは本来乗り換え可能だったから、ということ。

 ここで迷う人は結構いるんじゃないかと思う。ただ、自分が図を描いたり色々してもしばらく理解できなかったことをこうやって言葉だけで書いても伝わらないとは思うけれど……。


2024年9月21日土曜日

yukicoder contest 447 オムニバス

 ABの二完。Bでxorの基底をちゃんと使えたのは良かったが、Cできなかったのはひどい。


No.2896 Monotonic Prime Factors

 解説AC。

 コンテスト中、素因数をソートして横に並べて、それらをn個に分ける場合の数だから重複組み合わせでできるはず……と思いながら、答えが合わず通せなかった。
 x個をn個に分けるのは、x個の間x-1個のうちからn-1個を選ぶのだから、x-1Cn-1になる。これが考えても出てこなかった。

 出てこないにしても、重複組み合わせというキーワードが思い出せているなら、検索とかでどうにかなったはずだよね。ちゃんとしよう。

No.2897 2集合間距離

 解説AC。

 この制約ならBFSするだけと気付かなかったのも反省。また、tester解のように45度回転させて平面走査みたいなことを考えていたのに、二分探索を思いつかなかったのも反省。

2024年9月18日水曜日

RECRUIT 日本橋ハーフマラソン 2024夏(AtCoder Heuristic Contest 036)

 pretest71位→システムテストリジャッジ前100位→リジャッジ後72位でした。

 リジャッジありがとうございます!
 システムテスト結果が出たとき、ジャッジおかしいんじゃないの? というようなことをツイートしたけど、それほど確信はなかった。リジャッジでTLEが減り、順位が上がって良かった。

 最終日まで300位前後で、最終日にAの別の作り方を試し、順位が大きく上がったのも嬉しかった。

 大体ツイートのまとめです。

コンテスト後のツイート

前半四日くらい

 Aを固定したとき、「Bの変更は全体取り換えのみ」とすれば最適解を求められそう……と思って書くが、色々バグらせた上PyPyじゃ間に合わない(あとでRUSTで書き換え、枝狩りをして一応間に合う。でもシステムテストだとTLEするかも→した)

最終日まで

 Aとしては適当な評価値で山登り/焼きなましを考えていたが、それだと300位前後にしかならない。最終日に方針転換を迫られる。

最終日

 t[i]からt[i+1]への最短距離での行き方を最初に調べ、それらを連続部分列として多くもつようにしたい。

 まず、各点から各点までのBFSを使って、t[i]からt[i+1]まで進む頂点を列挙。この集合をNEEDとする
 そのうち、長さが短いもの同士で、一番最初の文字=一番最後の文字とかなったりするものを組み合わせていく。評価値は、「できあがったものの長さ/組み合わせた個数」のようにする。
 評価値の小さい順にAにおいていく。ただし、Aの長さ+Aに出てきていないNEEDの個数<=LAとなるギリギリまでおき、その後はNEEDに入っているものをおいていく。
 NEEDに入っているものxをおくときは、今までのAの中で、xのそばにxと隣接するものができるだけ多いような場所に置いた。

 これが最終提出でした。

気になっていたこと

 ところで、「自分のコードは、Aを与えられたら、Bを全取り換えするものだけ使うなら最善のものを出力しているつもりだったけど本当か?」が気になっていたので調べてみた。

 上位の方のコードで出力しているAを入力し、そのときのスコア(そのコードでのスコア vs 自分のスコア)を比較すると、

・B全取り換えだけでやっている人には大体ちょっと勝ち(or引き分け)
・部分取り換えも使っている人には結構負け

 という感じだった。

というわけで、自分のコードは、B全取り換えだけ使うなら多分最善だったけれど、

・厳密な最善を求める必要はない。多少スコアを犠牲にしても、計算量改善した方がメリットは大きい
・部分取り換えの使い道は少ないと思っていたけど、自分が思ったいたより大きく改善するらしい。

と分かった。

 Aを決める部分の方がスコアに影響する度合いとしては大きいけど、そっちは発想力が求められた印象。今回はたとえば、「中心を決めて木構造にする」というAの取り方が強かったようだけど、コンテスト中に思いつけたか? と考えると結構厳しく感じる。それに対して、「Aを求めた後何を出力するか?」の部分は発想よりアルゴの力が求められた気がする。

 その部分で、(Bを全取り換えする場合の)最適解を求められていた(と思われる)という意味では、やるべきことはやっていたといえるけれど、もっと計算量を削減しなければヒューリスティックな手法は使えない。もっと考えなくてはいけなかったなぁ。

2024年9月17日火曜日

第11回 Asprova プログラミングコンテスト(AtCoder Heuristic Contest 037)

 141位。

コンテスト後のツイート

 マージした後のx+yの値が一番大きくなるような二点をマージする(マージの仕方はツイートと同じ)……という貪欲が強かった。
 これを思いつかなくてはいけなかったのだが、厳しかった。

 座標が大きい方から考えるのが良さそう、とは思ったけれど、コストをパラメーターに考えたくなってしまう。座標が大きいものをマージしたらコストも低くなる、とは考えにくかった。

AtCoder Beginner Contest 371

 Eまで。

コンテスト後のツイート

F - Takahashi in Narrow Road

 解説放送を見てAC。SortedSetを使った。

 解説放送を見て衝撃だったのは、$X_i-i$、$G_i-T_i$と座標変換して良いというところだった。これは思いつけない。
 これを思い付いていればそれ以降の部分は自力で解けた気がするので、ここが本質だと思う。しかし、言われてもかなり長いこと正当性が分からなかった。
 こういう変換ができることもあると覚えておきたい。

 

G - Lexicographically Smallest Permutation 

 大体自力でACだけど、中国剰余定理などという単語はツイッターで見た。

 順列を、どう巡回するかで分けるのはよくある方法。一つ決めるとその巡回部分は全て決まるので、それを使って最初の数字から決めていく。辻褄を合わせることができるか? とい部分で中国剰余定理を使えばOK。

 Fでなくこっちを解いていればコンテスト中に解けた気もする。
 ただ、コンテスト中は、Gの「辞書順」という単語を見て避けてしまったんだよね。もうちょっとちゃんと問題を把握してから解くか避けるか決めた方が良いね。









2024年9月14日土曜日

yukicoder contest 446

 Dまで。


No.2891 Mint

 結構解かれていたのに解き方が分からず、今話題のChatGPTに聞いたところ、商が同じものをまとめて計算すれば良い、と教えてもらった。なるほど! と思ったものの、コードは若干間違っていたため自分で書いたらかなり時間がかかった。



2024年9月13日金曜日

Codeforces Round 958 (Div. 2)

 Dまで。

コンテスト後のツイート

E. Range Minimum Sum

 解説AC。こたつがめさんの放送の振り返りも参考にした。
 また、Cartesian Treeはけんちょんさんのブログを参考にした。
 なかなか解説を理解できず、苦労した。

 まず、A[i]を取り除かない場合は、各iに対して、A[i]の左側で、A[i]より初めて小さい値が出てくるindexはどこか?(右側についても同じもの)を調べれば計算できる。

 その上で、差分計算で求めたい。
 このときの差分計算というのは、iを除いた場合とi+1を除いた場合で比較するというもの。全く取り除かない場合と比較するのではない。(結構後者を考えてしまったが、前者が自然ですね)

 そのとき、変更される部分がたいして多くない、というのが重要。取り除くindexがiからi+1へ変更したとき、Cartesian Treeにおいてiの左の子と、そのさらに右の子孫たち(及び、その逆側)、及び、i+1の左の子と、そのさらに右の子孫たち(及び、その逆側)しか変更されない。それらを変更すればOK。

 ただ、どこまで変更すれば良いかもO(1)でできるらしいのだがよく分からず、範囲最小値を求められるSparse tableを使って二分探索で求めた(Segment treeだとTLE)。





2024年9月9日月曜日

トヨタ自動車プログラミングコンテスト2024#9(AtCoder Beginner Contest 370)

 Eまで五完の上、ペナルティをたくさん出してまずい。

コンテスト後のツイート

F - Cake Division

 解説AC。

 二分探索するのは分かるが、全点から試さなくてはいけなそうで、どうすれば良いか分からなかった。コンテスト中はそこを高速化することは思いつかず、全部試さなくてもいくつか点を試せば良いのかなぁ、というのを提出してWA。
 ダブリングで高速化できるのはなるほど、でした。

 あと、コンテスト中は、全点を試す→二分探索の順番で考えていたことも思いつかなかった原因かも。順番を変え、二分探索→全点を試すで考えるのが重要だった。

 結構難しいが、以前、類題を解いたことがあったことを考えると解けなくてはいけない問題だった。


2024年9月8日日曜日

yukicoder contest 444

 Aを解いた後、Bを読んでいたら目が痛くなって撤退。


No.2871 Universal Serial Bus

 解説AC。

 コンテスト後、解こうとしたらWAを量産してしまった。
 二つ罠があった。

・全ての場合に確率が0のとき、期待値は無限になる。

 期待値の定義を考えれば当たり前で、これに気付かないのはまずい。

・「ケーブルを 180度回転させて上下ひっくり返した状態」は左右も反転する!!

 これ。
 testcaseを読んだり解説を読んでもしばらく気付かなかった。コンテスト中ACするのは難しかったのでは。

No.2872 Depth of the Parentheses

 自力AC。
 二次元DPで計算量はKの三乗にはなった。

 evilケースどうやるの?

No.2873 Kendall's Tau

 自力AC。
 「ケンドールの順位相関係数」は初耳でした。

 どういうときに使うのかな~と思ったら、順位の相関を計ると知り納得。(名前が「順位相関係数」だから当たり前なのだけど、定義だけ読んだら分からなかった)

2024年9月7日土曜日

yukicoder contest 443

 ABを解いた後、AHCの最中ということもあって疲労により撤退。


No.2864 String of yuusaan

 解法ツイートを見てAC。

 パッと問題を見たとき、周期性があるとは思わなかった。色々頑張れば(周期性がなくても)解けると思ったが、頑張る気力がなく撤退。
 周期性がなくても解けそうな問題だけに、実験しようという気持ちにもあまりなれないから、周期性があると気付くのは難しい気がするのだけど……疲れていてちゃんと考察できなかったからなのかなぁ。

No.2865 Base 10 Subsets 2

 自力AC。
 これは苦労せず解けました。

No.2866 yuusaan's Knapsack

 自力AC。

 やり方は割合すぐに分かったのだが、バグってしまいACまで時間がかかった。「Pythonのlistは参照の値渡しであること」が原因でこれ自体は知っているのだけど、値を渡しているつもりで間違えてしまうと、どこでミスっているか気付くのは大変ですね。

No.2867 NOT FOUND 404 Again

 自力AC。

 解法が桁DPなのは分かりやすい。最近は桁DPは下の桁からやっていたが、今回久しぶりに上の桁から実装した。
 DPの遷移で、"4"が一致しているところから、"40"が一致しているところだけでなく、"4"だけ一致しているところにもいけることに気付けず、愚直を書いて比較して気付いた。

2024年9月1日日曜日

AtCoder Beginner Contest 369

 Eまで五完。

コンテスト後のツイート

F - Gather Coins

 セグ木DPで答えを求められるのはあっていたが、復元方法が分からなかった。

 コインをソートした状態で考え、各コインが何回で取れるかという情報を持っておけば良い……というシンプルな方法だった。

G - As far as possible

 解説放送を見てAC。

 貪欲に長いpathを取っていけばいいというのは分かったが、実装が分からなかった。
 木DPでそういうpath分解ができるというのは思いつかなかった。典型のようなので身に着けておきたい。

2024年8月25日日曜日

yukicoder contest 441

 ABの二完。


No.2844 Birthday Party Decoration

 ひどかった。

 正しい解法を実装しようとしたが答えが合わず(マイナス方向に進むときの計算をミスっていた)。
 プラスとマイナス両方へいく場合を、(プラス側に行く場合の距離, マイナス側へ行く場合の距離)をソートし、累積maxを用いて計算しようと思ったが、その場合の総距離の計算を間違えていた。(大きい方は二倍しなくて良いと勘違い。)

 どのようなテストケースでWAが出ているかを見て、やっと気づいてAC。

No.2845 Birthday Pattern in Two Different Calendars

 解説AC。

 貪欲で良いと勘違いし、WAになっているテストケースを見ても何で落ちているか分からなかった。言われてみればmod M-1での分解を考えるという典型なのに全く思いつかなかったのはまずい。

No.2846 Birthday Cake

 解説AC。

 LCMを使ってDPするのは考えたけど、除いて良い数があると思えず、別な方法も思いつけずで解説を見てしまった。

2024年8月20日火曜日

AtCoder Grand Contest 067

 A一完。

コンテスト後のツイート

C - Divisibility Homomorphism

 解説・解説放送を見てAC。

 コンテスト中の考察は全く間違っていた。

・1 3

 がNoだと気付くのが第一歩で、そこから上手く考察を繋げていかなくてはいけなかった。

 こういうのが答えになりそう! と思いつけば(証明できなくても)ACにたどりつける問題ではあるけれど、逆に、一旦間違った方針に進むと方向転換の難しい問題だったと思うので、どうしようもなかったか。




2024年8月18日日曜日

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)

 D1までとF1で五完。

コンテスト後のツイート

F2. Court Blue (Hard Version)

 自力AC。F1と同じ方法でできた。

 F1では、nに一番近い素数を基準にDFSしたわけだけど、それに加えて、mに一番近い素数を基準にDFSしたらAC。nowをmin(p-1,m)から小さい方へ動かしていき、(p,now)からxのプラス方向やyのプラス方向にどこへ行けるか調べていく。それで、x成分がnにたどりつけたら探索をやめる。
 これをx,y逆転させてもう一回やる。

 これでACできたけど、n=mの場合と違い、正当性はやや怪しい。

(追記)正当性は大丈夫そう。n<mでnに一番近い素数を基準にするときが問題なのだけど、mがある程度大きいなら、mに近い素数をpとして、(n,p)にたどりつけるので問題ない。nとmが近いときは、上記の方法で多分大丈夫。


2024年8月17日土曜日

Educational Codeforces Round 169 (Rated for Div. 2)

 Eまで五完。

コンテスト後のツイート


F. Make a Palindrome

 解法ツイートを参考にAC。

 コンテスト中に三乗で解く解法は思いついていた。
 配列Aにおける値は、

・配列Aの左端右端の要素が同じなら消す。違うなら、小さい方を合体させて答えを一つ増やす。これでO(配列の長さ)で求まる。

 で求められる。

 この計算量を落とす方法が分からなかったが、累積和を使って特徴づけできる。

 「両端の要素が同じなら消す」という操作をできるだけ増やしたい。a, b, c, dをindexとして、(a, b)から両端を消すことで(c, d)へもっていくことにすると、累積和Sについて、

・S[b]-S[a]=S[d]-S[c]

 が成り立つ。これを変形して、

・S[a]+S[d]=S[b]+S[c]

 なので、二つの累積和の和が同じ物を集め、index i, jについてj-iが小さい方から見ていくと、(z, w)の後に(x, y)がきた(S[x]+S[y]=S[z]+S[w]が成り立っている)なら、DP[x][y]=DP[z][w]=(z-x-1)+(y-w-1)のようにして全ての値を求めることができる。

2024年8月15日木曜日

Codeforces Round 966 (Div. 3)

 Gまで七完。Hが解けず。……と思ったが、Cがシステムテストで落ちた。

コンテスト後のツイート

C. Numeric String Template

 sの長さがnじゃなかったら即ダメ、と返すようにしてAC。その事実自体は気付いていたけど、こういうcaseが作れるの気付いてなかったなぁ。

H. Ksyusha and the Loaded Set

 解法はあっていた。
 A[0]とA[1]の間の区間をセグ木に入れるのを忘れていた。こんな単純なことだったとは。

 まあ、こういうときはランダムテスト書くしかないかね。書こうか迷ったんだけど、ちょっと時間が足りなそうだった。(ランダムテストは書かず、テストケースを見てACしました。)

 

2024年8月12日月曜日

AtCoder Beginner Contest 366

 Dまで四完と失敗。

コンテスト後のツイート

E - Manhattan Multifocal Ellipse

 コンテスト中の方針でAC。

 xに対して、x方向に関するマンハッタン距離の和を求める関数を得なくてはいけないが、そこでミスがあった。
 ただ、それを修正しても、二分探索で上限・下限を求める方針だとTLEし、尺取りに直さなくてはいけなかった。

 解けなくてはいけない問題だったのは確かだが、実装もやや面倒だし、簡単というわけでもない気がする。こっちよりFがACできなかった方がまずい。

F - Maximum Composition

 解法ツイートを参考にAC。

 コンテスト中、うまくソートする問題だろうと思い、

・C(Ax+B)+D>A(Cx+D)+B

 を変形して、

・BC+DとAD+B

 の大小比較を考えれば良いというところまでは書いた。なんでそれで解けなかったんですか? そこで式変形は止まっている……。

 さらにいうと、昔、この問題はオンサイトで自力ACできているのに、今回解けなかったのはひどい。

2024年8月10日土曜日

yukicoder contest 440

 AとCの二完。Bが解けず。


No.2836 Comment Out

 全く思いつかなかった。

 「数を増やす操作」を繰り返したものが最大だと思い込み、たとえば、N=5なら、

・5 4 3 2 1

 とか

・2 4 5 3 1

 みたいな列が最大だと思い込んでしまった。(それ以下のものは全て作れる)

 しかし、この判定が意外と難しく、そこで間違えていると思ってしまった。(今でも、やり方が分かっていません)

 実際の解法は単純でした。実験コードをすぐ書くべきでしたね。
 Ratedコンテストならもっと早く実験していると思うのでACできただろうと思うものの、多分実験コードを書いたのはWAを二個くらい出した後だし、ACするまでに時間かかっただろうな……。

No.2838 Diagonals

 自力AC。

 これは、(実験せず)頭の中で考えて正解を導けた。嬉しい。


2024年8月8日木曜日

Codeforces Round 964 (Div. 4)

 全完。

コンテスト後のツイート




2024年8月5日月曜日

AtCoder Regular Contest 181

 ACの二完。

コンテスト後のツイート

B - Annoying String Problem

 解法ツイートを参考にAC。

 Sの一文字目がTの何文字目にあたるのか? を調べる方針は良かったし、TがSの繰り返しだろうというのも当たっていた。
 そこまでくればgcdで周期を考えるのは自然なはずだが、これを思い付けなかった。うーん。

 また、Tの長さを計算したら負になる場合がある、ということに気付かずWAやREを重ねてしまった。
 考察は後一歩だった気もするが、ここに引っかかることを考えるとACは遠かったね。

D - Prefix Bubble Sort

 概ね自力でAC。(コンテスト後にツイートなどは見たけど、あまり参考にせず解いた)

 xという操作を適用すると、「x以前にあって、転倒数への寄与が0より大きいものたち」は、indexが一つ下がり転倒数への寄与が一つ小さくなる、ということには割合すぐ気付けた。
 が、実装が上手くできず、Aが広義単調増加であることをどう使えば良いかも迷った。長いこと遅延セグ木でどうにかならないかと考えていたけど上手くいかず、Aが広義単調増加ならクエリに関するimos法でできると気付けた。(これが公式解説の方法だった)

 700点にしては簡単で、時間があれば自力で解けたとは思うけど、Cの後こっちを解いていれば解けたという気はあまりしない。

2024年8月3日土曜日

yukicoder contest 439

 Aしか解けず。


No.2828 Remainder Game

 解説AC。

 結構長い時間かけて考えても分からず、解説を見たら、誤読に気付いた。A_1~A_5の値(のmultiset)を求めなくてはいけないと考えていたが、和さえ求めれば良かった。
 それなら自力で解けた気もするが、実際に考えたわけではないから分からない。

No.2829 GCD Divination

 普通の期待値DPなのに時間がかかってしまった。(答えが合わず、解説も見た)

 なお、コンテスト中に解けなかったのは、全てのNについて答えを求めないとDPが回らないと勘違いしたため。約数だけ調べれば大丈夫ですね。

 

2024年8月2日金曜日

日本レジストリサービス(JPRS)プログラミングコンテスト2024#2(AtCoder Beginner Contest 364)

 Fまで六完。

コンテスト後のツイート

G - Last Major City

 解説AC。(解説放送も見た)

 最小シュタイナー木を履修した。分かってしまえば難しくない。Kが高々10というところから3^NのDPと気付ければ自力で思いつくことも可能だったか?


Educational Codeforces Round 168 (Rated for Div. 2)

 Dまで四完。

コンテスト後のツイート

E. Level Up

 SortedSetをセグ木上の二分探索に直してAC。
 自分のセグ木二分探索のライブラリの書き方が変だったので、修正に時間を要したけど、どう書くのが良いのだろう?

 とりあえず、セグ木の演算が足し算で、
・sum(0, index)がある値以上になる最初のindexを返す
 というセグ木二分探索は実装した。

 一般的には何を二分探索で求めるようにすれば良いんだろう?

 



2024年7月31日水曜日

AtCoder Beginner Contest 322

 Eまで五完。

コンテスト後のツイート


F - Vacation Query

 コンテスト後、Pythonで遅延セグ木を使った実装だとTLEになる……という話を聞いて避けていたのをようやく実装。
 普通に遅延セグ木で通りました。(ただし、二重配列にしないという工夫はしている)

 なお、ツイートで書いている解法だと、遅延セグ木に乗せるものが足りていないですね(多分、実際に実装したら気付いたでしょう)。

 演算が多要素×多要素の場合も簡単に書けるように、遅延セグ木をライブラリ化しておくべきですね。


2024年7月28日日曜日

Codeforces Round 962 (Div. 3)

 全完。

コンテスト後のツイート


2024年7月27日土曜日

yukicoder contest 438

 A、Cの二完。Aが難しくて困ったけど、解けて良かった。(それと比べるとCは簡単だった)


No.2820 Non-Preferred IUPAC Nomenclature

 色々参考にしてAC。

 どうやって解を構成するかは分かったのだけど、木DPとかマージテクとか考えてひどいことに。
 行きがけ、帰りがけを考えればDFSで構成することができた。やっぱりDFS系は苦手なのかなぁ。
 

2024年7月25日木曜日

Codeforces Round 961 (Div. 2)

 B2もDも解けず。

コンテスト後のツイート

B2. Bouquet (Hard Version)

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

 x,x+1が使う候補のとき、

・xをできるだけ使う → x+1をできるだけ使う → xのものをx+1に変換する

 で良いのではないか、というのはコンテスト中にも考えていた。(それで本当に良いのかは分かっていなかったが)
 ただ、ツイートの方法で良いと思ったため方針転換できなかった。

 x,x+1を使う個数の和をm/x個とすると、その個数がxの個数より大きかったとき、最低でも、求める数より大きくなってしまう。それでダメだった。
 (簡単に反例が見つかるかと思ったが、そう簡単でもなかった。ランダムテスト書くしかなかったか)





2024年7月23日火曜日

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

 Fまで六完。

コンテスト後のツイート

G - Sum of Tree Distance

 解説AC。

 マージテクで解けると聞き、マージテクで通そうと思った後も自力で解けなかったのは情けない。「ある頂点から根の方向へ何歩進んだか? の総和」を持たなければいけない気がし、それだと一歩一歩全ての色について更新しなくてはいけないと思ってしまった。

 が、根からの距離の総和さえ持てば代用できるため、マージテクが適用できる。



2024年7月22日月曜日

AtCoder Beginner Contest 363

 Eまで五完。

コンテスト後のツイート

C - Avoid K Palindrome 2

 Pythonで通す方法の一つとして、

・from more_itertools import distinct_permutations

 を使うというものがあったらしい。
 知らなかったので仕方ないか。

F - Palindromic Expression

 ツイートした解法で、bit全探索の部分で、「Nより大きくなるなら探索をやめる」という枝狩りをしたらACできた。

2024年7月20日土曜日

yukicoder contest 437 ('09 Contest 002 day2)

 A一完。


No.2812 Plus Minus Blackboard

 コンテスト中に、プラス、マイナスそれぞれ絶対値の小さいものについて操作を行っていけば良いのでは? と思いついたが証明が分からず、証明を考えていたら終わってしまった。
 コンテスト後、証明は分からないけどとりあえず投げてみたらACだった。

 解説を見るとこの方法で正当そう。
 ただ、この方法を直接示しているわけではないので、「この方法を示そう」と考えるのでは難しかったか。

No.2816 At Most Two Moves

 解説AC。

 1以外の点について、1から一歩でいけない確率は1/2で、2歩でいけない確率はいくらだろう……と考え、中継点と繋がっていないときだな、と思ったはずなのに答えが出せなかった(解説を見た)。そこまで考えたならすんなり分かって欲しいのだが。

 

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

 Eまで五完。

コンテスト後のツイート


F. Stardew Valley

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

 使っても使わなくても良い辺たちの連結成分ごとに見て木DPするという方針は思いついていなかった。
 この問題が類題だったようだけど、思い出せなかった。

 ただ、この部分が解けたとしても、オイラー閉路を構築する部分で躓いていただろう。DFSして帰りがけ順に見ていけば良い(!)とは知らなかった。

G. Minecraft

 こたつがめさんの放送の振り返りを見てAC。解けなきゃいけない問題だった。

 繰り上がりの数を持ってDPする方針は問題を見てすぐ思いつたのに、繰り上がりの値が大きくなるかも、と思って実装できなかった。
 高々nになる、というのは言われれば当たり前。Fを考えている合間に見たため長いこと考えたわけではないが、思いつかなかったのは悔しい。

 なお、定数倍高速化をしないと自分のPyPyの実装では通らなかったので、コンテスト中に通すならChatGPTを活用しなくてはいけなかったかも。


2024年7月15日月曜日

yukicoder contest 436 ('09 Contest 002 day1)

 A一完。BでWAが出て、10分以上見直したがどこが間違っているか分からず、頭が働いていないと思って寝てしまった(こんなのばっかり)。


No.2804 Fixer And Ratism

 WAが出たテストケースを見て、「同時に帰った人々の名前をレートが低い人から順に出力」するなら、パソコンを使用可能にしていない人→パソコンを使用可能にした人の順ではいけないことに気付いた。

 結構気付きにくいところだと思うので仕方なかったか。

No.2805 Go to School

 自力AC。

 スタートとゴールからダイクストラですね。

No.2806 Cornflake Man

 自力AC。

 小さい順に調べていけば良さそう→0以上M以下の全ての整数について調べなくてはいけないかと思ったが、よく考えたらAに入っているものだけ調べれば良いと気付いてAC。

No.2807 Have Another Go (Easy)

 自力AC。

 確率を求めると思って答えが合わず(計算量も間に合いそうになく)悩んでしまったが、場合の数を求めると気付いたらDPでできた。

No.2809 Sort Query

 テストケースを見てデバッグしたけど方針は自力でAC。ただ、タグの「クエリ先読み」は見た。

 最初、SortedMultisetを使えばそのままできそう? と思ったけど、全くそのままではなかった。クエリの2(ソート)が与えられてから、再度クエリの2が与えられるまでの間はSortedMultisetの中身は変更せず、クエリの2が来るたびに変更するようにすれば良かった。

 

2024年7月14日日曜日

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

 Fが解けず。

コンテスト後のツイート

F - Perfect Matching on a Tree

 解説AC。

 重心で分けることはコンテスト中も考えていたが、正当性が分からなかった。主客転倒を考えるのはなるほど。

G - Count Substring Query

 以前自分で書いたAho-Corasick法の実装を参考に書き直したが、こっちの方が汎用性がある気もする。今度書くときはこっちを元にすべきか。

2024年7月13日土曜日

Codeforces Round 957 (Div. 3)

 Fまで六完。


E. Novice's Mistake

 (n, a)を定めると、bは高々一つ。また、単調なので二分探索で求めた。
 そして、その個数が少なそうなので、n=1以外のときは埋め込んだ。

 でも、n*aは高々7桁なので、二分探索も埋め込みもいらなそうですね。


G. Ultra-Meow

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

 二項係数でやる方法は考えたはずなのだけど、三乗だと思って棄却してしまった。ちゃんと計算量を見積もらないと。
 その後、nを増やしていったときDPでできるのでは? とその方針ばかり考えてしまった。

2024年7月10日水曜日

Codeforces Round #956 (Div. 2) and ByteRace 2024

 Cまで解いた後、Dをすぐに思いつかず睡魔に襲われ途中でやめてしまった。パソコンを消した後でDの解法に気付いたが実装する気力が湧かなかった。


D. Swap Dilemma

 いくつか実験したら、転倒数の和の偶奇では? と気付いた。

 まあ、見てすぐ分かるものではないし、すぐ分からなかったのは仕方ないかなぁ。

E. I Love Balls

 自力ACしたが時間がかかった。

 specialじゃないカードは交互に二人のプレイヤーにわたるので、その回数で分配すれば良い。
 specialなカードは、specialじゃないカードと一緒にわたる or 全部配り終わってからわたるのいずれか。なので、n-k+1回わたる回数があるので、それで分配すれば良い。

2024年6月24日月曜日

yukicoder contest 434

 Cまで三完。


No.2792 Security Cameras on Young Diagram

 解説AC。
 経路数の和になることには気付かなくてはいけなかった。

2024年6月19日水曜日

CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)

 Fが解けず終了。

コンテスト後のツイート

F - Easiest Maze

 何回かWAを出したが自力AC。

 解けなかったのは実装力不足のせい……といいたいところだが、Yes、Noの判定も間違っていたのはまずい。こういうのはちゃんとした確認してから実装しよう。


2024年6月15日土曜日

yukicoder contest 433

 ABの二完。Dを考えていたが分からなかった。


No.2783 4-33 Easy

 解説AC。

 「良いスコアボード条件」の最後の条件の意味が分からず困ってしまった。このまま読むと、〇Xという形は使うことないけど……→使わないのが正解でした。

 この、-4というのが分からなかったのだけど、一回に点が入るのは満塁ホームランの最大四点ということなのですね。

3 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 27X

 みたいなのものあり得るはずなのにこの式は何? と悩んでしまった。

 ただ、ここに書いてあるものだけだと、「数字+Xが9回裏に入るとき、9回表の時点で裏のチームが引き分けか負けている」という条件が抜けてないだろうか。
 このことが式に書かれているはず、と先入観を持って読んでいたせいで読解ができなかった気もする。

No.2784 繰り上がりなし十進和

 解説AC。

 線形代数っぽい見た目で、結合和として表したときに各係数が10以下で良いと気付くと解ける。
 また、DFSのようにしても良い。全部で10^6個しかないので、0からスタートしてたどりつける数字を埋めて行けば解ける。

 ただ、自分のPyPyのコードはTLEしてしまい、(Chat GPTを使い)RUSTでACした。writerさんのコードは結構余裕を持って通っているのだけど、どこで差がついているのかよく分からない……。

No.2785 四乗足す四の末尾の0

 自力AC。

 自力ではあるのだが、Nが1、-1のとき以外は素数だということの証明はできなかった。

2024年6月13日木曜日

Codeforces Round 952 (Div. 4)

 Gまで。H2はコンテスト二分後に通った。

コンテスト後のツイート

H2. Maximize the Largest Component (Hard Version)

 ツイートした解法であっていた。

 imos法をすぐに思いつけなかったのは問題だが、解法が分かってもそんなに簡単な気がしないので仕方ないかなぁ。

2024年6月9日日曜日

サントリープログラミングコンテスト2024(AtCoder Beginner Contest 357)

 Eまで五完。

コンテスト後のツイート

F - Two Sequence Queries

 自力AC。

 コンテスト中、遅延セグメント木を使えば解けると気付き、十分時間もあったのに解き切れなかった。
 いい加減に実装して数値を合わせようとするのではなく、ちゃんと、何が何個足されるのか考えてから実装すべきだったか。


2024年6月7日金曜日

yukicoder contest 432

 全完。Hで詰まったけれど、どうにかACできたのは良かった。

コンテスト後のツイート


Codeforces Round 951 (Div. 2)

 Dまで四完。

コンテスト後のツイート

E. Manhattan Triangle

 ツイートした解法で良かった。コンテスト終了一分後くらいに書き終ったものを提出してAC。

 Unratedだから笑い話で済むけど、Ratedでこういうことをしたら悔し過ぎるので、もっと集中しよう。

2024年6月5日水曜日

Codeforces Round 950 (Div. 3)

 F1まで。

コンテスト後のツイート

F2. Field Division (hard version)

 自力AC。

 コンテスト中に考えていた方針であっていたが、実装が大変だった。Gに行かずF2に集中していたらギリギリ間に合っていたかなぁ……。


G. Yasya and the Mysterious Tree

 Binary Trieを使うということを参考にAC。

 ただし、コンテスト中は誤読しており、xorではなくorを計算するものと思っていた。これがなかったら解法を思い付いていた気がする。

 ただし実装には非常に苦戦した。
 自分のTrieだとTLEで通らず、Chat GPTによりC++へ書き換えると、エラーが起きてしまい、どこが間違っているか分かるまで一時間以上かかった。

 偶奇に分けて要素たちをBinary Trieに突っ込み、毎回自分の要素を減らした上で最適なものを探すのだが、要素数が0になっていたときの処理を怠っていた。
 Pythonのコードもバグっていたはずなのだけど、PythonだとLIST[-1]というのでエラーが出ないため、たまたま合ってしまっていたんですね……。

 修正してなんとかAC。
 ただ、C++でも制限時間ギリギリだったので、Trieの書き方に問題がありそう。Binary Trieをちゃんと書かないといけないのかな。

2024年6月3日月曜日

AtCoder Beginner Contest 356

 Eまで五完。

コンテスト後のツイート

F - Distance Component Size Query

 解説AC。特にevimaさんの動画を参考にした。

 セグメント木とSortedSetを使い、二分探索で頑張れば解ける。「ある数と右隣の数が繋がっているか?」という配列をもとう、と思えるかがポイントか。

2024年6月1日土曜日

Educational Codeforces Round 166 (Rated for Div. 2)

 Dまで四完。

コンテスト後のツイート

E. Splittable Permutations


 クエリで与えられた数字が一意に並ぶことは分かっており、その間に余った数字を入れていくと考える部分もあっていたが、その条件が分かっていなかった。

 ただ、並べる部分を再帰を使って書き、その書き方だと二乗になっていることに気付かずなぜTLE・MLEするか分からず随分悩んでしまった。
 こういう実装はすらすらできるようにならないと。

F. Remove Bridges

 こたつがめさんの放送や実装を見てAC。

 解法は面白かったが、それだけだと実装が分からずこたつがめさんの実装を見る。すると、「各葉について、消された頂点までの距離」(この説明は意味不明だが……答えを得るのに必要な配列のことです)がdfs一発で求められていることに驚いた。言われてみれば分かるが、葉を中心に考えていたため思いつかなかった。

 ただ、そのままだとPyPyの再帰がメモリを食うため通らず、非再帰に直してAC。木DPを使うと非再帰に直せた。

yukicoder contest 431

 ABの二完。 

No.2767 Add to Divide

 テストケースを見てAC。

 「B-Aの約数がA+Xになる」でXを絞る方針でコードを書いたがWA。ランダムテストを回したが落ちるケースがなく途方にくれてしまった。

 テストケースを見たところ、A=Bで落ちていると分かってAC。全然気付かなかったなぁ。

No.2768 Password Crack

 自力AC。

 これは簡単だけど、もっと質問回数を減らせるとは気付いていなかった。

No.2770 Coupon Optimization

 自力ACだが結構苦戦してしまった。

 畳み込みなのでFFTしようとしたが、numpyによるFFTの方法を忘れており、numpy.fft.fft(A,k)のkの値の足りないコードを書いてしまった。最終的にできる配列が基準だから、今回はk=1<<19が必要。

 畳み込みを使わなくても解けるらしいことには気付かなかった。

2024年5月31日金曜日

AtCoder Regular Contest 177

 Cまで三完。

コンテスト後のツイート

D - Earthquakes

 連結成分ごとに分けて考えて良いということを元に考察し直してAC。
 「連結成分ごとに分けて考えて良い」ことさえつかめていれば、後のステップは「その柱が倒れたとき、その連結成分に含まれる柱が全て倒れる確率」を求めるという方針で良く、結構シンプルだった。

 ただ、実装は大変で、答えが0になるときの処理をどうするかでかなり困った。どちらかというと考察より実装にウェイトのある問題だったと思うので、考察で詰まったのは良くない。

2024年5月28日火曜日

Codeforces Round 946 (Div. 3)

  Fまで六完。G、コンテスト後に考えていたけど結局自力で解けず。

コンテスト後のツイート


G. Money Buys Less Happiness Now

 コンテスト後も考えたけど分からず、こたつがめさんの放送の振り返りを見てAC。

 DPの高速化や、Cを小さい順に使うことばかり考えてしまった。


2024年5月26日日曜日

東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)

 Dまで四完。

コンテスト後のツイート

E - Guess the Sum

 解法ツイートなど見てAC。

 質問回数の最小値を求めるのが本質なのだが、インタラクティブ問題なこともあってそれに気付きにくい。
 最短距離を求めると思えたら難しくないが、問題の見た目からセグメント木を何かする問題に見えてしまいやすい。そう思うと解けなくなってしまう。

 同じ罠にハマった人が多かった模様。

 これ、発想力の問題だから、ARCで出して良かったのでは?

F - MST Query

 解説AC。

 制約に重みが10以下とあるのは気付いていたが、どう利用すれば良いか分からなかった。順位表で多く解かれていたのを見て、もっと汎用的な方法があるのだろうと思い、検索に時間をかけてしまった。
 Link-Cut treeについても勉強しないとね。
 



2024年5月18日土曜日

yukicoder contest 430

 A一完。Bが全然思いつかないのは頭が働いていないせいだと思い、寝てしまった。


No.2758 RDQ

 解説AC。なんか、思ったより難しかった。

 やれることが約数列挙くらいしかないので、約数列挙して何かしようと思うのは良いが、何をすれば良いか分からなかった。
 約数ごとにやろうと思ったら、クエリごとにindexの二分探索で答えが求められるとは気付いかなかった。

No.2759 Take Pictures, Elements?

 自力AC。

 Aの各要素についてLISTを作り、二分探索により解いた。「移動候補が複数ある場合、左右でもっとも近くにある場所への移動が最適」なことを利用している。

No.2760 not fair position game

 自力AC。
 いわゆる真似っこ戦略で解けました。

2024年5月14日火曜日

AtCoder Beginner Contest 353

 Fが解けず六完。

コンテスト後のツイート

F - Tile Distance

 K=2の場合をケアしてAC。
 Kが小さい場合に問題が起きそう、とは思ったから時間があれば解けたと思うので、Gに時間がかかり過ぎたのが敗因。

 ただ、K=2の場合をケアしたつもりがWAが二個でてしまい困った。
 これは、最初の方にしたK=2の場合は嘘になる考察をコードに入れっぱなしにしていたせいだった。考察に漏れがあったなら、コードも見直さないと。


Kotlin Heroes: Episode 10

 Fまで六完。またもT-shirts圏に入れず。

コンテスト後のツイート


H. Composite Spells

 各魔法について、その魔法を使ったときのHP増減と、その途中のHP増減の最小値(つまり、最大ダメージ)を持って計算していけばOK。

 コンテスト中この方針で書いたがWAが出て、何が原因か分からず迷走してしまった。

 コンテスト後、解法ツイートを見て、LongをBigIntegerに直したらAC。

 Kotlinって標準で多倍長整数使えると知らなかった。
 Longで収まる範囲の問題しか出ないと思い込んでいたのが敗因。Longで収まると思い込んでいたからoverflowは考えなかった。



2024年5月13日月曜日

Codeforces Round 944 (Div. 4)

 最後の問題が解けず。


H. ±1

 2-SATという情報を得てAC。

 この前のABCでは2-SATじゃないかと嘘考察してハマったのに、実際に2-SATが出たら解けなかったのは情けない。
 ただ、最初見たとき2-SATは疑ったので、時間があって落ち着ければ解けていたと思う。

2024年5月7日火曜日

yukicoder contest 291

  ABの二完。Bで唖然とするようなミスをして、Cも分からぬまま終了……。


No.1478 Simple Sugoroku

 自力AC。

 ワープを使う場合、「後ろx個へワープで辿りつけたらそこからは歩く」という戦略を取るのが良く、このxを全探索すればOK。

No.1479 Matrix Eraser

 フローの練習で解いた。自力でグラフは構築したがTLEが取れず、他の人の提出などを見てAC。

・start→縦でまとめられるもの→(i, j)→横でまとめられるもの→goal

 というグラフを考えたが、これだとMLE・TLEしてしまった。
 (i, j)の部分は省略することが可能。また、A[i][j]の値ごとにflowを流せば良いので、H+Wの大きさのflowをHW回流す感じで解ける。
 こうすればACできた。

 ただ、言語とかDinic法の実装とかで工夫したら最初の方針でもACできたはず。そういうライブラリも持っておきたいね。

Educational Codeforces Round 165 (Rated for Div. 2)

 Dまで。

コンテスト後のツイート

E. Unique Array

 解説AC。

 このG問題の類題で、似た解法で解ける。

 各要素が唯一である区間を長方形と思って管理するところまでは同じ。その後、それを使って貪欲に処理していく。

 最近解いた問題なのに、コンテスト中も、今復習しようとしたときも全く思い出さなかったのはひどいのでは。

2024年5月5日日曜日

AtCoder Beginner Contest 352

 Eまで五完。

コンテスト後のツイート


 F - Estimate Order

 解説AC。

 重み付きUnion-findで連結成分ごとにまとめた後、bit DPする。bit DP部分をDFSっぽくやって高速化した。

 コンテスト中もまずbit DPできないか考えたはずなのだが上手くいかない気がし、2-SATでいけると勘違いして突き進んでしまった。「どれか一つが真」って条件は2-SATで表せないですね。

 色々ひどかったけど、2-SATの復習は多少できたかもしれない。

G - Socks 3

 解説AC。

・前半の、期待値を場合の数に置き換えるパート
・後半の、場合の数を多項式の積で表し、形式的べき級数で計算するパート

 どちらも典型なのだが、身に着いていない。


 どちらかというと、後者は問題演習を積めば身に着く気がするので、前者の方がより身に着けたい内容か。期待値を、「i回以上である確率P_i」の和で表すという方法は覚えておきたい。

2024年5月4日土曜日

Codeforces Round 942 (Div. 1)

 B2まで。CombinedじゃないCodeforces Div. 1はちょっと避けたりしていたけど、今回は参加。レートが落ちず良かった。

コンテスト後のツイート


 C. Fenwick Tree

 解説AC。

 各成分の、k回後に対する寄与が二項係数になるということに気付けなかった。それが分かればすんなりAC。

 なお、コンテスト中考えていた解法だとΣのベキ乗の係数が必要そうになったのだが、その方向でも正しい答えを得る方法はあったらしい(が、理解できていない)。

Codeforces Round 943 (Div. 3)

 時間ギリギリ全完でした。

 G2の方針自体はもっと速く思いついていたんだけど、これで計算量が良いかで迷い、またSortedSetを使わなくては実装できないのか?(使ったらTLEするのでは?) といったあたりでも迷って時間かかってしまった。
 あと、並列二分探索でできないか? などとも考えた(できなかった)。

 実際に実装してみたらACでした。

コンテスト後のツイート







2024年4月28日日曜日

AtCoder Regular Contest 176 (Sponsored by Mynavi)

 Cまで三完。ARCでこれくらいの順位が取れると嬉しい。

コンテスト後のツイート

D - Swap Permutation


 解法ツイートで行列累乗で解けるというのを目にしたが、ある(a,b)というペアが最終盤面でどのような位置にあるか? という遷移を考えてしまい、上手くできなかった。

 index i, i+1が最終的にどの数字になっているか? に着目するのは言われてみれば自然。コンテスト中に解けなかったのは仕方ないにせよ、行列累乗で解けると言われたら思いつきたかった。

E - Max Vector

 解説AC。

 問題を読んでフロー(最小カット、燃やす埋める)じゃないかとは思ったが、どうやってグラフを作れば良いのか。

 とりあえず、

・Nが多いことはあまり本質的ではない。N=1の場合に関するグラフを構築すれば、一般のNでのグラフも(今回は)同じように構築できる。
・X_i+Y_iなどというのはフローで扱いにくそうだし、X_j, Y_j, A_ijが500以下という条件があるので、各数字に関する頂点を作りそう。

 というあたりを手がかりにすれば良かったか。

 ただ、劣モジュラ関数についての一般的な知識は得ていた方が良いのは間違いない。theory and meさんのこの記事を理解すべきだよね……。

2024年4月25日木曜日

Educational Codeforces Round 163 (Rated for Div. 2)

 Eまで五完。

コンテスト後のツイート

F. Rare Coins

 解説AC。

 自分になじみのない解法が必要かと思って解説を見たのだが、普通の方法で解けた。

 ちゃんと問題を整理し、1/2の確率で自分のお金が増える、相手のお金が増える、というのを元のお金を調整して、「1/2の確率で差を減らす」と解釈するとシンプルな二項係数の和になる。










2024年4月23日火曜日

Codeforces Round 940 (Div. 2) and CodeCraft-23

 Dまで四完。ARCの後だったこともあり、前半は休み休みやっていた。

コンテスト後のツイート

E. Carousel of Combinations

 解説AC。

 Combi(n, k)*(k-1)! mod k の和を求める問題。実験コードを書いてこれを計算してみると、k=4と素数のとき以外は0になること、かつ、規則的に値が変化することが分かる。kを固定したとき、最初に値が正になるのはn=kのときで、k-1。そこからkごとに-1し、0になったらまたk-1に戻る。(これはkが素数のとき。k=4は2と0を交互に取る)

 これが分かった後、埋め込みか? などと考えてしまい解説を見てしまったが、累積和を二回やるのが正しかった。規則的に値が変化するのだから、累積和を考えるのは自然。

 大体解けたけどTLEが微妙ってとき、変な手法を考えてしまうのは悪い癖。まともに計算量を減らす手法を考えるようにしないといけない。






2024年4月22日月曜日

AtCoder Beginner Contest 350(Promotion of AtCoderJobs)

 G解けず。Fで苦戦したため順位は悪い。

コンテスト後のツイート

G - Mediator

 解説AC。

 マージテクで解いた。コンテスト終盤にマージテクが使えるんじゃないか? というアイディアは思いついたけど、具体的な解法には思い至れなかった。