ABC171

Fが数え上げ(昨日全く解けなくてトラウマ)でちょっと詰まって不穏になったけど結局解けて、全体として面白かった。

A - αlphabet

A問題でまさかの誤読(大文字を小文字に、小文字を大文字にするんだと思い込んでいた)。文字コードは'A'のほうが'a'より小さいと、わかってはいたが、やはり大文字のほうが小さいという状況は混乱を生んだ。if (c < 'a') c += 'a' - 'A'; などと書いていたが、符号とか順番とか、サンプルが通らないとどこも間違ってる気がして。特に最初は大文字小文字変換としても間違っていたので泥沼にはまった。3分以上かかってしまい、この時間のかかり方はyukicoderのAみたいだなと思った。

B - Mix Juice

ソートして小さいほうからK個足せばいい。既出な気がして、誤読してないか不安だった。

C - One Quadrillion and One Dalmatians

クソムズC。天才なのでそれなりのスピードで書けた。まず、何文字の名前になるか調べる。K文字の名前は26^K個あるので、便宜上0番の名前を空文字列(26^0=1で1通り)として、K=0から順に26^Kを足していって番号を超えたらループを抜けて超える手前の数を引く。これで桁数がわかったので、あとは26進法に直すだけ。

D - Replacing

PASTっぽいけど簡単で面白い(わりと瞬殺だった)(最終的な和だけ求めればいいと誤読していたが短時間で修正できた)。まずstd::mapを使うことが浮かんだが、10^5までなのでvectorでいい。各数が何個あるかカウントしておけば p[c] += p[b]; p[b] = 0; のように移し替えることができる。

E - Red Scarf

Aで少しロスしたもののCDをいい感じに解いたので順位が上がっているかと思ったらそうでもなかった。問題の見た目からしても、このEめちゃくちゃ簡単なのでは?まず、全体のxor(Tとする)がわかっていれば T ^ a_i を出力するだけ。「何でもいいのでは?」と思いTを適当に設定して出力してみる(出力に10^18以下などの制約がないので際限なく大きい答えは存在しなさそうであることに注意)。しかしよく考えるとT=0にしたうえで出力したそれらのxorが0になるとは考えにくい(あぶなかった)。そういえば制約にNは偶数とあった。a全体のxorは、全体のxorをN回から1個ずつ抜けてるのでなるほどここが奇数になる仕組みか。つまり、Tはa全体のxor。これは瞬殺したかったなあ。

F - Strivore

それなりに解かれているのでこれもそこまで難しくなさそう。Sの長さをNとして、長さN+Kの文字列(部分列としてSを含む)を作る。最初、N+K文字の中からN個を選ぶだけかと思ったが、元から含まれる文字を追加したときに重複してカウントしてしまう。O(N^2)のDPを高速化するような方向でも考えたがダメっぽい(昨日の恐怖が呼び起こされる(それがなければもう少し早く解けたんじゃ?))。で、しばらく経って、条件を満たす文字列を、左から貪欲に部分列をとっていくことでダブりなく分類できると気づいた。あとは、その部分列以外のところの埋め方を数えるだけ。貪欲にとったので、次に来るSの文字以外の25通りが基本で、最後だけ何でもありの26通りになる。その最後の部分の長さが0からKまでについて何通りあるか足せばいい。Sの最後の文字の位置がわかっているので、あとはそれより左の領域で残りのN-1文字がどこにくるかをコンビネーションで数えるだけだ。実装が軽かったので思ったより早解きできた(22時までには解きたいなあとか思っていたが10分前に通せた)。