Project Euler lv22(550問)達成 pic.twitter.com/M1nMuPSKlo
— ひとあれ (@hitoare1) September 3, 2020
本来は500問の時に書こうと思っていた。
限界が見えてきて精神的に一区切りついたタイミングで書いています。
数学の問題が解けるサイトです。
★→特におすすめ
競プロよりの問題
Investigating in how many ways objects of two different colours can be grouped
Tours on a 4 x n playing board
数学よりの問題
Investigating the primality of numbers of the form 2n^2-1
Constraining the least greatest and the greatest least
N個の自然数からなる集合\( \{A_i \}\)が与えられる。
この集合が「pairwise coprime」「setwise coprime」「そのどちらでもない」のどれかを判定せよ。
ただし、「pairwise coprime」とは、どの相異なる2要素もそのGCDが1であることであり、「setwise coprime」とは、pairwise coprimeでなく、全ての要素のGCDが1であることを指す。
まず、\(1 \leq A_i \leq 10^6\)なので、\(10^6\)以下の整数を高速に素因数分解できるようにエラトステネスの篩の要領で素因数のテーブルを作っておく。
自然数A,Bに対し、AとBのGCDが1であるとは、AとBが同じ素因数を持たないことと同値である。
よって、pairwise coprimeかどうかを判定するには、\(A_1\)から順番に素因数を保存しながら「\(A_k\)の素因数のうち\( A_1,...,A_{k - 1} \)までに出てきたものが存在するか」をチェックすればよい。
また、setwise coprimeであることと「\(A_1,...,A_N\)全てに共通する素因数が存在しない」ことは同値である。
よって、素数pに対し\(f(p)\)を\(A_1,...,A_N\)の素因数に出てきた回数として、\(f(p)=N\)であるものが1つでも存在するかどうかをチェックすれば良く、存在しなければsetwise coprimeである。
(追記:本番は上の方針を取ったが、実際は全体のGCDを取るだけでいい。)
https://atcoder.jp/contests/abc177/submissions/16325578
かなり数学よりだと思ったけど意外とAC数が多い。
\(H+1 \times W \)マスのグリッドがある。
グリッド上は右か下に移動できる。
ただし、上からk行目からk+1行目に移動する時、左から\(A_k\)マス目から\(B_k\)マス目の区間で下方向に移動するのは禁止されている。
一番上のWマスのうちのいずれかからスタートして、k+1行目に到達するまでの最小移動回数を\(1 \leq k \leq H\)に対して求めよ。到達不可能ならば-1を出力せよ。
縦移動の回数は決まっているので、横方向の最小移動回数を求める。
各行のWマスに対し、「その地点に到達するのに必要な横移動の最小回数」を上から順に更新していくことを考える。
区間最小値を求めるsegtreeを使う。
segtreeの中の要素を\(s[i]\)で表す。
k-1行目まで処理したとする。
この時、\(A_k \leq i \leq B_k\)に対し、\(s[i]\)を\(s[A_k - 1]+(i-(A_k - 1))\)で更新すれば良い。(禁止されていないギリギリの区間から回り込むイメージ。\(A_k=1\)の時は別途処理)
これを素直にやると更新が\(O(HW)\)回発生するので高速化する。
sは「1ずつ増加する」いくつかの区間に分割でき、1回の更新で1個の区間で上書きされる。
このような「中身が単純な区間で上書きする」タイプの更新は、区間の端点だけをsetで管理するのが有効(今回は始点だけで良い)。
\(A_k - 1\)と\(B_k+1\)での値を保存しておけば、残りは最小値となり得ないので、setから削除し\(s[i]\) をinfで更新してしまえば良い。
端点の追加・削除の合計回数は\(O(H+W)\)になり、segtreeやsetの操作でlogがつくが十分間に合う。
初期値では、1,...,Wの全てが区間の始点としてsetに全て入れておくと実装が楽になる。
https://atcoder.jp/contests/abc177/submissions/16363990
持ってないデータ構造(なんとかセグ木とか)を使いそうな気がしてめちゃくちゃ焦った。
