2022年7月31日日曜日

AtCoder Regular Contest 145

　Cまで三完。

　ARCは初手で実験することが多いのに、実験しなかったために失敗したのは良くなかった。Cは実験しなくても解けそうな気がしたため最初しばらく実験せず。Dは実験して良い性質が得られると思わなかった。

コンテスト後のツイート

D - Non Arithmetic Progression Set

　解説AC。
　良い整数集合を構築した後、最後の一個で調整する方法で解いた。

　初手で、貪欲にSを構築（実験）→oeisしてみる、もしくは、検索してみるべきだった。そうすれば、Sがどんな性質を持つかは分かったはず。（残り時間は30分ほどあったので、そうやって考える時間は残っていた）
　ACできたかは分からないが、実験もせずに終わったのはダメ。反省。
時刻: 0 件のコメント:
ラベル:

2022年7月30日土曜日

yukicoder contest 354 （オムニバス

　Cまで三完。


No.2024 Xer

　解説AC。

　Aをソートして、それが条件を満たすかどうか、だとサンプル4が合わない。

　ただ、このように必要条件で絞る方針は間違っていなかった。
　何でソートすれば良いかは、与えられた不等式から考えるか、実験して考えるか、くらいか。どちらにせよ思いつくのは不可能ではなさそう。時間があれば試さなくてはいけない解法でした。
時刻: 0 件のコメント:
ラベル:

2022年7月28日木曜日

AtCoder Beginner Contest 261

　Gを除く七完。

コンテスト後のツイート

G - Replace

　解説放送を見てAC。

　難しい。
　TからSに戻すと考えると区間DPにできるということが気付きづらいし、それだけだと一文字同士の処理で上手くいかないというのも気付きにくい。
　また、計算量が五乗になるのにTLEにならないというのも意外に感じた。

　一つ一つの考え方自体は難しくないのは確かなのだけど、ACした後でも簡単という気がしない。
　単純なDPでも、DPにもつ配列が二乗、三乗……となると途端に難しくなるから、こうやってちょっと複雑なことが組み合わさるとなかなか整理しづらくなるのが厳しい。
時刻: 0 件のコメント:
ラベル:

2022年7月25日月曜日

yukicoder contest 353 （オムニバス）

　Cまで三完。D、解説読んでも難しい気がしたけど、こんなに解かれるんだなぁ。


No.2017 Mod7 Parade

　解説AC。

　まず、10^x mod 7が6周期だということを押さえておく。そして、mod 7を考えるので、各数字のmod 7も高々7個。

　これを利用して、

・DP[i][j]で、桁数 mod 6がi個、答え mod 7がjとなるものの個数

　というDPを考える。
　下の桁から追加していくとき、その数字を追加するか、しないか、で遷移は二通り。なので、計算量も抑えられている。
　なお、上の桁からやると桁数を覚えなくても解け、計算量も下がる（というツイートを発見）。確かに！

No.2018 X-Y-X

　解説AC。

　かなり賢い解法に思えるが、隣接要素のxor（差）を考えるのは定石の一つだし、そうして帰着した問題を見ると、偶奇で分けて片方反転させるのも定石。
　迷うのは仕方ないけれど、色々試している間に解けるべきだった。

No.2019 Digits Filling for All Substrings

　これは自力でACできた。
　mod 3でDPすればOK。

　No.2017 Mod7 Paradeと似た解法だけど、こっちの方が大分思いつきやすく感じた。コンテストの問題順が、No.2019 Digits Filling for All Substrings→No.2017 Mod7 Paradeとなっていたら、似た解法の応用問題が後に出題されている、という感じで良かったと思うけれど、全体テスターがいないから仕方ないね。


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

2022年7月23日土曜日

Codeforces Round #808 (Div. 1)

　A一完で終了。Aはまあまあ早かったのだが。

コンテスト後のツイート

B. Difference Array

　解法ツイートを見てAC。

　sum(a_n)に関する制約があるのが怪しい。それを利用できないか考える。
　実際に操作をしてみると、すぐ、大半の要素が0になるのは分かる。ので、0の個数を管理して、他は愚直に操作すればOK。

