脳log[20220504]

2022年05月04日 (水) [AtCoder] 精進。灘校文化祭コンテスト 2022 Day1-D,F。有志コンに不用意に手を出して思い知らされるのは、AtCoder の ABC がいかに初心者向けに手心を加えてくれているか、ということ。難しくて解けないんだよ。■さて４問目。D 問題「Double Permutations」(400点)。ループする数直線上に N 個の点があって、点 0 からスタートする。1 から N-1 の歩幅を１回ずつ使って数直線上の N 点すべてに止まりたい。向きは変えられない。なにか雲を掴むような話。しらみつぶしに調べたいけど制約上限が 20 万で許されない。おおよそ線形時間で解きたい。一日放置していたら、ペアを作ってみようと考えた。雲は掴めないから共通の性質を与えて共通の取り扱いをする手掛かりとしたい。0 と N-1、1 と N-2 という感じで和が N-1 のペアが一番多く作れる。ペア１つにつき１周に１足りないからスタート地点の１つ手前に戻ってくる。これを繰り返すとどうなるか。N が偶数の時はうまく行きそう。N<10 の範囲で全探索したけど、N=1 を除いて N が奇数の時は解がない。提出 #31433409 (AC / 132 Byte / 127 ms)。なんでうまくいくのかはわからない。■F 問題「Mth Next Permutation」(６問目・500点)。Pi=1 と Pj=K を含む巡回グループの周期を考える。グループのメンバーを選び、並べ替え、グループ外の数列を並べ替え、掛け合わせる。提出 #31434643 (AC / 521 Byte / 202 ms)。K=1 の場合を特別扱いしたけど、うまく一緒に考えられるのだろうか。■全部で 16 問あるんだけど、解ける方が少ない。■■■精進２。灘校文化祭コンテスト 2022 Day2-A,B■A 問題「ACPN」(300 点)。実験したら M 個の剰余が出現する周期は K と M の最大公約数で分割されるようだった。たとえば M が 10 なら剰余は 10 種類あるが、K が 5 のとき最大公約数は 5 で、M 個の値は周期 2 の組が 5 組となって出現する。あとはこの周期で N が割り切れるかどうか。提出 #31438777 (AC / 70 Byte / 59 ms) 中国剰余定理はわからない。でもそろそろわかるかもしれない。■B 問題「Min Max Min」(400 点)。２日目は全体的に配点が１日目より高め、とはいえ２問目はまだ 400 点、なのにもう難しい。A と B の要素数の上限がどちらも 20 万だから、A と B の組み合わせを考えることがもう許されていない。どうするの？ 提出 #31440194 (AC / 386 Byte / 250 ms)。お風呂で考えた。数列を順番に見ていって、現在の要素を範囲の右端とする。この要素が最大値(最小値)として通用する範囲がどこまでかを調べる。最大値の範囲と最小値の範囲は食い違うわけだけど、広い方の範囲を採用する。その範囲で最大値の最大値最小値と最小値の最大値最小値の組み合わせ(２×２＝４通り。実際にはどちらかが１つの値しかとらないので２通り)の積が答えの候補。２問目でこれはなしだよ。３問目を読む気力がもうない。■B 問題の謎解答。提出 #31445298 (kotatsugame さん / 72 Byte / 167 ms)。短いだけでなく速い。なんで答えの候補を A.max*B.min と A.zip(B).map{|a,b| a*b } に限定していいのかわからない。この一連のツイートが Day2 の B 問題についてのものだろうか。「@kotatsugame_t これならひっかかってませんか？ https://t.co/CFIYrhdR68」「～のときは、区間は短いほど得なので、長さ１の区間のみで十分です。」 ああなるほどって思えないからこれが関連ツイートなのかどうかわからないんだよね。