キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

　Dまで四完でした。EFを見てFに行ったのですが、解けずに終了。Eの制約には気付いていたのに、やり方を思いつかなかったのも、Fの解法が思いつかず迷走してしまったのも大いに反省です……。

コンテストへのリンク

コンテスト後のツイート

E - Oversleeping

　コンテスト中は主にFを考えていたので、こちらはあまり考えなかったのですが、Y,Qの制約が小さいのには気付いていました。しかし、周期性があるのなら、制約が小さくても何の意味があるんだろう？　と思い、全探索を思いつかず。

　Y, Qを固定した場合の式を立式していれば解法に気付けたんでしょうか……。中国剰余定理まわりにもやや苦手意識があるので、ちょっと自信がないです。

・制約が小さいのだから、Y, Qを固定、全探索を考える

・Y, Qが決まっている場合を立式し、中国剰余定理に帰着

　のどちらのステップも自然な考察でたどりつけるものなので、できなかったのはまずいですね。反省。

F - Zebraness

　フロー。

　いわゆる「Project Selection Problem」（燃やす埋める問題）だった。

　フローと疑えば気付けるかもしれないけど、結構難しいですね。

　なお、PyPyだと（自分の）Ford-Fulkersonだと間に合わず、初めてDinic法を実装した。挑戦したことはあったけど理解できなくて今まで避けていたもの。とはいえ、分かってしまえばそこまで複雑ではなかったですね。

　「Dinic法」で検索してでてきたページ多数を参考にしてコードを書きました。ありがとうございます。坐禅Logさん、tkwさん、みさわさんなどを読んでいたらだんだんと理解できました。

Codeforces Round #708 (Div. 2)

 　ABCとE1をAC。そこそこ速かったので順位はまあまあだったが、逆に言えば、時間があったのにDやE2が解けていないということ。

コンテストへのリンク

コンテスト後のツイート

D. Genius

　コンテスト中の考察でほぼ正しく、後は詰めるだけ、というところまで行っていたと思う。

　……が、実際にコードにするのには非常に長い時間がかかってしまった。こういう問題を解くと、大体の方針は立っても、そこから実際のコードに落とすのは容易でないことを実感する。

　（問題文の読解が結構面倒なので、ここまで考察するのも結構大変だけど）i→j、と進み、jが今まで行ったことのない、これまでで最大の数字のとき、この後進めるのは、

・iより前

・jより後ろ

　のいずれか、である。

　なので、DP[i][j]で、「一つ前がiで現在jにいるときのスコアの最大値」とすれば、メモリ二乗、時間三乗のDPで解ける。

　メモリ制限もあるので、これを一次元にまとめたい。（そうすれば時間も二次元に落ちそう）

　このとき、jを主役にして、

・DP[j]で「初めてjに到達して、直前にいたのがiのときの最大スコア」とするのでは遷移が上手く書けない。（私が書けなかっただけで、ちゃんとやれば多分書けるはず……）

　そうではなく、

・DP[i]で、「最大でjまで到達したことがあるものの中で、現在iにいるものの最大スコア」とすると、一次元のDPテーブルを使い回せ、遷移式も簡単に書ける。

　時間がかかっていたのは、前者の方針に固執してしまったせいもある。けど、その辺は、コードを書きながら遷移式を考えるので良い気がするんだけど。もっと先に考察すべきだったのかなぁ。

AtCoder Regular Contest 114

 　ABの二完でした。解説を聞いてしまえば、C～Eのどれも解けてもおかしくなかった問題に思えるのだけど、実際には一つも解けていないので厳しい。

　（自分にとっての）難易度はE<D<Cだった気もするけど、どれに時間を割くべきか判断するのは難しいので、解ける問題を増やすしかなさそう。

コンテストへのリンク

コンテスト後のツイート

C - Sequence Scores

　公式解説放送を見てAC。

　解説を聞いても難しく感じた……。

　

　本番中は、DPをメインに考えていたものの、各マスにおける寄与数みたいなことも考えた。けれど、まずN個の区間に分けた場合の総和からペナルティ分を引くという発想にはなれなかった。

　そもそも、

・同じ数字が二回現れていて

・その間の数字が全てそれより大きい

　ときにペナルティ、という数え方が思いつけていない。

　数列Aのf(A)を求めるとき、あるindexで+1される条件……みたいなことは結構考えていて、その際、「+1されないとき」を考えた方が上手くいきそう、とは思ったのだが、その条件を簡単に言い表すことができなかったのが敗因か。

　DPを念頭に置いていたとしても、このあたりは考えなくてはいけない内容なので、単純に考察が足りていなかったと思う。だが、この考察は結構難しく思える。

D - Moving Pieces on Line

