2022年6月30日木曜日

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

 　Eまで五完。

コンテスト後のツイート

 F - Teleporter Setting

　解法ツイートを見てAC。

　スタートとゴールから各点への距離を求めておく。テレポートするとき、利用したい点は、スタートかゴールかのいずれかに近い点なので、それぞれ最も近い点を求めておく。

　ここで、未定の点がxと決まったとき、テレポートの使い方は、

・1→（1に近い点）→x→N
・1→x→（Nに近い点）→N
・1→（1に近い点）→x→（Nに近い点）→N

　の三通り。
　この三番目の場合に気付かなかったため解けなかった。
　別な問題を考えたりしてちょっと時間を置ければ気付けた気もするけど、そういう余裕がなかったね。

G - Prefix Concatenation

　解法ツイートを参考にローリングハッシュ＋二分探索を書いたがTLEが取れず。
　解説を見て、KMP法を使ってACした。（Z-algorithmを使う方法は理解していない）

　色々な文字列アルゴリズムはがあるけれど、ローリングハッシュ（とManachar）以外は（コードの書き方だけでなく）内容も思い出せなくて困る。

　困るんだけど、ローリングハッシュでどうにかなることも多いから、ちゃんと覚えなきゃ、という気にもならないんだよね……。

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

2022年6月28日火曜日

AtCoder Regular Contest 143

　Cまで三完。

コンテスト後のツイート

C - Piles of Pebbles

　コンテスト中は、（まずちょっと考えて一度飛ばそうかとDに行き、分からず戻った後）、

・再帰で愚直解を書く
・書いてみたら、X=Y=1のときは見たことある結果になる
・この問題を思い出し、解説を読む。
・大体同じように解けそう、と分かり、(愚直解と一致するか試した後)AC

　という流れでした。

　類題を覚えていたのは、当時嘘解法でACしたためです。嘘解法でACすると、記憶に残りやすいので良いかも？

D - Bridges

　解法ツイートを見てAC。

　コンテスト中、最初は（問題文通り）2N個の頂点があるグラフを考えていたけれど、Cを解いて戻った後は、N個の頂点のグラフで考察すべきでは？　とは思い直した。N頂点のグラフで、多くの頂点がサイクルに巻き込まれるような辺の貼り方をすれば良さそう……と思うも、最小循環費用流？　とか考えたりして、やり方が分からなくなってしまった。

　落ち着いて見れば、これはDFSする（DFS木を考える）だけで良い。
　こういったDFS系の問題は落とすことが多いので注意しようと思っていたのに、また解けなかったというのは悲しい。最初、2N頂点のグラフを考えていたために引きずられた、という部分はあるが、これは思いつきたかった。

E - Reversi 

　解説放送を見てAC。

　葉について考察し、それをもとに木DPをすればOK。

　葉については考えたけど、それを元に有効辺を付けようとは考えなかった。石を取り除けるかどうかの判定をどうやるんだろう、と考えるだけでなく、辞書順最小の裏返し方をどう見つけるんだろう、と考えたなら有効辺にするのは結構自然かもしれない。

　まず判定をどうにかしよう、と思ってしまうけど、（この問題に関しては）辞書順のことも考えて臨むべきだったのかな。
時刻: 0 件のコメント:
ラベル: ,

2022年6月25日土曜日

yukicoder contest 349

　Cまで三完。


No.1989 Pairing Multiset

　解説AC。具体例・図もあり、解説が分かりやすかった。

　解説を箇条書きにすると、

・Sが定まっているとき、f(S)はソートして二つずつ組みを作っていけば求められる
・多重集合はソート済み配列と同一視できる。
・ソート済み配列は、グリッド上の経路に対応させられる。（ので、その個数は、経路数と対応する）
・グリッド上で、ある縦の線に対応する経路数の和として数えられる
・あとは計算量削減パート

　という感じか。
　
　四点目・五点目は簡単ではないけど、三点目までたどりつけばこういうことは考えそう。
　なので、二点目・三点目が思いつけるかどうか、という気がする。

