2022年2月28日月曜日

AtCoder Regular Contest 136

　ABDの三完。

コンテスト後のツイート


C - Circular Addition

　解説AC。
　何を反省すべきか難しい……。

　「隣接項の差」を思いつかなかったのがダメなのだけど、どうしたら思いつけたか。愚直解は書くべきだったかもしれないけど、それで気付けたかと疑問。
時刻: 0 件のコメント:
ラベル:

2022年2月19日土曜日

yukicoder contest 332

　ACDの三完。


No.1842 Decimal Point

　このAの類題なんですね。当時解けてたのに忘れていた。
　立式の仕方はちょっと違うけど、「とりあえず立式」するしかない問題。

　ただ、
・$A*10^C$を$B$で割った式
・その余りを$10$で割った式（この余りが答え）

　の二式を書いても、直接、$A*10^C$を$B*10$で割れば良い……と分かるわけではなさそう？（これくらいしかできることはないとはいえ、若干の発想が必要な気がする）

　これに加えて、

・$A*10^C$を$B*10$で割った式

　を書き、見比べれば、この余りをBで割った余りが答えになることは示せる。
時刻: 0 件のコメント:
ラベル:

2022年2月14日月曜日

AtCoder Regular Contest 135

　Cまで三完。

コンテスト後のツイート

D - Add to Square

　解説AC。

　市松模様に分けて片方の正負をひっくり返すと、各行・各列の総和が一定になる、と気付くのが重要。
　そう言われても「なんで気付けるの？」って感じだけど、「不変量を探そう」という気持ちを持って実験（特に、一次元の場合などを考えたり）すれば不可能ではなかったと思う。
時刻: 0 件のコメント:
ラベル:

2022年2月12日土曜日

yukicoder contest 331

　ABの二完。

コンテスト後のツイート

No.1837 Same but Different

　解説AC。
　「mod 3を考える」というのは思いつかなければいけなかった。その後の方が難しいのかもしれないけど、まずこれを思いつかないと勝負にならない。
時刻: 0 件のコメント:
ラベル:

2022年2月9日水曜日

yukicoder contest 330

　A一完。途中で睡魔に襲われてしまったけど、時間あってもBやCは解けなかったかも……。


No.1830 Balanced Majority

　解説AC。

　制約から二分探索を使うことは大体明らかで、どうやってそこへ持ち込むか。

・1～x番目までの表の枚数 - 裏の枚数

　を考えるという発想はあったが、それを利用するために、最初の一枚と最後の一枚が何か確定させておくとは思いつかなかった。

No.1831 Parasol

　時間はかかったけど自力AC。

　奇数xを、1+(x-1),  2+(x-2), 3+(x-3), ... と分けると気付けたら解ける。

No.1832 NAND Reversible

　解説AC。

　NANDに関する規則（末尾の1の個数だけで決まる）に気付かなかった。ちゃんと実験すれば気付けるはずなので、手を動かさなくちゃダメ。
　その後、場合の数の求め方にも戸惑ったのはまずい。これはさくっとできなきゃいけなかったはずなのだけど、和がaのとき……と考えず、左端が何個とき……と考えてしまったのがまずかったか。ちゃんと立式すれば分かったかなぁ。
時刻: 0 件のコメント:
ラベル:

2022年2月8日火曜日

Codeforces Round #770 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Fair Share

　解説AC。

・グラフに帰着→オイラー路問題へ

　そもそも二分グラフにするということが思いつかなかった。
　なかなかの発想が必要な気がしたが、結構解かれているので、これくらいは思いつかなくちゃいけないみたいだ。

F. Fibonacci Additions

　解説ACしたが、なぜこれで良いか分かってないのでもう少し考える。

　→読んで、一応理解しました。

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

AtCoder Beginner Contest 237

 　FHが解けず六完。Eが嘘解法だった。

コンテスト後のツイート

E - Skiing

　楽しさの変化を距離とみなしてダイクストラと考えて、負辺があるけど大丈夫そうな気がして投げたら通ってしまった。after_contestで落ちたのは納得。

　正しい解法は、登るときだけ標高差をコストとみなして、ダイクストラ。そして、全頂点探索し、スタート地点との標高差で楽しさを計算。というのは、言われれば分かるけど、なかなか思いつきにくい印象。
　コンテスト中、TLEが返ってきたら、解けていなかった気もする。

F - |LIS| = 3

　これは通せなくてはいけなかった。
　LISのDPを考えたとき、各長さのLISの最後の値の最小値を持ってDPする。それをそのまま持てば良い。

　コンテスト中はなぜか、各文字が最後に来るような最長のLISの長さは？　と考えてしまっていた。これだと$4^10$もたなければいけないので、間に合わない。

Ex - Hakata

　解説放送を見てAC。

・Dilworthの定理：推移的なDAGについて、最大独立集合（任意の二点に辺が存在しない頂点集合の最大サイズ）と最小パス被覆の本数が一致する

