凍りました(もう凍ってから 1.3 年くらい経ってそうですね)。みなさんは今は Twitter (現 X) にいるのでしょうか。他の SNS への流出もありますか?まとめます。
実質 ARC175-E の解法記事なので、タイトル詐欺かもしれません
Twitter (現 X) 言及?
面白かった〜みたいな感想マジで嬉しいです、感想何個あっても嬉しいのでドシドシリプでください
— nok0 (@nok0_kyopro) 2024年3月24日
どしどし
コンテスト感想
楽しかったです(楽しかったので) 今回 A と C に五千年かけていたので E が通っても負けだと思っていたんですけど(C までを通したとき (85:53 (+1)) に D と E をちらっとみて E のほうが解けそうだったので E に特攻)、E があんまり通されていなかったのであたたまりでした
C はひとしきり迷走したあとにすっきりした解法になったので楽しかったです 実装もお気に入り
A は迷走したまま最後まで走り抜きました 実装もお気に入らず(ぽか) 問題(と想定解)はすきです
D と F は読んでません(ぽか)
E の解法
あんまり他の人が書いてなさそうな解法で解いていても Twitter にいないと気軽に書けなくてこまります(こまるので)
次のような図形を構築することを考えます(ここで、\(N\) は与えられる \(N\) と関係ありません。制約を満たす任意の \((N,K)\) で構築できるので、なるべく詰めておけば入力の \(N\) は見なかったことにしてよいためです)。
どのような \(K\) も \(N ^ 2+2S\) もしくは \(N ^ 2+2S+1\) として書けるので、上の形で構築ができればよいです。
ぐっと睨むと、次の \(3\) 集合で \(N ^ 2+2S\) が実現できることがわかります。
\[\lbrace (x,y,z)\mid x+y+z=S-2\wedge0\leq x,y,z\lt N\rbrace\] \[\lbrace (x,y,z)\mid x+y+z=S-1+N\wedge0\leq x,y,z\leq N\rbrace\] \[\lbrace (x,y,z)\mid x+y+z=S-1+2N\wedge0\leq x,y,z\lt N\rbrace\]
お気持ちとしては、\(\lbrace (x,y,z)\mid x+y+z\equiv S-1\pmod{N}\wedge0\leq x,y,z\lt N\rbrace\) に対して、\(\lbrace (x,y,z)\mid x+y+z=S-1+N\wedge N\in\lbrace x,y,z\rbrace\rbrace\) を付け加える代わりに \(\lbrace (x,y,z)\mid x+y+z=S-1\wedge0\leq x,y,z\lt N\rbrace\) の部分を \(1\) つずらす感じです(発想としては、\(S=1,2\) の構築を考えることで出ました。最初から見通しよくこの形だったわけではなくて、降順の列を rotate してがちゃがちゃしていました)。
\((N,N,N)\) は使われないことがわかる(\(S\leq N\) より、\((N,N,z)\) は入れることができない)ので、\(1\) として \((N,N,N)\) をいつでも入れることができます。
実装は以下のようになります。
#include <iostream> #include <cmath> #include <ranges> int main() { using namespace std; // 和が sum で各座標が 0 以上 limit 未満である (x, y, z) をすべて出力 constexpr auto sum_triplet{[](const unsigned sum, const unsigned limit){ for (const auto x: views::iota(0U, limit)) for (const auto y: views::iota(0U, limit)) if (const auto z{sum - x - y}; z < limit) cout << x << " " << y << " " << z << endl; }}; const unsigned K{*next(istream_iterator<unsigned>{cin})}, N(sqrt(K)), S{(K - N * N) / 2}; sum_triplet(S - 2, N); sum_triplet(S - 1 + N, N + 1); sum_triplet(S - 1 + N + N, N); if (1 & (K + N)) cout << N << " " << N << " " << N << endl; return 0; }