　「多重集合やソート済みの配列はグリッド上の経路に対応させられる」は時々見かける内容だと思うので、押さえておきたい。
時刻: 0 件のコメント:
ラベル:

2022年6月21日火曜日

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

　Eまで五完。

コンテスト後のツイート

 F - Cumulative Cumulative Cumulative Sum

　解説AC。

　とりあえず立式すればその先が見えてくる問題。
　コンテスト中はこの問題を飛ばしてGへ行ったけれど、Fを考えていれば解けたかというと怪しい。

G - Black and White Stones

　解説AC。

　「各辺に置く黒い石の個数を固定したらDPで解けるのでそれを足し合わせれば良い」と言われれば難しくない。
　コンテスト中は、なんか上手い方法があるのではと思い、「ポリアの数え上げ定理」を調べたりして迷走していた。

　落ち着いて問題を見直してみると、特に対称性のある問題ではない。Dの制約が小さいことに注目して、各辺に置く黒い石の個数を固定して解けば良いのでは？　と考えてみるべきだった。
時刻: 0 件のコメント:
ラベル: ,

2022年6月17日金曜日

Codeforces Round #800 (Div. 1)

　Cまで三完と思いきや、Cがシステムテストで落ちて二完。

コンテスト後のツイート

C. Keshi in Search of AmShZ

　自力AC。

　解法ツイートで「どの道を進んだとしても最低x歩で行ける」と書いたけどこれじゃ考察不足。ダイクストラで今までに見た辺の行き先は、今見ている辺の行き先よりDPの値が小さい（もしくは同じ）なのだから、ブロックしなくてもOK。それ以外を除外したときに、歩数が小さくなるかどうか考えればOK。

　これは、コンテスト中も頭をよぎったのだけど、なぜか必要ない気がして考えずに提出してしまった。pretestでWAが出てたら気付けてACできた気がするので悔しい～。
時刻: 0 件のコメント:
ラベル:

AtCoder Regular Contest 133

　Cまで三完。

コンテスト後のツイート

D - Range XOR

　kaageさんのブログの解法を参考にしてAC。

　累積xorの性質として、偶数とその次の奇数のxorは1とか、偶数から四つ連続したもののxorは0といったものは有名。それを使う問題なのは分かるけれど、詰めるのは大変。
　最終的に桁DPになりそう、というのも分かるが、使うところまで詰めるのも難しい。

　上のkaageさんのブログの解法では、l, rを偶奇で分類し、「lが奇数、rが偶数」のときだけ桁DPで処理している。（他の場合は、最初に書いたxorの性質を用いて処理）

　ただ、私は、桁DPは下の桁で場合分けしてメモ化再帰を使って実装した。

　calc(L, R, x, eqflag)で、「L以上R以下の数iに対して、i^xもL以上R以下であり、eqflag=1なら、i<=i^x、eqflag=0ならi<i^xとなるような場合の数」とした。

　不等号の計算を間違えたためちょっと実装に苦労してしまったが、この問題だと下の桁を場合分けする実装の方がやりやすいと思う。
時刻: 0 件のコメント:
ラベル: ,

yukicoder contest 342

　ABの二完でした。


No.1929 Exponential Sequence

　半分全列挙。

　このキーワードさえ思い浮かべばそう難しくない問題なのに、全く思い浮かばなかった。反省。

No.1930 XOR of Two Range

　自力AC。

・xが偶数のとき、x^(x+1)=1

　という事実を知っていれば、L+R以外は大体打ち消し合いそうだというのは分かる。その後は、周期性を実験して求めるのが簡単。
時刻: 0 件のコメント:
ラベル:

2022年6月14日火曜日

yukicoder contest 322

　Fまで六完。


No.1741 Arrays and XOR Procedure

　今見たら自力でACできた。

　こういう、隣接要素に対して何か処理をしていくタイプの問題では、パスカルの三角形と関係があることが多い。二項係数の回数だけそれぞれの値が使われると気付けばOK。

　自分の提出ではLucasの定理をそのまま使った。二項係数の偶奇がO(1)で求まるとは知らなかった。

No.1742 Binary Indexed Train

