-
Notifications
You must be signed in to change notification settings - Fork 0
ARC lessons learned4
ARC Div.2にratedで参加します。
ARC rated初参加だった。A,B 2完を42:34ノーペナで、初の青パフォである。
コードはこちら
両者の全カードの和は
-
$S mod M = 0$ なら、Bobは最後の一枚を引かされるのでAliceの勝ちである -
$S mod M > N$ なら、Aliceは最後に$1..N < M$ を出し、Bobは最後の一枚を引かされるのでAliceの勝ちである - それ以外
$0 < S mod M \leq N$ なら、Bobは最後に$1..N$ を出せるが、その前にカード出すAliceは場のカードの和が$M$ の倍数にならざるを得ない。よってBobの勝ちである。
コンテスト中の思考の過程を追う。
- Grundy数かと思ったら、このゲームは可能手がすごく多い。
-
$1..N < M$ より、場のカードの和が$M$ の倍数になる=負けるような手をほぼ確実に回避できる。公式解説を読んで再認識したが、カードはそれぞれ異なるので手札が2枚以上あれば確実に負けを回避できる。 - 最後の1ターンは出すカードに選択肢がない時である。ここで勝敗が決まるだろう。
- 後手が詰む一つの状況は、すべてのカードが出切ったときで、
$N(N+1) mod M = 0$ である。 - 後手が最後に出すカードを
$S \in 1..N$ とする。$N(N+1) - S mod M = 0$ なら後手がカードを出す前に、先手は場のカードの和が$M$ の倍数にならざるを得ない。条件を言い換えると、$N(N+1) mod M \in 1..N$ である。 - 同様の議論から、上記でなければ、先手は負けず後手が負ける。
上記をまとめると、 Bob 、そうでなければ Alice が 答え である。
今回は理詰めで提出したが、ゲーム木を構築して解を推測することもできる。
// 0 means the first player wins
Num visit_dfs(std::vector<Set>& hands, Num turn, Num accum, Num m) {
const auto other = 1 - turn;
if (hands.at(turn).empty()) {
return other;
}
if (hands.at(turn).size() == 1) {
const auto s = accum + *hands.at(turn).begin();
return ((s % m) == 0) ? other : turn;
}
Vec vs;
for(const auto& x : hands.at(turn)) {
vs.push_back(x);
}
for(const auto& x : vs) {
const auto s = accum + x;
if ((s % m) == 0) {
continue;
}
hands.at(turn).erase(x);
const auto result = visit_dfs(hands, other, s, m);
hands.at(turn).insert(x);
if (turn == result) {
return turn;
}
}
return other;
}
void solve(std::istream& is, std::ostream& os) {
const std::vector<std::string> players {"Alice", "Bob"};
for(Num m{2}; m<=10; ++m) {
for(Num n{1}; n<m; ++n) {
std::vector<Set> hands(2);
Num total = n * (n+1);
for(Num i{0}; i<2; ++i) {
for(Num j{1}; j<=n; ++j) {
hands.at(i).insert(j);
}
}
const auto r = total % m;
const auto r_in = (1 <= r) && (r <= n);
os << "m=" << m << ", n=" << n <<
", mod=" << r << ":" << ", 1<=r<=n " <<
players.at(r_in) << " " <<
players.at(visit_dfs(hands, 0, 0, m)) << "\n";
}
}
}コードはこちら
ゼロサムなので、全要素が平均値付近にそろっている状況を作れる。つまり全要素の差を高々1にする。具体的には、
後は操作に矛盾がないことを確かめる。 No 、見つからなければ Yes が答えである。
この方法は公式解説1と同じである。ARC早解きで勝てるなら不変量だろうと思っていたら、強運が向いた。
ARC rated 2回目は、120分掛けて一問も解けなかった。前回のように上手くはいかない。
コードはこちら
解けるとすればA問題しかなさそうというのは、問題文からも順位表からも分かったので、ひたすら問題に集中して悩みはなかった。
手番の途中で広義単調増加になったら即刻打ち切ってよい。
隣り合う数 No はなさそうだが証明できない。
翌朝気が付いたことに、
ここまでくれば解法が分かる。まず入力が広義単調増加なら何もしない。 No である。
コンテスト後に Yes 1 1 を間違えていたが、最後の2 WA 1 msec だと自分で気が付いた。
数列が広義単調増加かどうかは、 std::ranges::is_sorted で調べられる。返り値は狭義単調増加ではなく広義単調増加(非減少)かどうかである。
ARC rated 3回目、B問題 1完だった。コンテスト中に青diffをACしたのは初めて、26:17ノーペナで初の黄パフォである。最大瞬間18位から逃げ切った。A問題よりB問題の得点が高いことに助けられた。A問題は90分掛けたが全く分からなかった。
コードはこちら
DPだと思ったが、それ以上のことは分からなかった。
よい文字列の定義は、 A,B,C それぞれの出現回数の偶奇がそろっているもの、と言い換えられる。これを8状態として区別できる。公式解説にある通り偶奇が反転している状態を同一視して4状態に減らすことができる、と言うことに気が付かなかった。
ある状態に挟まれた文字列はよい文字列である。これは整数列の累積和について、
公式解説にある状態遷移が巧妙である。
コードはこちら
丁寧に場合分けする。
Yes である。
No である。
Yes である。そうでなければ塗れない頂点があるので No である。
以上で答えを網羅できた。公式解説と、
コンテスト中の思考の過程を追う。
-
$N$ と何かが互いに素なら、同じことを繰り返してすべての頂点を塗れる。そうでなければ塗り残しがある。この何かを求めればいいと直観的にすぐわかる。 - マルチテストケースなので、エッジケースを間違えると大量のWAが返ってきて、根本的に解法が間違っているのかそうでないのか分からない。よって最初にエッジケースを挙げて、それ以外の場合分けを丁寧に行う。
- 題意を理解するために手を動かす。
$N = 2$ が特殊だと分かる。互いに対称な位置なら詰むのも分かる。 -
$N$ が偶数なら初手は自分の位置か対称な位置しかないので、とりあえず対称な位置に打って、直前に打った点の対称な位置に打つのを繰り返す。$N$ が奇数の場合も同様に繰り返す。以後原点を読み替えるだけなので周期性があり、これで全頂点を塗れるだろう。 -
$gcd(N,x) = gcd(N,N-x)$ なので、$K$ を$N - K$ に読み替えてもよい。これで場合分けが減る。符号を入れ替えても最大公約数は変わらないので、絶対値を取って場合分けを減らす。 - これ以上場合分けは無いので提出したらACした。最大瞬間順位から想像するに、この時点で多くの方はA問題を解いている途中で、B問題を最初に取り組んだ方は少なかったのかもしれない。
コードはこちら
Div.2 になって400点問題が出たのに、120分掛けて一問も解けなかった。ARCはそれほど甘くない。
解になりえないものを除外する。両端は変えられないので
リバーシ操作は、両隣が異なる場所
入力 1010... では、幅
以下ラン長はすべて奇数とする。ラン長が1のランは何も操作しないので無視する。ラン
異なるランの操作について順列組み合わせを考える。
101 の真ん中を 1 で塗るリバーシ操作しかないので分かる( 010 を反転しても同じなので、以後 0 と 1 を入れ替えた場合は考えない)。
公式解説は上記と同じことを言っている。特に、あるランの操作回数
コンテスト中の思考の過程を追う。上記に書いた
解になりえないものを除外する。両端は変えられないので
ランの要素をすべてそろえることを考える。両端はそろっているので、両端の間に
反転方法は二通りある。一つは
あるラン
と思ったのだが、入力例以外が答えが全然合わない。実験コードを15分で書けば分かったことである。しかしそれ以外のことに気を取られ過ぎて、実験コードを書こうと思わなかったのは反省点である。以下にある通り、 10... を 11... に変える方法を総当たりで求める実験コードはそれほど複雑ではない。
using Pattern = std::bitset<32>;
using Seq = std::vector<std::pair<Num,Num>>;
Num visit_dfs(Pattern current, const Pattern goal, Num width, Seq& seq) {
Num total {0};
if (current == goal) {
for(const auto& [l,r] : seq) {
std::cout << l << ":" << r << " ";
}
std::cout << "\n";
return 1;
}
for(Num left{0}; (left+1)<width; ++left) {
bool stop {false};
for(Num right{left+1}; !stop && right<width; ++right) {
if (current[left] == current[right]) {
stop = true;
const auto s = right - left;
if (s <= 1) {
break;
}
auto next = current;
for(Num i{left+1}; i<right; ++i) {
next[i] = current[left];
}
if (current != next) {
seq.push_back(std::make_pair(left+1, right+1));
total += visit_dfs(next, goal, width, seq);
seq.pop_back();
}
}
}
}
return total;
}
void full_search(std::istream& is, std::ostream& os) {
Num width = 5;
is >> width;
Pattern current(0);
for(Num i{0}; i<width; i+=2) {
current.set(i);
}
Pattern goal(0);
for(Num i{0}; i<width; ++i) {
goal.set(i);
}
Seq seq;
os << visit_dfs(current, goal, width, seq) << "\n";
}
int main(void) {
full_search(std::cin, std::cout);
return 0;
}コードはこちら
コンテスト数日後に解けた。Diff 1889 の問題を解けたのは、次回に期待が持てる。コンテスト中は15分掛けて分からなかったので見限ったが、分かってしまえば実装は簡単である。
この問題の要点は、コマではなくコマの間隔を移動できることである。コマの間隔を移動を左から右に移動できることを示す。右から左に移動するのは左右対称にするだけなのでやはり可能である。
左の端のコマが原点
どのコマがどこに移動したかは気にしない。元のコマがどこにあったかを気にせず、初期配置から
ここから分かるのは操作1回で、
答えを最小にするには、間隔が少ないものほど左側に寄せればよい(間隔が大きいものが左側にあるなら、右にある間隔と入れ替えると答えを小さくできるので)。よって偶数番
ソート後の
この方法は公式解説と同じである。
コードはこちら
コンテスト中にはちらっと見たが解けそうも無いと諦め、その後4日ほど考えたが、全く答えが分からなかった。スライムは倍化することが計算量を決めるという発想に至らなかった。
スライムを大きくするのではなく、これ以上大きくならないという壁に注目するのは正しかった。しかし計算量の見積もりができず
この問題の2が次のABC 384に出た。こちらは緑diffのとっつきやすい問題だが、ペナルティを出してしまった。