・大半が0になること
・こういう問題では上手い方法はなくて、基本的には真面目に操作を行うしかなさそうなこと

　には気付いていたのに、解法へたどりつかなかったのは良くない。ただ、解法の鍵となる部分は分かっていたので、それ以上反省するのも難しい……。

C. DFS Trees

　解説AC。

　まず、ツイートした解法は間違っていました。問題で与えられたアルゴリズムを勘違いしていました（重みではなく、indexの小さい方からdfsするかと思っていた）。

　これを踏まえると、「MSTに入らないedge x-yについて、xとyの間にあるような頂点はダメ」だけでOK。これをどう実装するかが問題。

　これは、木上のimos法で解ける、という解法ツイートを見て、以下のようにできると分かりました。子孫全てにある値を足す、というのをimos法を使って処理しています。

・頂点xとyのLCAがxでもyでもないとき、xの子孫、およびyの子孫に+1する。
・頂点xとyのLCAがxのとき、yの子孫に+1、xの子でyの先祖であるような頂点kの子孫に-1する。頂点kはダブリングを使えば求まる。

　一つ目の方法では、答え(findMST(i)=1となる)の候補となる頂点に+1しており、二つ目の方法では、答えにならない頂点に-1しています。ので、全て処理した後、値がmaxと一致している頂点たちがこの答えになります。


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

2022年7月22日金曜日

Codeforces Round #807 (Div. 2)

　遅れて参加してDまで。

コンテスト後のツイート

E. Mark and Professor Koro

　解説は理解したけど、PyPyではTLEが取れず。（一人ACしている人がいるけど、どうやっているのかよく分からない）

　結局、遅延セグ木を使って筆算の繰り上がりをシミュレートする問題になる。
　ただ、1が立っている最上位の桁などを二分探索で求めなくてはいけない。この辺、セグ木上の二分探索をちゃんと実装していればlog一個になるのだろうけど、自分の提出はlog二個のままです。（遅延セグ木の二分探索は、実装したことはあるけれどライブラリ化していなかった）
　log一個に直したら通る可能性はあるけど、他の提出が通っていないのを見ると、実装する気になれません……。
時刻: 0 件のコメント:
ラベル:

2022年7月20日水曜日

AtCoder Beginner Contest 260

　Eまで五完。

コンテスト後のツイート

F - Find 4-cycle

　解法ツイートを見てAC。

　Tが3000以下というのが怪しい。これをどう使うか、という問題。
　コンテスト中は、Tの二重ループでどうにかすることしか考えなかった。が、鳩ノ巣原理を使うならTの組に対して何かを割り当てることになる。

　その両面を検討しなくてはいけなかった。

G - Scalene Triangle Area

　自力AC。

　imos法を頑張る、としか言いようがない！
　斜めにimos法をしたり、その斜めの累積和を途中で切り上げたりするのを書かなければならず混乱するけれど、頑張るしかない。
時刻: 0 件のコメント:
ラベル: ,

2022年7月19日火曜日

AtCoder Regular Contest 144

　Cまで三完だが、遅かったためレートを下げた。解いている最中はそれほど遅い気がしなかったのに、順位は悪かったので、（自分では分からなかったが）体調が悪かったのかもしれない。

コンテスト後のツイート

D - AND OR Equation

　解説ACだが、今見返すとチャンスはあった。

　実験してoeis（これやこれなどが出てくる）と見比べれば${(1+x)}^N/{(1-x)}^{(N+2)}$の$K$次の係数と分かる。

・${(1+x)}^N$は、二項定理を使って展開
・${(1-x)}^{(N+2)}$は、$1/(1-x)=1+x+x^2+x^3+...$とできることを利用すると重複組み合わせにより二項係数になる

　を利用すれば求められる。
　ただし、二項係数を求めるとき、Kが998244353に近い値のときは気をつけて計算しなくてはいけない。（コンテスト中に、ここの処理まで上手くできた可能性はかなり低そう……）

