イノたまごラボ・あのぶる の「こんなの作ったよ!」

「イノたまごラボ」はひとり同人サークルのようなものです。今のところ同人誌は作っていませんが、ソフトウェアからイベントまで、心惹かれたものを細々と。

ABC全部やるチャレンジ・ABC345

全体の進捗

  • やった回: ABC345
  • 成績: ABC3完 / 0ペナ(+未AC0ペナ、終了後提出で1WA)/ 16:38(ペナ込み)
  • 推定パフォーマンス: 1212

パフォーマンスだけ見るとかなり良かったのだけど、これ実はBとCを一度個別に解いているのでこの推定水パフォを鵜呑みにしてよいかというとかなり怪しい。
とは言え初めて解いたときも解説とかは読んでないので初見でも3完は出来たと思うし、仮にCに20分かけたとしても1000は超えていた雰囲気ではある。

A問題: ABC345-A Leftrightarrow

atcoder.jp

なんかいい解き方ないかとか考えた末、愚直に解いて6分弱消費。オンサイトで出るとすごい焦る(もう何とは言わないが実際焦った)タイプ。 コンテストでAC早かった順にコード短めの人のを見ていくとこのどっちかが多かった印象。

  • 文字列を先頭・末尾・中間に分割して個別に判定
  • 正規表現で一括評価

コード読ませて貰った分だと、中間部分の判定をするところで、配列にしてuniqして=1個になるかを見てるのがお洒落だったかなーと思う。

B問題: ABC345-B Integer Division Returns

atcoder.jp

要するに10で割って端数を切り上げた値を出力せよ、というやつ。Floatでやると誤差で泣くのでRationalでやりましょう。

C問題: ABC345-C One Time Swap

atcoder.jp

「全体から当てはまらない数を引いていく」パターンの問題。あと三角数大活躍。

「操作の内容からして変換後の文字列が返還前後で変わらないケース以外でダブることはまずない」と言えるので、やることが分かってしまえばコードはシンプル。

(1)全ての文字数が違う文字だった場合、ありうる文字列のパターン数 - (2)入れ替え前後で文字列が変わらないパターン数 + (3) (2)が1以上 ? 1 : 0

という計算式になるので、 それぞれをゴリゴリと計算していけばOK。 文字の入れ替え=文字列の中から2文字を選ぶ、なので、それぞれの組み合わせの数は三角数で求めることが出来る。制約で1 <= i < j <= Nが保証されているので、順番を考慮しない組み合わせ計算を使う。

D問題: ABC345-D Tiling

(ランタイムエラーするしWAするコード) atcoder.jp

まだ解説は読んでない。

制約を見る限りおそらく全探索で、適切に枝刈り?しつつDFSしていくタイプだと思われる。
RE多いのは多分枝刈りが足りなくて呼び出しのネストが深すぎるとかそういうやつで、そもそもいくつかWA起こしてるので写経からかもしれない。

5/1 追記

ちゃんと解けたコード🎉 atcoder.jp

何ということはなく、単純に最初の1枚がそのまま置けなかったケースが考慮出来てなかっただけ。
RE起こしたケースはif文で拾ってあげればいいし、WA起こしたケースは転置のパターンを追加したらあっさりAC。悔しい。

バグらせにくいコードを心がける気持ちは仕事にもちゃんとつながるので、肝に銘じていこうと思いました。