出力を入力へ

プログラミングに関する基本的な事を中心にまとめます

参加記録 ABC104

最近のABCは難し過ぎる. ABしか解けなかったけど,これでレート上がるんだから皆解けなかったのだろう.

AB解いて300(10:38), 576th 956 -> 990(+34), パフォーマンス1214

B - AcCepted

正規表現で解けるかな,なんてことは一切考えず愚直に実装した.

'A', 'C'の文字が含まれている位置の確認はともかく, それ以外の文字が小文字であることの確認処理の実装があまり上手くなかった. 'A', 'C'が含まれていることを確認済なので,全文字列の大文字数をカウントする想定実装がシンプルだが 'C'の位置候補でループ処理することしか考えていなかったので 文字列全体のループを別途作る?とか考えていた.

結局提出したのは,'C'の位置だけ記録して,元の文字列全体を小文字化した上で 'A','C'だけ大文字に変換して元の文字列と一致するか確認する方法. 実装直後に想像以上に汚い実装になったので悩んだけれど 結果は正しそうなのでさっさと提出してしまった.

C - All Green

解説の「中途半端に解く配点は1種類以下であり、それ以外の配点は完全に解くかまったく解かない」が全てだと思う. これに気付けなかったので全探索を諦めてしまったし,最後DPで解こうか悩んだ上で実装できなかった. 考えてみれば上記方針はあたりまえなのでこれは気付きたかった.

実装面ではビット操作による全探索に苦手意識があるのと, 完全に解く問題が与えられた上で,残りスコアを中途半端に解く場合に何問解けばいいかを

int need = (G - s + s1 - 1) / s1;

とコンテスト中にさらっと実装するのは無理だったかな,と感じた. どちらもわかっていれば大した事ではないのでしっかりと復習しておく.

D - We Love ABC

方針はCより簡単だった. DPを利用すること,処理した文字列の位置と処理状況を利用すること は比較的早く気付けたが,その後の実装が上手くいかなかった.

解説のように漸化式を上手く構築できればいいけど, 今回のような少し複雑な式になると,まだまだ解けそうにない. このあたりの感覚はもっと多くのDPを解いて慣れるしかないのかと考えてる.