0.はじめに
最近レートが徐々に上がってきたので調子に乗って参戦したところ
1問も解けずレートも32ダウン・・・。
1か月積み上げたレートが戻りました・・。
解説を見ながら解くと、A、Bともなんとか解けたので
めげずにチャレンジしていきたいと思いました。
1.A - Replace C or Swap AB
初見で、以下の場合分けで行ける！と実装するも
サンプルすら通らず・・・。
xの値 yの値 結果(同じ場合はOKとして)
AorB C ”No”
A B xの後ろの値がBorCで、yの後ろの値がAならok
B A xの前の値がAorCで、yの前の値がBならok
一回操作した箇所を繰り返し操作すればいろいろ何とかなるんだな
と気づき仕切りなおし。
Cで区切ったエリアごとの判断でよいと気づき
エリア内のXとYのAB個数が同じで、
X側とY側の値が異なる部分の先頭がAならOKと
雑に実装したところ、サンプルは通りましたが
WA13RE6と今一でした。
試験後解説と正解した人の解答を見たりして考慮しなおしたところ
以下の考え方でACとなりました。
・Cで区切られたブロック内のXとYのABの数をそれぞれカウント
・X内のA<Y内のAかつX内のB<Y内のBでなければ”No”を出力して終了
・X文字列内のCは先頭からチェックしていきY内のAと同じ数になるまでは
Aに変換し、それ以降はBに変換
・再度エリアを先頭から見ていき、それぞれのAの数を数える
Y側のAの数が上回るアドレスがある＝AB→BA変換でどうにもならなくなる
と判断し、”No”を出力して終了
・すべてのエリアでNoにならなかったら”Yes”を出力して終了
条件をロジックに落とし込む部分が1時間悩んでも出てこなかったところが
今後経験でひらめくようになるかは疑問ですが数をこなしていくしかないかなと
思いました。
https://atcoder.jp/contests/arc166/submissions/46396027
2.B - Make Multiples
A問題に行き詰ったときにふと見て、行けるかなーと思いましたが
まだAの方が行けそうな気がした気がしたのでスルーしました。
解説を読んで、なるほど感が強かったです。
3つ選ぶという条件を考えればあとは力技で行けるというのが
全く出てきませんでした。
実装は以下のようにしました。
【下準備】
aとb、bとｃ、aとc、aとbとcそれぞれの最小公倍数を求める
（コンテスト用Pythonのバージョン上がってlcm使えて楽でした。）
【リスト内数字毎の約数計算】
リストを頭から見ていき
a,b,c,ab約数,ac約数,bc約数,abc約数それぞれの倍数にするために必要な
操作回数をリストに格納。
リストは、a約数,b約数,c約数,ab約数,ac約数,bc約数ごとに作り
値はタプルで、左に約数に必要な操作数、右にインデックスを格納
abcについては、回答に使う場合には最小値の1つしか必要ないので
リストではなく、最小値を保持
【解答計算部】
[N＝1]の時
abcの倍数最小値を出力して終了
[N＝2]の時
N=2の時は、回答とするための組み合わせが限られるので
以下のそれぞれを算出し
abのリストの1つ目とcのリストの2つ目を足した数
abのリストの2つ目とcのリストの1つ目を足した数
acのリストの1つ目とbのリストの2つ目を足した数
acのリストの2つ目とbのリストの1つ目を足した数
bcのリストの1つ目とaのリストの2つ目を足した数
bcのリストの2つ目とaのリストの1つ目を足した数
abcの倍数最小値
その中で最小値を出力して終了
[N＝3]の時
それぞれのリストを昇順にソートし
先頭３つにカット(よく考えたら別にカットしなくてもよかった)
[3つの数を操作するケース]
aのリスト、bのリスト、cのリストから１つずつ選んで
インデックスがかぶっていなかったら合計値を保存
→その中の最小値を保持
[2つの数を操作するケース]
N=2の時の組み合わせで、リストからそれぞれ選んで
インデックスがかぶっていなかったら合計値を保存
→その中の最小値を保持
[1つの数を操作するケース]
abcの倍数最小値
上記3ケース内で、一番小さい数字を出力して終了
最初は、全組み合わせと考えたらどう考えても時間足りん！と思いましたが
ひと工夫で何とかなり目からうろこでした。
https://atcoder.jp/contests/arc166/submissions/46397079
以上