　コンテスト中、形式的冪級数で表すところまではできていて、その後は多少技巧的ではあるが自分で思いつける変形だった。
　特に一番目、二項定理を使おうとも考えなかったのはひどい。形式的冪級数を使うならここは押さえねば。
時刻: 0 件のコメント:
ラベル: ,

2022年7月16日土曜日

yukicoder contest 352

　A一完。睡魔に襲われたせいでB以降あまり考えられなかったけど、眠くなかったとしてもBが解けたかどうかかなり疑問。 


No.2008 Super Worker

　解法ツイートを見てAC。

　まあ、何かでソートするんだろうな、とは考える。
　何でソートするか調べるために立式するのだが、そのとき、次にする二つのアルバイトを比較するのが重要。3項以上の和を考えるのではなく、次の二項の順番を違えた場合の式を比較する。そうすれば何でソートすれば良いか分かる。

　二項での比較でそうなるのは分かったけど、どうして三項以上でもソート順でいいのか？　というのがしばらく分からなかった。けどこれは、二項ごとに隣接swapを繰り返すとソート列が作れるというのと同じ理屈ですね。
時刻: 0 件のコメント:
ラベル:

2022年7月13日水曜日

AtCoder Beginner Contest 259

 　Fまで六完。

コンテスト後のツイート

G - Grid Card Game

　解説AC。（解説放送も見た）

　コンテスト中、いわゆる「燃やす埋める問題」ではないかと疑ったりもしたのだが、違うと思ってしまった。

・start→行のノードたち→列のノードたち→ゴール

　みたいなグラフを考えていたのだけど、

・start→行および列のノードたち→ゴール

　を考えるのが正解。「燃やす埋める問題」を思ったなら、そういうグラフを考えるのは当然なはずなのに、捨ててしまったのはまずい。
　こういうグラフ構築と、「燃やす埋める問題」では「Xを選択してYを選択しない場合のペナルティ」を見ていく、という点は頭に入れておきたい。

　その後の処理もテクニカルだけど、この系統の問題になれていれば突飛な考え方ではない気がする。類題経験を積んだ方が良さそう。

Ex - Yet Another Path Counting

　解説放送を見てAC。

　二通りの四乗の解法がある：

・同じラベルの二点全てについて二項係数を足す
・多点スタートのDPをする

　各ラベルの個数によりこれらを使い分けることで三乗になり、ACできる。
　コンテスト中は一番目の方法しか思いつけなかった。二つ目も見たことあったのに。
時刻: 0 件のコメント:
ラベル: , ,

Codeforces Round #806 (Div. 4)

 　Div. 4で全完できなかったのは初めてだと思うのでショック。

コンテスト後のツイート

G. Good Key, Bad Key

　他の人のコードを見て理解し、AC。

　ただ、コードを見てもすぐには理解できなかった……。ランダムケースで実行して、自分のコードが負を吐く場合があることに気付き、理解できた。

　しかし、このことに気付けなかったのはひどい。このケースを書かないというのは、「何回badな鍵を使ったかもってDP」という正当性が理解できていないこととほとんど同じだ。（いや、最初考えたときは理解していたはずなのに）

　答えが負になるはずがない、ということは分かっていたので、コンテスト中もランダムケースを実行すべきだった。Nが小さい場合の愚直を書いて比較したりしたが、Nが小さければ答えが一致してしまうため、今回のミス発見には至れない。
　そこから、Nが小さい場合は上手くいっているみたいだから、Nが大きい場合に何が起こるか考えよう（もしくは、Nが大きい場合のランダムケースを実行してみよう）、と思うべきだった。


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

2022年7月12日火曜日

Codeforces Round #805 (Div. 3)

　苦労したけど全完できた。

コンテスト後のツイート

　Fの既出には気付かなかった。
　EやGはもっと簡単な方法があったらしいが、理解していない。
時刻: 0 件のコメント:
ラベル:

2022年7月10日日曜日

Kick Start Round D 2022

　Cで詰まって解き終わらないかと思ったけど、全完できて良かった。

コンテスト後のツイート



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

2022年7月8日金曜日

2022 TCO Algo Round 3

　0完、チャレンジもできず敗退しました。


