0.はじめに
最近ARCの調子も上がらない感じですが、まぁ、一回さぼると
さぼり続けそうなので参戦。
AがさっぱりでBを見たところ、意外と行けそうだったので
何回か再提出を繰り返しつつもAC達成。
そのかいあってレートも+27の943と最盛期に近づけました。
1.A - Spoon Taking Problem
右手左手に順番と円状と、コンテスト時はとっかかりすらつかめず
お手上げでした。
解説を見て、スプーンの取り方は、全員右を取るパターンと
全員左を取るパターンしかないと分かり、まずそこに気づかないと
解けないんだなーっとわかりました。
逆に、そこさえ気づけば、右回りパターンと左回りパターンの
合計で算出できました。
https://atcoder.jp/contests/arc175/submissions/51659825
2.B - Parenthesis Arrangement
アットコーダーにありがちなかっこの組みあわせ問題。
いろいろ試行錯誤の上3回WAを出しながらも解けました。
【考え方】
文字列Sから、すでに向きあっている括弧を省き
組み合わせがない右かっこの数をRC、左かっこの数をLとする
最小コストで正しい括弧列に操作するパターンは以下の3つ
(1)全部コストAの操作で正しい括弧列にする
LとRCがそれぞれ3個ある場合、コストAの操作2回で
正しい括弧列にすることができる。
123456
)))(((
↓1と6を入れ替える
123456
())(()
↓3と4を入れ替える
123456
()()()
(2)LとRCの小さい方のうち偶数分だけコストAの操作、
残りをBの操作で正しい括弧列にする(LとRCの小さい方が奇数の時のみ可能)
LとRCがそれぞれ3個ある場合、コストAの操作1回とコストBの操作2回で
正しい括弧列にすることができる。
123456
)))(((
↓1と6を入れ替える
123456
())(()
↓3と4を入れ替える
123456
()()()
(3)全部コストBの操作で正しい括弧列にする
LとRCがそれぞれ3個ある場合、コストBの操作6回で
正しい括弧列にすることができる。
123456
)))(((
↓1~6を入れ替える
123456
((()))
上記3パターンをすべて計算して、一番小さい数を
出力することでACとなりました。
解説と若干違うのかな。(解説の内容をあまり理解できていない)
https://atcoder.jp/contests/arc175/submissions/51651993
以上