Toy と帽子と ADP BE

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

AtCoder Regular Contest 154

2完3WA。

各問題

A - Swap Digit

A > B のとき AB を入れ替えて A に小さい数字が集まるようにしたとき 'A*B` は最小になる(気がした)ので、そのとおりやるとACします。

しかし私は、2年以上使っていた巨大な数の剰余を求めるスニペットがバグっており 2WA 出してしまいました。そんなことある?!

B - New Place

まず、Sに含まれる文字種とTに含まれる文字種が異なる場合構築は当然不可能です。それ以外の場合構築は可能です。

Sの末尾の連続する部分文字列がTの(連続するとは限らない)部分列である場合、Sの先頭から当該部分より前の文字を適切な場所に挿入することでTを構築することが可能です。よって、Sの末尾のどこまでがTの部分列であるかを判定すればよくて、これは尺取り法の要領で線形で実装可能です。

まとめ

Bを通せたので大怪我にはなりませんでしたが、まさかそんな基本的なスニペットがバグっているとは...。