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 件のコメント:
ラベル: ,
登録: 投稿 (Atom)