　を用いて、フロー（mincut）の問題へ帰着するところが難しい。

　ただ、回文を列挙した後、グラフの問題として見てみたら、フローの雰囲気を感じ取ることはできてもおかしくないか。
　
時刻: 0 件のコメント:
ラベル: ,

2022年2月7日月曜日

モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）

　Eまで五完。

コンテスト後のツイート

F - Two Exams

　「ソート」というキーワードを見てAC。

　$P_x>P_y$かつ$Q_x>Q_y$を満たす$(x, y)$の組は少ないから、とりあえず列挙してグラフの問題にしようか、と考えると難しい。
　トポロジカルソートを使うのかな、などと考えてしまいやすい。ツイッターを見ても、同じ罠にハマった人は多かったよう。

　二次元平面に$(P_i, Q_i)$をプロットして平面走査っぽく考えてみると、ソートしてDPという方針が自然と思い浮かぶ。

　一般化しすぎて解けない問題に帰着してはダメ。今回は特に、一見解けそうに見えるからハマりやすかったんだと思う。
　解けないかも？　と気付く嗅覚（知識）と、もう一度元の問題を振り返ることが重要。

G - Cubic?

　解説放送を見てAC。

・区間→累積和（今回は累積積）を考える
・ハッシュ化

　と考える問題で、ハッシュ化の仕方が難しい問題だったはずだが、コンテスト中は一点目で詰まっていた。セグメント木でどうにかならないかと考え、もっと簡単な累積和でどうにかできると気付けなかった。

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

2022年2月4日金曜日

Codeforces Round #743 (Div. 1)

　Unratedになった回。


B. Xor of 3

　解説AC。
・操作によって全体のxorは変わらない
・列の長さnが奇数のときは、index 1, 3, 5, ...　,n-2 とした後、n-4, n-6, ... ,1とすれば全て0にできる

　と気付くのが重要。
　一点目はまあ気付くけど、二点目はなかなか気付きにくい。
時刻: 0 件のコメント:
ラベル:

2022年2月2日水曜日

AtCoder Regular Contest 134

　Dまで四完。

コンテスト後のツイート

E - Modulo Nim

　解説AC。

　初手実験は悪くなかったが、実験コードをもっと高速化しなくてはいけなかった。敗北パターンを考えるとき、「全て12の倍数」のときだけダメ、ということに気付くのは実験するのが一番だろうので、あまりにも愚直なコードではなく、多少は考えて実装するべきだった。

　「全て12の倍数」のときに絞れば、敗北パターンを全列挙できる。これも実験コードで行ったが、自分のコード（多少考察を加えたものでも）だと時間がかかり過ぎている（コンテスト中にこの実験をしていたら間に合わなかったと思う）。
　手元のPCにもPyPyは導入したはずなので、それを使うべきだったか？

　あとは、bitDPしてAC。

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

2022年2月1日火曜日

キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)

 　Dまで四完。


E - Swap

　解説放送を見てAC。（解説方法後半の賢い方法で書いた）

　制約を見ると全探索は無理そうなので、DPを疑ってはみたがどのような状態を持てばいいか全く分からなかった。

　言われてみれば当たり前なのだけれど、何も思いつかないなら、「一文字目から決めていこう」と考えるべきでした。そうすれば、Swapがテーマなので転倒数が重要そうなのは分かるし、他に何をキーに持てばいいか、というと各文字の個数でしょう。

　DPを疑い、「一文字目から決めていこう」とさえ思えれば、結構自然な考察で正しい解法にたどりつけたはず。Fを中心に考えていたとはいえ、何も思いつけなかったのは反省。

F - Treasure Hunting

　解説放送を見てAC。（解説放送後半の、簡単かつ計算量の良い方法で書いた）

　コンテスト中は嘘のDPに走ってしまったが、最初考えたときに二分探索（二文法）では？　と思ったときがあった。何を固定すれば良いか、どういう問題にすれば良いか分からず捨ててしまったけど、その着想が重要だった。

　「K番目の数がX」となるときどうなるか？　という方針で上手くいくかどうかが分かりにくいが、この方針をちゃんと考えればDPに辿り着ける。

G - Divisors of Binomial Coefficient

　ツイッターで「区間篩」というキーワードを見てAC。
　EやFは難しかったと思うけど、この問題は解けなくてはいけなかった。反省。

H - Eat Them All

　解説放送を見てAC。

・ハミルトン路（全ての頂点を一度ずつ通る閉路）を構築するより、オイラー路（全ての辺を一度ずつ通る閉路）を構築する方が簡単

　これを使うのはなるほど。その後、

・グリッドが二部グラフであることを用いて、フロー（とその復元）を用いて各辺を通る回数を求める。

　最後に、

・オイラー路の復元は、dfsの帰りがけでOK。

　一つ目が見えても、二つ目三つ目のポイントを超えるのは難しい。ただ、フローがこういう風に使えるということを押さえておくのは頭に入れておきたい。
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)