　公式解説放送を見てAC。

　本番では、面倒そうだからと回避したけど、解法は意外とシンプルでした。

　ただ、T（赤と青の端点）の各点について、左が赤なのか青なのか、で場合分けが必要そうに見える（コンテスト中は、そこの考察が大変で時間がかかりそうだから避けた）ので、そこから抜け出すのが難しそう。

　また、その部分が考察できても、DPすると思えたかも自信がないので、本番中こっちを頑張ったとして解けたか、というと厳しいかも。

　ただ、地道な考察の積み重ねでACに結び付けられる問題に思えたので、考える価値はあった気がする。

　AC人数を見てDを考えるのははじめから避けてしまったけど、それはもったいなかった。（とはいえ、じゃあ何を参考にすれば良いかというと悩ましい。問題文を読んだ時点でいけそう、と思えたら解いてたと思うので）

E - Paper Cutting 2

　公式解説放送を見てAC。

　これはシンプルですね。

　ある直線での切断が行われる確率は？　を求めようと思えば、解法に至るのは難しくない。

　四次元のDPテーブルを持つDPが見えるので、FFTなどを用いてそれを高速化していこう（という方針でも本当は解けるらしいけど）、などという方針に惑わされないことが重要だった気がする。

　Cと似た方針だけど、こっちの方がCより簡単な気がする。もっとちゃんと考えるべきだったか。

F - Permutation Division

　公式解説放送を見てAC。

　解説放送を聞くと、自然な考察の積み重ねで解けているように感じてしまったため、本当に難しいのがどこなのか今一つ理解できていない。

　もうちょっと考えてから解説を聞くべきだったか。

Codeforces Round #705 (Div. 2)

　ABの二完でした。Div.2でこれはひどい。

コンテストへのリンク

コンテスト後のツイート

C. K-beautiful Strings

　後ろから見ていく。

　まず、各i文字目について、そこまでで各文字が何回ずつ使われているかを前計算。

　それを使って、「i文字目までSと同じ文字列で、条件を満たすものがあるか？」を調べていく。

　i文字目までに使われている各文字について、あと何回使えばkの倍数になるか？　を計算する。それを埋めるだけでn文字まで埋まってしまうようなら、i+1文字目を、「その中でS[i+1]より大きい最小のもの」にして、後はソートして埋めるのが最適。

　そうじゃないとき、i+1文字目はS[i+1]より一つ大きいものになる。（S[i+1]が"z"のときは上手くいかないので、次の文字を見る）

　一文字付け加えたとき、「あと何回使えばkの倍数になるか？」を再計算。それでも余った部分は"a"を付け加え、ソートしたもので埋めるのが最適。

　……というような感じで、コンテスト後にACした。

　「こんな感じ」という、おおまかな方針は立つけれど、正確に記述するのは難しい問題。上の説明でも、iが0文字のときなどを省略しているけれど、その辺を適当に書くと落ちてしまう。

　この問題は、おおまかな方針が立ったらコードを書きだしたのは間違っていなかったと思う（もっとしっかり考察した方が良かった、ということも多いけれど、この問題はそうではないと思う）けれど、詰まったときどうすれば良かったんだろう。難しい。

D. GCD of an Array

　解説を見てAC。

　エラトステネスの篩のような方法で、2*10^5までの素因数分解は前計算しておく。

　GCDはセグ木で管理できるので、素因数分解したものをセグ木に載せる方法を試したけど上手くいかず。

　公式解説を見ると、

・答えは単調増加なのだから、一々計算してはダメ。増えた分を差分計算しなさい、とある。

　なるほど、と思い、そこを直すも、セグ木のままだとTLEが取れなかった。（ただ、自分の書き方が悪いだけで、これでも通せるはずです）

　もう一度公式解説を読むと、各素因数について、最小値だけを管理すれば良い、とある。ただ、multisetを使う、という部分がよく分からなくて困った。

　結局、各素因数について、

・どのindexでそこを使ったかをsetで管理→setの要素数がn以上になれば、その素因数をGCDに持つ。

・(素因数の重み, index)をheapqに入れて管理、シミュレーション。heapqの最小要素が実際の値より小さいなら、popする。

　のようにしたところACできた。

　ただ、制限時間ギリギリなので、あまり良い書き方ではないですね……。（PyPyで、もっとまともな実行時間でACしている人がたくさんいます）

AtCoder Beginner Contest 194

　全完106位。久々に良い順位！

コンテストへのリンク

コンテスト後のツイート

　各問題に関しては、書きたいことがないで省略。

　昨日のyukicoderと今日のABCとで連続で桁DPが出たのは珍しいですね。途中、実装に詰まったとき昨日のコードを見に行ったりしたので、そのおかげで早く解けたのは間違いないです。

