0.はじめに
ARC久々だなーと思い調べたら、前回は7/9なので、2か月ぶりでした。
その時はQIITA記事書けない位の惨敗でした。
今回も、Aすら解ける気はしなかったのですが、あがいているうちに
なんとかAだけは解け、Bも時間は足りませんでしたが
解き方を模索できるくらいは問題を理解できました。
結果として、レート+17と昨日と合わせて今週だけで+34も
あがりました。
1.A - Sum equals LCM
初見でレーティング参加を後悔しましたが、試行錯誤の上
なんとか解いていけました。
【考え方１】
N=6の例をみて、最小公倍数が6になる
かつ、合計が6以下となる、2個以上の数列は2と3であるが
そこに1を足している・・・
→合計の条件を満たすために、1はいくらでも追加できる。
→最小公倍数をみたすリストの合計がNを超えなければ
そこに1を追加していけば条件を満たす
→最小公倍数をみたすリストの合計がNを超えないためには
Nが素数でなければよい、
（素数だと、リストは2個以上の値が必要なため、
１とNが最小公倍数リスト候補となり足すとNを超えてしまう。）
★Nが素数でなければなんとかなる！
→実装した結果WA
【考え方２】
N=4の例を見て、素数でもなんとかならないことを悟る
★Nが5以下は条件を満たさない！
→実装した結果WA
【考え方３】
N=9の時を考えると、素数ではないが、リスト候補には、3しか上らず
3が2つあっても最小公倍数は3のため、条件を満たさない
★Nが素数で2回割れたらだめ！
→実装した結果WA
【考え方４】
N=27の時を考えると、素数ではないが、リスト候補には、3しか上らず
3が3つあっても最小公倍数は3のため、条件を満たさない
★Nが素数で2回以上割れたらだめ！
→実装した結果WA
【考え方５】
N=72の時を考えると、素数で２回以上割れるが、A=9,8,1を55個
と、条件を満たせる。
★Nが素数のべき乗だったらだめ！
→実装した結果AC
と、トライアンドエラーを繰り返して正解にたどり着きました。
【実装】
[素数リスト作成]
実装は、１つ１つ素数で割っていったらまにあわなそうだったので
まず素数のリストを作ろうと思い、ぐぐったら、エラトステネスの篩で
素数を求める例があったのでこぴって使いました。
素数リストの上限は、Nの最大値の0.5乗≒31623までとし
最初に素数リストLを作成。
[条件を満たさないかの判定関数 is_prime、条件を満たさない時Trueを返す]
※考え方の最初、素数だったらだめ！というときに作った関数なので
素数判定のような関数名になっている
1)変数chkに0をセット
(chk:n以外で素数で割切れるかつ、素数のべき乗でない場合1をセット)
2)for文でリストLの要素をxに入れて一つずつチェック
2-1)nがxで割り切れる場合
2-1-1)chkNにnをxで割った値をセット
2-1-2)変数flgに0をセット
2-1-3)flgが0の間以下を繰り返す
2-1-3-1)chkNがxで割り切れる場合
2-1-3-1-1)chkNにchkNをxで割った値をセット
2-1-3-1-1-1)chkNがxで割り切れない場合flgに1をセット
2-1-3-2)chkNがxで割り切れない場合はflgに1をセット
↑ここら辺はループしているのに次のループでするべき判定を
先取りしていて冗長なのでごちゃっとしている
2-1-4)chkNが1の時、nはxのべき乗であるためTrue(条件を満たさない)を返す
2-1-5)chkNが1でない時、chkに1をセット
2-2)nがxで割り切れない場合は次のxへ
3)chkが0の場合、Trueを1の場合Falseを返す
[メイン処理部分]
1)Tを読み込む
2)以下T回繰り返し
2-1)Nを読み込む
2-2)Nが5以下の時Noを出力
2-3)Nが6以上の場合
2-3-1)is_prime(N)の戻り値がTrueの場合Noを出力
2-3-1)is_prime(N)の戻り値がFalseの場合Yesを出力
忘れないようにまとめましたが無駄に長くなったし
内容も書き直したくなるくらい無駄が多いなと思います・・・。
https://atcoder.jp/contests/arc165/submissions/45679114
2.B - Sliding Window Sort 2
コンテスト中はなんとなく直感でこうすればよさそうというのは
思い浮かんだのですが、実装まで落とし込めませんでした。
まぁ、解説を読んでもパット理解できなかったので、直感も
あってたかはわかりませんが・・・。
解説を読んで理解した考え方を忘れないよう自分の言葉でメモ。
【考え方】
１）操作をすることによって、辞書順が大きくなることは無い。
最大でも、元のリストと同じ状態。
→操作しても辞書順が変わらないケースは
リストの値が、K個昇順に並んでいる場合なので
そのような並びがあった場合は、リストをそのまま出力して終了
２）辞書順を大きくするためには、なるべく元のリストの儘が良い。
変える場合も、先頭の方は変えない方がよいので
リストのうしろから、K個をソートしたリストを回答候補1として保持
３）回答候補１と元のリストを先頭から比較して、一番最初に
差異が出た位置をiとしたとき、iの前の部分が昇順に並んでいたら
その並び順を活かす方が変化が少ないため、iを含むK個の列の値のうち
iより前の部分の昇順な並びが最大になるような位置からK個を
ソートした値を回答候補2として保持
４）回答候補１と回答候補２のうち、辞書順で大きい方を出力して終了
一応メモとして残しましたが、解説放送を見た方が、理解しやすいかと思いました。
https://atcoder.jp/contests/arc165/submissions/45688012
以上