Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 135

3完。

Dが無理だと思ったので早々に見切ってEに集中したのが完全に裏目に出ました。どうやって構築するんですかあれ!?

Cまで軽快に解いて調子いいと思ったらこの仕打ちでぐんにょりです・・・。

各問題

A - Harmony

AとBの差が奇数のときはIMPOSSIBLE。そうでないときはAとBを足して2で割ればOKです。ようするにAとBの中間点を取るということで。

B - 0 or 1 Swap

これは{1, 2, ..., N}を並び替えた数列(数字が連続している)、というのを利用して、単純に前から見ていって場所と数字があっていないところを探すのが早いんじゃないでしょうか。 数字が連続しているため、前後の大小関係を見る必要は実はありません。

C - City Savers

あー、editorialによると、前から貪欲でいいらしいです。私は考察に自信がなかったので、前から貪欲と後ろから貪欲を両方やって大きい方を取りました。てへ。

D - Digits Parade

苦し紛れに13の倍数の判定方法とかをググったりしましたがまったくわかりませんでした。まあ|S| <= 10^5なのでそんな正攻法ではいかんともしがたいです。

editorialによれば、DPだそうです。DはDPのD、言われてみればそりゃそうですね・・・。

E - Golf

Kが偶数のとき、距離は偶数単位でしか詰める(あるいは開ける)ことができません。なので、Kが偶数かつX+Yが奇数のときは構築不可能です。

それはわかったので、後は構築すればいいのですが、その方法はさっぱりわかりませんでした・・・。

F - Strings of Eternity

見てません。

まとめ

DPかー。そういえばそんなものもあったな・・・。(本当に完全に頭からDPのことが抜け落ちていたらしい)

3完にもかかわらず水色手前のパフォが出て、かろうじてレートは微上昇。次回も一応昇級戦です。いい加減しんどいぞ・・・。

f:id:mdstoy:20190727231309p:plain