　ただ、もっと綺麗に素早く桁DPを書く力を付けたい。

Codeforces Global Round 13

　Dまで四完でした。

　Cでセグ木を使ったけど、imos法を使えば使わなくて良かったらしい。確かに。

　Fは惜しかった気がしたけど、コンテスト後にACするまでかなり苦労したことを考えると現実的には厳しかった。

コンテストへのリンク

コンテスト後のツイート

F. Magnets

　一応、自力AC。

　多分、公式解説と同じ方法なのですが、私が苦戦したところ（クエリ回数を減らす部分）に触れられていないので、何か勘違いしているのかもしれない。

　ここでは、ツイートしたものをまとめておきます。

　そもそものアイディアは、

・一個 vs 他全て

　をn回試すというもの。

　ただ、これだと、

・--N--NNNSSS

　のようなとき、Nのところに対しては0が返ってくるので困る。

　なので、そこをちょっと工夫して、「他全て」ではなく、「今まで試して0になったものを除く全て」を試すという方針にする。

　これは、まず、

・1 vs 他全部を投げて、

で0が返ってきたら、

・2 vs 他全部 - {1}を投げる。

これも0なら

・3 vs 他全部 - {1, 2}

……とやっていく。

　これなら、さっきの

・--N--NNNSSS

　という例で、最初のNでは0が返ってくるけれど、それ以降のN（やS）に対しては-1が返ってくるため上手くいく。

　それにより、n回のクエリで、「NかSだと確定しているもの」と「高々一個NかSがあり、他は"-"のもの」とに分けられる。後者を二分法で調べれば良い。

・NかSと確定している一個 vs 後者の半分

　というクエリを投げて、1が返ってくればその中にNやSがある。0なら、残り半分に高々一個NやSがある。

　ただ、この方針だと、n+lognの繰り上げ回数クエリが必要。さらに二回クエリを減らす必要がある。

　そのうち一回は割合簡単に減らせる。最初にn回クエリを投げたが、返り値の正負や偶奇を見ることで、最後の一回が"-"なのかNやSなのか、というのは分かる。

（具体的に書いていないのは、試行錯誤しながらコードを書いていたので、正確に理解できていないためです。逆に言えば、試行錯誤すればできるはず）

　もう一回は、先程書いた、

「後者を二分法で調べれば良い。

・NかSと確定している一個 vs 後者の半分

　というクエリを投げて、1が返ってくればその中にNやSがある。0なら、残り半分に高々一個NやSがある。」

　にヒントがあった。

　1が返ってきたときの方が情報が多い！

　なら、適当に半分を取るのではなく、

・NかSと確定している一個 vs 後者の半分のうち多い方

　というクエリを投げた方が得られる情報が多い。

　実際、そうすると、

・1が返ってくる→その中にNかSが含まれる（と情報が増えるので、最後1個残ったときそれがNかSと分かる。ので一回減る）

・0が返ってくる→「残りの方に高々一個NかSがある」（最後までこれを繰り返すと、残り一個が"-"かどうか分からないので、それも聞く必要がある。が、小さい方を取っていったので、logで収まる！）

　となる。

Educational Codeforces Round 105 (Rated for Div. 2)

 　Cまで三完。Dが解けなかったのは、Cで苦戦して集中力が落ちていたせいかも。

コンテストへのリンク

コンテスト後のツイート

D. Dogeforces

　ちょっと分かりにくいけれど、難しい問題ではなかった。

　小さい給料の人から順に木を作っていく。（与えられた表をx:給料、i,j:人として(x, i, j)のリストとみて、xでソートする）

　その際、最下層の人それぞれについて、「現在の木に関して、自分の一番上の上司は誰か」が分かるようにしておく。（Union-hindの要領で、再帰を使って書ける）

　すると、新たな給料xと人i, jを見る際、「iに関する一番上の上司もしくはjに関する一番上の上司」の給料がxであれば、新しいノードを作らないようにすれば良い。（そうでなければ、新しいノードを作り、その人を「i, jの一番上の上司」の上司にする）

　うーん、本番中は、（clarが来てたけど）解の存在とかが気になって思考が疎かになっていた気がする。特に発想もいらないし、できなきゃいけない問題でしたね。

E. A-Z Graph

　解説AC。

　解説を読んだらギャグだった……。

・頂点u, vの間に双方向のpathがあればkが奇数のときは条件を満たす

・さらに、そのラベルが一致していれば、kが偶数のときも条件を満たす

　となる。どちらも、u, vを行ったり来たりするpathを考えれば良い。

　ギャグだけど、最も単純なパスを考えれば答えに辿り着ける、という意味では教育的かも？