人権なし

競プロで解いた問題や開発の進捗などの記録です

JOI 夏季セミナー 2019 に通りました

7/21 に選考結果が来ると思いきや,1 日ほど遅れたみたいですね(選考がかなり難航していた?).去年も参加して今年も通ることができたのでよかったです.例年以上に一般枠での応募が多かったようで,TL の方々でも落ちている方がいらっしゃるようです.もっと定員を増やしてもいいのに・・・と思います.ところで,作文でどのように評価されるのか気になるところです.僕は以下のように書いたら通りました.

情報オリンピック日本委員会 様

夏季セミナーへの参加を希望します.

・氏名:

・学校名:

・学年:

・JOI 春合宿の参加年度:2018/2019

・興味を持っている分野,夏季セミナーへの抱負:

去年の夏季セミナーにも参加させて頂き,「暗号理論」を学習テーマとして選択しました.一方で,自分は昔から競技プログラミングを続けていたため「グラフ理論」にも興味があったので,これも選択してみたかったです.そのため,自分の興味のある競技プログラミングに通じる分野を今年度選択可能でしたらぜひ選択したいと思っています.今年度が最後のJOIに関わる年になるので,他校の方々との交流も積極的にしたいと考えています.

選考の方よろしくお願い致します.

夏季セミerの方々,よろしくお願いします.

AtCoder Beginner Contest 134:E - Sequence Decomposing

問題

https://atcoder.jp/contests/abc134/tasks/abc134_e

解法

単調増加列の数を最小化すればよい.既に色を塗った整数以外で新しく単調増加列を構成することを考える.ここで,残っている数字の中で最も大きいもののうち一番左にあるものは新たに作る単調増加列の終端になる.なぜならば,この数字より大きいものはないから.次に,この数字より前の位置にある中で最も大きいもののうち一番左にあるものを先ほどの数字の前にする.これを繰り返すことで単調増加列を 1 つ構成出来る.数字を追加する各段階で最も大きい数字を選んでいるので,単調増加列の数を最小化することができる.O(N * 3logN) ぐらい?

解答

https://atcoder.jp/contests/abc134/submissions/6485524

実装にとても時間がかかってしまった.

f:id:babcs2035:20190721215349p:plain

 

AtCoder Beginner Contest 134:D - Preparing Boxes

問題

https://atcoder.jp/contests/abc134/tasks/abc134_d

解法

i = N, (N - 1), (N - 2), ... の倍数の順番に考えていく.そうすると i 番目の箱にボールを入れるかどうか決める際 i * 2, i * 3, ... 番目の箱にボールを入れるかどうかは既に決まっているので,これらの箱に入れたボールの総数の偶奇と a_i が異なる場合のみ i 番目の箱にボールを入れればよいとなる.全体で計算量は O(N / 1 + N / 2 + N / 3 + ... + N / N) となり O(NlogN) となる.これは N / x を 1 ~ N で x について定積分すると NlogN となるから(らしい).

解答

https://atcoder.jp/contests/abc134/submissions/6484703

スムーズに解法を思いつけたので良かった.

f:id:babcs2035:20190721213412p:plain

 

AtCoder Beginner Contest 126:F - XOR Matching

問題

https://atcoder.jp/contests/abc126/tasks/abc126_f

解法

M = 0 のとき,答えは自明に (0, 0).

M = 1 のとき,K = 0 のときしか答えは存在しない.

それ以外のとき,K < 2^M ならば答えが存在する.なぜならば,K >= 2^M のときには 0 ~ (2^M - 1) の数で xor をとっても 2^M になりえないから.答えは (K 以外の 0 ~ (2^M - 1) を降順に並べたもの), K, (K 以外の 0 ~ (2^M - 1) を昇順に並べたもの), K となる.2 つの K の間に含まれる (K 以外の 0 ~ (2^M - 1) を昇順に並べたもの) の xor は 0 ~ (2^M - 1) すべての xor が 0 であることより,K になる.また,2 つの K 以外の数の間に含まれる数は K 以外 2 回含まれるので xor は K になる(同じ数で 2 回 xor を取れば 0 になるので).O(2^M).

解答

https://atcoder.jp/contests/abc126/submissions/6432111

600 点問題にしては簡単だと思った.

f:id:babcs2035:20190719155433p:plain

 

AtCoder Beginner Contest 126:E - 1 or 2

問題

https://atcoder.jp/contests/abc126/tasks/abc126_e

解法

(X_i, Y_i) のカードは他方が分かればもう片方もわかる関係である.なので,(a, b), (b, c) とあったとき a が分かれば b も c も同時にわかる.このようなカードの連結成分内のカードは 1 つのカードのみ魔法を使って知ることで全て知ることができる.よって,答えは連結成分数になる.Union-Find 木などを使って実装して O(N + M).

