ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > Codeforces Round 612 (Div.1) 解法

Codeforces Round 612 (Div.1) 解法

コンテストページ

Dashboard - Codeforces Round #612 (Div. 1) - Codeforces

解法

A - Garland

左から順に見て、今までに入れた偶数の数、奇数の数、前の項の偶奇をキーとする DP をします。

B - Numbers on Tree

同じものがあれば葉側の方を微増すれば良いので、答えは distinct だとしてよいです。

根から順に決めていきます。今見ている頂点のお名前は x です。 まずは、部分木のサイズ以上の c_x が来たら NO をしておきましょう。 小さいものを x の部分木に使うとしてよいので、x の値は未使用なもののうち c_x 番目に小さいものとしてよいです。

「未使用なもののうち c_x 番目に小さいもの」は、どうすのがよいのでしょう。私はセグメント木で二分探索（活きの良いログが 2 匹乗っております）（はい！？）で対応したのですが、平衡二分木があると良さそうです。もしくは、もっと簡単な方法があるのでしょうか。

実はあって、この問題の制約は n ≦ 2000 ですから、二乗が間に合います。（はい！？） 指摘してくださった方々、ありがとうございます。この記事の下の方の togetter コーナーで紹介されています。

C1 - Madhouse (Easy version)

まず全体でクエリして、文字列を長さで分類します。 長い順に見ていきましょう。

まず、最長のものを見ると全体の出現回数がわかります。 さらに、それより一つ短いものを見ると、出現回数に 1, 2, 2, ... , 2, 1 で重みづけたものがわかりますから、先程のものとの差を取ると、端がなくなったものの出現回数がわかります。

このようにすると、結局あらゆる [i, n -i[ での出現回数がわかるので、またしても差を取ることで、s[i] <-> s[n-i+1] を除いて各場所の文字が確定します。

同じことを、今度は全体ではなく一つ短いもので行いましょう。 そうすると、最後の文字から連鎖的にすべてが決まっていきます。

ところでこれではクエリ数が 2 なのですが、制約では 3 になっています。私はまた嘘を言ってしまっているのでしょうか（泣）

反省

安定に寄せているとはいえ、時間がかかりすぎてしまいました。 ただ戦略ミスと言うよりは、キレイな実装に落とすまでの考察の遅さが脚を引いているような印象ですから、今後ともバーチャルコンテスト等でそのあたりを少しづつ速くしていこうと思います。

お気持ち

こどふぉのレーティングはあまり気にしていないのですが、Div. 1 から落ちるとさすがに悲しいかなという気持ちです。あっとこと違って、こどふぉは格上のコンテストからは閉め出されるシステムですから（泣）

ツイッターの様子

A - Garland

貪欲法被害者の会です。

B - Numbers on Tree

やはりみなさんログは 2 つだったのでしょうか。瓜二つならぬ、ログ 2 つな解法です。

こちらは優しい方々です。なんですか！！ n ≦ 2000 って、制約を読みましょう！

C1 - Madhouse (Easy version)

いかようにもできそうな問題ですが、考察を頑張ると実装がどんどん軽くなるタイプの問題です。このあたりの詰め方が足りないことに、実装をしているときに薄々気づいてしまって悲しい気持ちになります。

これです！！ これわかります！！！ 不要な空行は毎回ある気がしますし、おそらくわかりやすさ（←本当ですか？）のためでしょう。