　自力AC。

　可能な限り貪欲に進めば良い。
　実装はダブリングと似た感じで書けばOK。
時刻: 0 件のコメント:
ラベル:

2022年6月13日月曜日

エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）

 　ABDEの四完で終了。Fは解きたかった。

コンテスト後のツイート

C - ±1 Operation 1

　コンテスト後、愚直解を書いて比較してAC。

　解法はツイートした方法で良かったが、Dが負の場合にもx%Dみたいな計算をしていたためWA。その部分をx%abs(D)に直したら通った。

　コンテスト中にコードを読み返して気付かないのはまあ仕方ない。ABCのCで愚直解を書くのはちょっとという気持ちになり後の問題へ行ったのも変なことではないと思う。まあ、あまり気にせずに。

F - Pre-order and In-order

　解説は読んだけど実装方法が今一つ分からず、自分の方法でAC。
　「通りがけ順（in-order）」というのは知らなかったけど、二分探索木とセットで理解しておくべき概念だったようです。

　ツイートに書いたように、

・頂点xがIでk番目に出現するとすると、Iでk-1番目までに出現する頂点が左側子孫、k+1番目以降に出現する頂点が右側子孫

　である。

　この境界はPにおいても境界になっており、その境目の直後の頂点が（存在すれば）xの右側の子になる。（左側の子は、Pにおいて次の点）
　なので、Pでこの境目のindexが何になるかが分かれば再帰で書けるが、コンテスト中はこの境目を求める方法が思いつかなかった。が、冷静になれば、これは二分探索で求められますね。

　解説ではO(N)でやっているようなのだけど理解できていません。

G - Constrained Nim

　自力AC。

　座標圧縮が本質の問題。

　Grundy数は基本的には1ずつ増える。ただし、問題文中の禁じ手に該当する個数の山があった場合は、定義通りにGrundy数を求れば良い。

　その際、今までに出現したGrundy数のうち、二回以上登場したものについて何回ずつ登場したかを覚えておくと、計算時間も間に合う。基本的には各数字は一回ずつ登場するので、二回以上登場するものは多くない（高々M回である）。

Ex - Range Harvest Query

　解説の遅延セグメント木の解法でAC。

　座標圧縮して遅延セグメント木を使えば良い、と言われればすぐ解けなきゃいけないのに、解説を読んでもなかなか理解できなかったのは反省。

　セグメント木の各ノードに「対応する区間ですでに収穫された実の個数」を持つ、ということをベースに考えれば、LAZY配列には「最後に収穫が行われた日付」を入れておくことで更新が可能になる、と分かりました。
時刻: 0 件のコメント:
ラベル: , ,

2022年6月12日日曜日

Codeforces Round #798 (Div. 2)

　Dまで四完。Dでのペナはケアレスミスなので仕方ない部分もあるが、Cでのペナはあまり良くなかった。細かい部分の考察をせず、sampleが合ったから良いかな、と提出してしまった結果のWAなので。

コンテスト後のツイート

E. ANDfinity

　解法ツイートを見てAC。

　とりあえず、0は全て1にしておく。
　その上で、下何桁0が続くか（trailing zeroと呼ぶらしい）を見て、それが最大のものに着目する。そいつらのうち1つを-1すると、それよりtrailing zeroが小さいもの達全てとconnectになる。
　それでダメな場合は、trailing zero最大の別のものに+1すれば良い。一番下の桁を考えると、さっき-1した数とconnectになるため、全てがconnectになる。

　と、trailing zeroに注目することと、高々二回で操作が完了することが本質だが、それらは全て試すことが必要。

　具体的には、
・64 64 1 1 1
　だったら、64の一つを+1することで一回の操作で完了できる。(trailing zeroは使わない)

・8 24 24 1
　だったら、trailing zero最大のものは8と24だが、24（のうち一つ）をｰ1すれば一回で完了するが、8をｰ1すると二回かかってしまう。
時刻: 0 件のコメント:
ラベル:

2022年6月11日土曜日

yukicoder contest 347

　Bまで二完。Cが解けなかったのはまずい。