解答

https://atcoder.jp/contests/abc126/submissions/6431380

簡単目な 500 点問題だと感じた.

f:id:babcs2035:20190719141512p:plain

 

AtCoder Grand Contest 035:C - Skolem XOR Tree

問題

https://atcoder.jp/contests/agc035/tasks/agc035_c

解法

N = 2^k であるときは No.なぜならば,N - (2 * N) のパス間で k bit 目が 1 であるものはないため,xor を N にすることは不可能だから.そうでないときは全て Yes となる.入出力例にある N = 3 のときのものに 4 - 5, 5 - (N + 1), (N + 1) - (4 + N), (4 + N) - (5 + N) と頂点と辺を足していく.これによって N が奇数である場合で解けた.N が偶数である場合は,(a ^ 1 ^ b) == N となる a, b の組を見つける必要がある.例えば,a = N - 1 とすると b = ((N - 1) ^ 1 ^ N) + N と定まる.O(N). 

解答

https://atcoder.jp/contests/agc035/submissions/6423841

f:id:babcs2035:20190718153317p:plain

数が 1 だけ増えていくことを考えられれば 1 の周りに付け足していく方針がたったと思う.

 

AtCoder Grand Contest 035:B - Even Degrees

問題

https://atcoder.jp/contests/agc035/tasks/agc035_b

解法

まず,辺の数が奇数の時は答えは No になる.偶数の時は答えを構成することができる.

簡単な場合として根付き木を考える.このとき各頂点の出次数の偶奇は葉から各辺の向きを決めることで操作することができる.具体的には,頂点 v の出次数の偶奇を変えたい場合は頂点 v の親の頂点に向けて辺の向きを設定すればよく,変えない場合はその逆の向きにすればよい.根の出次数は,ほかの頂点の出次数が全て偶数であり辺の数も偶数であることから,必ず偶数になる.

与えられたグラフは連結なので必ず全域木を構成することができる.この全域木に含まれる辺以外の辺の向きは適当に決めてしまう.そうすることで,全域木においての各頂点の出次数の偶奇が決まる.この決まった偶奇をもとに全域木の葉から順に前述の通りに操作をしていけばよい.O(N + MlogM).

解答

https://atcoder.jp/contests/agc035/submissions/6413394

グラフの簡単な場合として木から考えるという考え方を学んだ.

f:id:babcs2035:20190717145603p:plain

 

AtCoder Grand Contest 035:A - XOR Circle

問題

https://atcoder.jp/contests/agc035/tasks/agc035_a

解法

(a ^ b) == c は (a ^ b ^ c) == 0 と同値より,高々 3 種類の数字しか登場してはならない.3 種類の場合は (a ^ b ^ c) == 0 となる a, b, c がそれぞれ N / 3 個,2 種類の場合は 0 でない整数が N / 3 * 2 個と 0 が N / 3 個,1 種類場合は 0 が N 個あれば条件を満たすので,この 3 パターンのどれかに当てはまるかどうかを確かめればよい.O(NlogN).

解答

https://atcoder.jp/contests/agc035/submissions/6377108

f:id:babcs2035:20190717144224p:plain

 

AtCoder Beginner Contest 132:E - Hopscotch Addict

問題

https://atcoder.jp/contests/abc132/tasks/abc132_e

解法

各頂点についてけんけんぱの k 歩目 (0 <= k <= 2) で到達するために辺を通る回数の最小値を求めることを考える.これは,各頂点について 3 つの状態(けんけんぱの歩数)をもっておき,ダイクストラ法を適用することで求めることができる.答えは頂点 T をけんけんぱの 0 歩目で到達するための最小のコストを 3 で割ったものになる.O(MlogN).

解答

https://atcoder.jp/contests/abc132/submissions/6351877

f:id:babcs2035:20190713140906p:plain

 

AtCoder Beginner Contest 132:D - Blue and Red Balls

問題

https://atcoder.jp/contests/abc132/tasks/abc132_d

解法

i 回操作が必要なとき,青玉が連続している区間が i 個あるということなので,(N - K) 個ある赤玉の間と左端と右端の (N - K + 1) 個の隙間に青玉の区間を i 個当てはめればよい.これは C(N - K + 1, i) 通りある.また,i 個ある青玉の区間のそれぞれに何個青玉を割りふるかを考える.各区間につき最低 1 個は割り当てないといけないので (K - i) 個の青玉を i 個の区間に当てはめればよい.これは C(K - i + (i - 1), i - 1) = C(K - 1, i - 1) 通りある.この 2 つの通り数を掛け合わせたものが答えになる.前処理でコンビネーション計算をする必要がある.O(N + K).

解答

https://atcoder.jp/contests/abc132/submissions/6351749

f:id:babcs2035:20190713135713p:plain