0.はじめに
ABCに引き続き開催のARC。せめて1問回答をノルマに挑戦し
なんとか1問AC頂けました。
B以降は、異次元の難しさだったので、すっぱりあきらめがつきました。
そんな感じでもレートは上がり、963という過去最高位となりました。
このまま900台キープを当面の目標としたいと思います。
1.A - No Attacking
チェスのこま置き問題。
まぁ実際におくのではなく、理論上置ける値を算出するタイプです。
段階的に考えていき最終的にACに至りました。
【考え方基本】
N<Aの時はどう考えても置けないから"No"
【考え方１】
・右上隅からルークを置いていき余った正方形に
置けるだけポーンを置く
→これだと、N=5、A=2の時、B=6が最高
Ａ＋－－－
＋Ａ－－－
｜｜ＢＢＢ
｜｜＿＿＿
｜｜ＢＢＢ
→例題すらうまくいかない。
【考え方２】
・ルークを2列目から2行毎に置けば縦はうまるが
横は、ポーンの移動スペースになるので結構置ける
→これだと、N=5、A=2の時、B=9置ける
｜｜ＢＢＢ
Ａ＋－－－
｜｜ＢＢＢ
＋Ａ－－－
｜｜ＢＢＢ
→例題はすべてAC！
Aが置けるのは、（N-A）の2乗まで
上の例だと、9個！
・・・
結果は、ACWA7つでした。
まぁ、例えばAが１の場合とか全然当てはまりませんね。
【考え方３】
・N-AがA以下の場合
考え方２の例のように、Aを置いた行すべてを
ポーンの移動先にできるため、BはN-Aの2乗置ける
・N-AがAより大きい場合
まず、Bは横にN-A列並べられる。
縦は、(N+1)//2行分並べられる。
ゆえに(N-A)*((N+1)//2)まで置ける。
・Bの値が上で求めた置ける数以下ならYes、でなければNo
として、ACとなりました。
https://atcoder.jp/contests/arc171/submissions/50006398
以上