No.1973 Divisor Sequence

　解説AC。

　素因数ごとにDPし、累積和による高速化をすれば良い。
　コンテスト中は、素因数ごとに分けずに同じDPの遷移が成立すると思い込み、答えが合わず悩んでしまった。

　たとえば、36の約数は、

・1 2 3 4 6 9 12 18 36

　であり、12*3=36なので、12の次の数は3以下全て……となりそうだが、12*2=24は36の約数ではない！
　なのでこれは成り立たず、素因数ごとに分けて考えなくてはいけなかった。

No.1974 2x2 Flipper

　解説AC。

　市松模様に塗ってどうこうするのかな、と考えていたが間違い。もっとシンプルに偶奇に着目すれば良かった。
　2*2マスをflipしても各行・列における黒マス（白マスも）の個数の偶奇は変わらない。十分正のチェックは、端の行・列に押し込めばできる。

No.1975 Zigzag Sequence

　自力AC。（C、Dより簡単かも？）

　A[i]がジグザグの中央になるときの答えを足し合わせれば良い。（小さい場合と大きい場合、両方を足す）

 左側がA[j]（j<i, A[j]<A[i]）となるときの部分列を考える。これは、jよりさらに左側全ては、選んでも選ばなくても良い。なので、BITを使って、pow(2, i)をA[i]に足していけば処理できる。これを左右からやる。
時刻: 0 件のコメント:
ラベル:

2022年6月8日水曜日

Codeforces Round #797 (Div. 3)

　全完。Fで時間かかってしまったけど、まあまあ良い出来でした。

コンテスト後のツイート


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

2022年6月7日火曜日

yukicoder contest 296

 　AB二完。終了後にCを自力AC。


No.1513 simple 門松列 problem

　求めるものが二つあるが、ans2はans1に[0,K)の平均を掛ければ良さそう。
　ではans1をどうやって求めるか？　というとこっちはDPが使える。

　DP[i][j]で、x-2番目の要素がi、x-1番目の要素がjの長さxの門松列列の個数とする。これを用いて長さx+1の門松列列の個数を求める。

　i<jのときを考える。
　すると、次の値となりうるのは、0, 1, 2,..., j-1からiを除いたもの。これをそのままやると間に合わない（全体での計算量が四乗になってしまう）が、累積和を使うことで計算量が落とせ、全体で三乗になるため、間に合う。

No.1514 Squared Matching

　ABCで同じ問題が出たのを機に、解説AC。

　こちらの方が制約が厳しいため、強引に素因数分解・約数列挙して解くことはできない。
　xの約数のうちの最大の平方数f(x)について着目することが必要になる。

　x/f(x)で分類してCounterで数えれば答えが合うことは分かったが、それだとMLEになってしまう。
　実は、各aについて、bは(a/f(a))*(平方数)と表せるので、bの個数はsqrt(N/(a/f(a)))と直接求められる。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 346

　Cのみ一完。


No.1964 sum = length

　解説AC。もっと速い解法があるようですが、それは理解できていません。

　DP[長さ][和]の四乗DPを考えていたが、DP[和 - 長さ]を考えれば三乗で済む。その方針も考えたはずなのに、上手くいかない気がして捨ててしまった。なぜ……。
　これが解けなかったのはまずい。

No.1965 Heavier

　解説AC。

　「良い区間」に関して、推移性が成り立つことに気付く必要があった。

No.1967 Sugoroku Optimization

　自力AC。

　いつも「aとして残りのマス数を選ぶ」のが最適、ということに気付けばあとは期待値DP。累積和で高速化できる。
時刻: 0 件のコメント:
ラベル:

2022年6月6日月曜日

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）

　Dが解けなかった。

コンテスト後のツイート

D - At Most 3 (Contestant ver.)

　100進数を考えれば良かった。
　コンテスト中は、二進数などを考えていて全く思いつかなかった。

　これを思い付くかどうかなのだけど、一つ手がかりとして、

・3個の和として作れる数の個数は高々C(300,3)で$10^6$と比べてあまり多くない

