Xmas Contest 2018 C: CombinatioN 解説
https://atcoder.jp/contests/xmascon18/tasks/xmascon18_c
問題概要
Pascal の三角形を書こうとしたが,ある場所で足し算を大きい値に間違えてしまった (→間違いがそこから伝搬).そして一部消えてしまった.というものが与えられるので,間違えた場所を特定せよ.
部分点解法
で間違えて 大きい値を書いてしまったときの影響を考えると, かつ を満たす のところが だけ大きくなることがわかります.
これを用いると,すべての を間違えた場所の候補として,与えられた条件がすべて満たされているか調べる,という解法が得られます (増えているところの情報から の値を求めて,複数個になったらダメ). 時間になります.
解法 1
制約をよく見ると,消えずに残っている値は 以下と書いてあります.ということは,正しい値以上が書いてある場所は なところしかありません.これは よりだいぶ少なくて, では 箇所です.
大きい方にしか間違えないので,正しい値未満が書いてあったら IMPOSSIBLE
です.これで弾かれなければ,部分点解法で間違えた場所 を決め打ったあと調べる箇所が から になるので,間に合うかもしれない気がしてきます.実際,実装の定数倍や言語次第かもしれません.
もう少し速くするには,間違えた場所の候補 を試すとき, なら間違えても情報が出てこない,ということを用います.まとめるとこんな感じ:
正しい値未満が書いてあったら IMPOSSIBLE foreach (i, j): if check(i, j): (i, j) を答えの候補に追加 答えの候補が 0 個なら IMPOSSIBLE,1 個ならそれを出力,2 個以上なら AMBIGUOUS function check(i, j): if C[i][j] > 10^9: 正しい値より大きい値が書いてあれば return false // これは前計算しておく return true foreach 何か書いてある (k, l): if k >= i and l >= j: x := (A[k][l] - C[k][l]) / C[k - i][l - j] x が正の整数でなければ return false x を x の候補に追加 else: A[k][l] = C[k][l] でなければ return false x の候補が 2 個以上なら return false return true
これなら一番計算が重い部分が で,無事間に合います.
解法 2
正しい値より大きい値が書いてある場所 をひとつ決めると,間違えた量 は の約数なので,それをすべて試します.正しい値より大きい値が書いてあるという情報から,間違えた場所 がどんどん絞られていきます.というのも, の値から と がほぼ決定されるからです ( のときを除いて,最大 通りしかないようです).
計算量のボトルネックは, とかになります.実装は結構大変かもしれません.さらに,AMBIGUOUS
等の判定で間違えがちです:例えば,一番下の段でひとつだけ消えていて,他が全部正しいとき,正しい値しか書いていないですが間違えた場所は一意に特定されます.
コメント
適当に問題設定を考えついて,最初は約数を調べる解法を思いついて適当に投下したのですが,snuke さんがすぐに言ってきた素直に全箇所調べる解法が十分速いことに気づき,簡単めでいいかな~と思って採用されました.しかしはまりがちポイントが大量にあることが徐々に発覚し,綺麗な実装ができますかという問題に.一発で通せた方はすごい!
Xmas Contest 2018 B: Bit Smaller 解説
https://atcoder.jp/contests/xmascon18/tasks/xmascon18_b
問題概要
とか, とか,そういうののうち 以下のものをすべて求めよ.
解法 1
全探索しましょう.数の切り方は高々 通りしかないのでなんとかなると思います.
先頭のほうから切っていく感じで再帰で実装するのもよいと思います.
枝刈りとかがんばらない限りは実行にそれなりに時間がかかりますが (わたしのは数分でした),答えだけ出せばいいので安心.
たちの積を求めていくより で 回割っていく,みたいなののほうがオーバーフローを気にせずに済んで枝も刈れていろいろお得かも (ただし に注意).
解法 2
親切にもふたつめの答えまで書いてあるので OEIS で検索すると見つかります.が,
- "not ending with 0" と書いてあるように,条件を満たす数の末尾に をつけてもやはり条件を満たす
- 切り分けたときに が入っていたり で始まっていたりそういうのも含まれている
ことに注意してください.
コメント
面白算数 (?) ネタを見つけたので易しめの問題にしてみました.作問陣は OEIS で検索するのをすっかりさぼっていたのですが,微妙に条件が違って逆にトラップになってたようで面白いですね.
この問題の範囲では一の位が (か ) の解しかないですが,他がないわけではないです (問題概要のとこの例とか).
みたいに最後の部分がないパターンも綺麗ですが,探索で見つかる範囲だと全然ないようです.桁を増やせば,例えば とかがあります (見た目がやばいですがこうやって構成されています: https://math.stackexchange.com/a/2126667).