Easy TwoDimensionalSort 

　解法ツイートを見てAC。

　一つ一つ文字を揃えていこう……と考えていくと失敗する。
　せっかく26*26あるので、もっと盤面をめいっぱい使う方法はないだろうか。

　全ての文字の行数のみソートされていれば良いので、そうするためにどうすれば良いだろうか？　と考える。すると、

・全ての文字の列数をdistinctにする

　ことさえできれば後は簡単だ。と、思いつける、のだろう。

　これが思いつかなかったため解けませんでした。
時刻: 0 件のコメント:
ラベル:

2022年7月6日水曜日

AtCoder Beginner Contest 258

　Eまで五完。

コンテスト後のツイート

F - Main Street

　自力ACだが時間かかってしまった。

　（K=1の場合を除くと）スタート・ゴールそれぞれから、直線で大通りに出る4通りを考えれば良い。その16通りを考えて最短のものを出力する。

　(スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bのときを気を付けるのが重要。このときはマンハッタン距離が答えにならないのに注意して実装する。

　基本的にはこれだけなのだが、自分が詰まったところを書いておく。

・if (スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bのとき
・else if (スタートから大通に出たときのy座標)/B=(ゴールから大通に出たときのy座標)/Bのとき

　のように実装し、それぞれ迂回して行く最短距離を考えると、「(スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bかつ(スタートから大通に出たときのy座標)/B=(ゴールから大通に出たときのy座標)/Bのとき」のときおかしくなる。

　このときはマンハッタン距離で良いことに長い時間気付けなかった。

G - Triangle

　解説AC。

　bitsetを使っても、bit_count(popcount)を高速化できないと意味がない。bit_countの高速化はこのスライドが詳しい（とtoamさんの解説に書いてあった）。
　予め63個ずつに区切っておき、それぞれについてこのスライドの方法でbit_countを求めるとTLEせず求められる。

Ex - Odd Steps

　解説放送を見てAC。

・Aを無視してDPを立式
・累積和を取ると式が簡単になる。行列累乗が使えそう
・A以外の部分は行列累乗で処理、Aのところだけ普通にDPする

　という流れ。

　上記のステップを経れば難しくないのだけど、Aが重要そうな問題で、Aを無視して処理することが解法に結び付くというのは意外だった。
　何も思いつかなければとりあえずDPを考えてみるのは重要か。
時刻: 0 件のコメント:
ラベル: , ,

2022年7月5日火曜日

Codeforces Round #804 (Div. 2)

　Cまで三完。


D. Almost Triple Deletions

　解説AC。

　（3WAを出した後、乱択解を書いて比較して）区間DPか？　とは思った（DP[i][j]で、A[i]=A[j]のとき、A[i]やA[j]を残すなら最大何個残せるか、などと定義）のだが、三乗以上の時間がかかってしまいそうで、どうやればDPを回せるか分からなかった。

　ここで、

・ある区間[l, r]が消せるのは、その区間に含まれる一番多い数の個数が半数以下のとき

　であることに注目。（このことはコンテスト中気付いていた）
　これを前計算するのは二乗で済む。

　これを用いてDPしようと思えば、区間でDPを定義しなくて良くなる。

・DP[i]=A[i]を残したとき、区間[0, i]でA[i]を残せる個数の最大値

　とすれば、DPが回る。
時刻: 0 件のコメント:
ラベル:

2022年7月2日土曜日

yukicoder contest 350

　Dまで四完。Eは解けなくちゃいけなかった。


No.1996 <><

　自力AC。

　DPするしかなさそうで、愚直にやると三乗になる。これを（累積和などを使って）高速化しなくてはいけない。

　そこで詰まって分からなくなってしまったが、実際は座標圧縮してBITを使うことで計算量を下げることができる。

　典型ではあるけれど、ここは考えなくてはいけない部分。思いつけなかったのはまずい。

No.1997 X Lighting

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

　重複を含めて数えた後、交点の分を引くという方針は思いつくが、どちらも正しく計算するのは結構面倒。答えを合わせるのにかなりの時間がかかった。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)