　ということがあった。
　あまり無駄なことはできない、というのは思いつく一助になったかもしれない。

G - Intersection of Polygons

　解説放送を見てAC。

　幾何はつい敬遠してしまいたくなるけれど、順を追っていけば解ける問題でした。（幾何はそういう問題が結構多い？）

　平行移動した直線たちの中で、一番左側、一番右側にあるものをどう求めれば良いかが難しいけれど、そこでも外積を使えるのですね。
時刻: 0 件のコメント:
ラベル:

AtCoder Heuristic Contest 011

　ツイートを転載しておく。元々、別の場所に書いてからツイートしているので、まとめてあった方が読みやすいかな、という気持ちもある。


・コンテスト後のツイート

　AtCoder Heuristic Contest 011　25Mに乗らず。

・最初は、AOJの15パズルをやってた（けど応用できなかった）
・木を探すパート：頑張って探す（乱択DFS）とN=6のときはそこそこ、7のときは時々見つかる。それより大きいときの見つけ方が分からなかった。
・15パズルパート：左上から頑張って変えた。

　木の見つけ方が分からなかったのが致命的。

　木を見つけることができないと、その後が敗戦処理みたいになるため虚しさがつのった。15パズルパートはもっと改善できたと思うけど、あまり木が見つかっていない状況でこっちを改善してもなぁ、という気持ちになってしまった。



・反省

　結局、木を探すパートを乱択DFSでやったのが筋が悪くて、（大きい盤面でもDFSで木を見つけることは可能らしいが、難しそう）全部のマスに仮置きした後に調整していく、という方針を思い付かなくちゃいけなかった。

　なんで思いつかなかったかというと、最初かなり長いこと（五日くらい？）、全てのマスのパネルについて隣のマスのパネルとの条件が満たされていれば完成盤面になると勘違いしてたんだよね。（複数サイクルが現れるので、ダメ）

　勘違いに気付いたときに、木であることを満たしたままDFSする方法（leafへたどりついていないedgeの個数を記憶してDFSする）を思い付いたため、それでいける気がして実装を始めてしまったせいかと思う。

　仮置きして調整していく場合でもこの考え方は使えるから間違ったことを考えていたわけではないんだけど、成功体験と結びついてしまったために思考を戻せなくなってしまっていたのかと。

　あと、木を探すパートは初日にDFSかその類似でいけそうと思っていて、その後しばらく15パズルパートを考えてから戻ったせいで、DFSでいけそうという考えが自分の中で固定化していたかもしれない。

　まあだから、終盤でも思考に余裕がないと……って話になるけど、それは難しいねー。

　残り時間が少なくなると焦ってしまうし。時間が迫ってるのに順位が悪いとつい目先のことに飛びつきたくなるのはまあ仕方ない。
時刻: 0 件のコメント:
ラベル:

2022年6月5日日曜日

AtCoder Beginner Contest 254

　Fまで六完。

コンテスト後のツイート

G - Elevators

　解説放送を見てAC。

　確かに一つ一つのステップは典型なので難問ではないと思うが、実装は非常に大変。

　特に、

・各ビルについてのエレベーターをマージする
・ダブリングするために、エレベーターをまとめ、使う必要のないエレベーターは削除

　をする際、どう処理すべきかで迷った。

　両方、低い階の方でソートする（これも、区間スケジューリングが頭にあると、高い階でソートしたくなり間違う）のだが、その後の処理は少し違う。（後者ではマージするわけではないので）

　時間をかけられ、また、サンプルが強ければ解けなくてはいけない問題だろうが、今回解き切るのはかなり難易度が高かったのでは。

　さらに、ダブリングの実装でミスり、デバッグにかなりの時間を要したのは良くない。ダブリングは大きいステップで行けるかどうか調べて（つまり、1<<i進むこのiを大きい方から見る）更新していくのが良いのですね。なるほど。

Ex - Multiply or Divide by 2

　大きい方から貪欲にやれば良いということにはコンテスト中に気付いたが、Bについては、(2x+1)→xの遷移ができないことに気付かず。
　惜しかった。


時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)