Google Code Jam Round 1C 2022 B - Squary 解説
おもしろかった。気付いたときうわーーーーって言いました。
問題リンク
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877b42/0000000000afdf76
2023/07/16 追記 GCJ のサイトが閉じられたので、代替となるリンクを貼ります。
https://github.com/google/coding-competitions-archive/tree/main/codejam/2022/round_1c/squary
なお、GCJ の過去問のデータはこのリポジトリで参照できます。
問題概要
数列 に、 個以下の整数 ( 以上 以下) を追加し、以下の等式が成り立つようにしてください。
制約
- (テストケース数)
- (数列の長さ)
小課題
- 小課題 1 (9pts):
- 小課題 2 (22pts):
考察・解法
小課題 1
追加する数を とします。このとき、
ここで、 とおくと、
これが整数になれば良いです。
コーナーケースですが、
- のとき:
(つまり、全ての ) ならば何を出力しても良い。
そうでないならば、 では不可能。
には気をつけましょう。
小課題 2
追加する数を つに増やし、 として、 の満たすべき条件を求めます。
このとき、どのような数列でも実は適当な を取ることができます。
与えられた条件は、 について表すと、
となります。これでは について分かりにくい式なので、 が つの項にまとまるようにくくります。
ところで、 の偶奇は一致する (証明略) ので、右辺は偶数です。よって、 は整数となります (必要条件)。
の絶対値は を超えないので、適当に割り振っても良いです。
例えば、 とすればどのようなケースでも条件を満たす解になります。
実装
実装を展開する
public void Solve(int testcase) { var n = sr.ReadInt(); var k = sr.ReadInt(); var a = sr.ReadLongArray(n); var sum = a.Sum(); var squareSum = a.Select(i => i * i).Sum(); WriteCase(testcase); if (squareSum == 0 && sum == 0) { Console.WriteLine(0); } else if (sum == 0 || (squareSum - sum * sum) % (2 * sum) != 0) { if (k == 1) Console.WriteLine("IMPOSSIBLE"); else { var p = (squareSum + sum * sum) / 2; // solve for x, y s.t. (x+sum)(y+sum) == p // x = 1-sum, y = p-sum var x = 1 - sum; var y = p - sum; Console.WriteLine($"{x} {y}"); } } else { Console.WriteLine((squareSum - sum * sum) / (2 * sum)); } } public void WriteCase(int testcase) { Console.Write($"Case #{testcase + 1}: "); }
ACコード: 省略 (GCJ の提出コード共有するの面倒なので……)
感想
GCJ っぽい (本当に?) ギャグ問題でした。ギャグだけど、実は のときは で全部達成できる、みたいな考え方はよく見るかもしれない……。
解けたら気持ちいいけれど解けなかったらただただ不快になりそう……。