Educational Codeforces Round 11(2022/3/30)
A: Co-prime Array
隣り合う2項が互いに素でなければ間に1をはさんでやればよい.
https://codeforces.com/contest/660/submission/151418088
B: Seating On Bus
配列を用意して実際に着席, 離席をシミュレーションすればよい.
https://codeforces.com/contest/660/submission/151418836
C: Hard Process
区間のうち, 0をk個以下しか含まないもので, 区間幅が最も長いものを求めればよい.
区間内の0の個数をk個で保ったまま区間の右端を増加させていくと, 区間の左端は(広義)単調増加するので, 尺取り法が使える.
https://codeforces.com/contest/660/submission/151422400
D: Number of Parallelograms
同一直線状に3点が無いという有難い制約があるので 個の辺候補の中から, 傾きと長さが等しい辺のペアをカウントすればよい.
辺の傾きと長さをkeyにもつ連想配列を用意すればよい.
傾きは誤差が怖いので小数で持つのではなく, 互いに素な整数の組で持たせる.
類題? G - Isosceles Trapezium
https://codeforces.com/contest/660/submission/151423448
E: Different Subsets For All Tuples
数列の長さを伸ばしていき, 以降に付す項を部分列に含めるか否かのそれぞれを配列で持って動的計画法をすればよい.
https://codeforces.com/contest/660/submission/151425040
F: Bear and Bowling 4
良い進捗は産めなかった.
総括
1時間18分A~E5完1ペナ60位.
Educational Codeforces Round 12(2022/4/1)
A: Buses Between Cities
方針にかなり迷ったが, 実際にB市から発車するバスすべてに対し, 目的のバスとすれ違うかをシミュレーションすればよい.
https://codeforces.com/contest/665/submission/151622816
B: Shopping
制約が小さいので, 愚直に探し, 愚直に前に持ってきてを繰り返せばよい.
https://codeforces.com/contest/665/submission/151623028
C: Simple Strings
隣合う文字が等しければ後ろ側の文字をその両端と異なるように変更すればよい.
類題: Problem - D - Codeforces
https://codeforces.com/contest/665/submission/151623202
D: Simple Subset
長さ1の数列が条件を満たすことを失念していてペナにペナを重ねてしまった.
部分集合の2以上の要素について, それらの2つの和は4以上の素数すなわち奇数でないといけないため, 部分集合の2以上の要素数は2以下. (要素数が3以上だと必ず偶数同士or奇数同士のペアが作れてしまう)
上記と同様に, 1を要素に含むとき, 2以上の要素数は1つのみである.
2以上の要素数が1つのみで, それと1の和が素数ならば, 1は何個あっても良い.
以上から, 候補は, 「2以上の数2つ」,「2以上の数1つ以下と1がいくつでも」 のいずれかである.
前者も後者も, 和の最大値() 以下の素数を全列挙しておけば高速に求まる.
https://codeforces.com/contest/665/submission/151626722
E: Beautiful Subarrays
累積Xor→Trie木で良いと思うのだが, TLEやMLEをして通せなかった.
F: Four Divisors
素数2つの積か素数の立法数である数を数えればよい.
素数2つの積である 以下の数は小さい方の素数
を決め打ちすれば,
以下の素数がいくつあるかを高速に求められれば良く, これができることは知っていたので, 調べると Meissel–Lehmer algorithm 等が見つかる.
https://codeforces.com/contest/665/submission/151625495
総括
1時間16分ABCDF5完9ペナ79位. ペナは全てD問題で悔やまれる. Fは自前でないものを利用したのでこの機に整備しようと思う. 正直使い道はほぼないと思うが.
