最終更新: 2021-06-05T05:03+0900
解説画像はこちら>https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg
この問題はとても良かった。確実に力になった。問題を解く選択肢が増えた。キーワードは「行列の掃き出し法を知ろう」だって。
最初は独力でパネルを順番に見ていく DFS を書いた。それしか知らない。だけどどうしても入力に左右されるし、あるパネルに影響する複数のスイッチの組み合わせを総当たりするので遅くなる。
入力を前処理して扱いやすくするとは考えてもみなかった。
でまあ今後は、こういうことができると知ったはいいけど、これが適用できる対象の性質を見抜けるかどうか、というところに課題が移ったとみていいのではないかな。簡単ではないね。
具体的な実装にも迷いがある。スイッチ数(N)、パネル数(M)の上限が 300 なのに対して 550 ms の時間をかけている。メインループだけど、
ステップ１の処理が N で、ステップ２の処理が N×M。もっとシュッと片付くうまい書き方があっても良さそうでは？
hai!@magrofly「典型057 Ruby https://t.co/Dri1yBSvuK」 / Twitter
「基底を求める」のはよくわからないけど、「解く」過程では順番に適用していくだけでいいようだ。さっきの手順に当てはめると、基底を求めるのがステップ２に相当して、解く部分がステップ３。ステップ１の検索が不要であると。
最初の提出。無駄にソート、検索している(９行目)。
N,M = gets.split.map(&:to_i)
A = N.times.map{
gets
next gets.split.map{_1.to_i-1}
}
S = gets.split.map(&:to_i)
n,T = 0,[0]*M
while as = A.sort_by!(&:first).shift
i = as[0]
A.map!{|bs|
i < bs[0] ? bs : ((as|bs)-(as&bs)).sort
}.reject!{|bs|
bs.empty? && n+=1
}
as.each{|i| T[i] = 1-T[i] } if S[i]!=T[i]
end
p(S==T ? 2.pow(n,998244353) : 0)
ツイートを参考に改良したが、あまり良くはならない。N,M<=300 だから？ 対称差を求める部分(15行目)が富豪的過ぎるから？ 前処理の部分でまだちょっと変なやり方をしてる？
N,M = gets.split.map(&:to_i)
A = N.times.map{
gets
next gets.split.map{_1.to_i-1}
}
S = gets.split.map(&:to_i)
N.times{|i|
next if A[i].empty?
(i+1...N).each{|j|
next if A[j].empty?
if A[j][0] < A[i][0]
A[i],A[j] = A[j],A[i]
elsif A[j][0] == A[i][0]
A[j] = ((A[i]|A[j])-(A[i]&A[j])).sort
end
}
}
A.reject!(&:empty?)
O = N-A.size
T,as = [0]*M,nil
as.each{|i| T[i] = 1-T[i] } if S[as[0]]!=T[as[0]] while as = A.shift
p(S==T ? 2.pow(O,998244353) : 0)
最終更新: 2021-06-24T16:08+0900
★２つだからってこういう素直なスクリプトを投げた。
N,P,Q,*A = $<.read.split.map(&:to_i)
p A.combination(5).count{|a5| Q == a5.inject{_1*_2%P} }
結果は TLE×21/AC×4。なんだよ全然ダメじゃんかよ。解説画像はこちら>https://github.com/E869120/kyopro_educational_90/blob/main/editorial/055.jpg。Ruby では解説が役に立たない。★６～７相当のより高速な解法があるというから、そちらを解説してもらわねば。
ABC192-F Potion (20210224p01) を思い出しながら悪あがきをした。
N,P,Q,*A = $<.read.split.map(&:to_i)
q = Hash.new 0
S = A.map{|a| q[a%P]+=1; q.dup }
(N-1).downto(N-4){|k|
S.pop # S.size==k
q = Hash.new 0
S.map!.with_index(N-k){|q0,i|
a = A[i]
q0.each{ q[_1*a%P]+=_2 }
next q.dup
}
}
p q[Q]
これで TLE×6/AC×19。0≤Q<P≤10^9 という制約がえぐすぎるんよな。大きすぎるし、素数じゃないし。いったいどういう手が打てるのか。
N が 100 以下というところで何かできないかと考えた。3..100 のある i より左から A×A のペアを作って記録し、また 1..98 のある i より右から A×A のペアを作って記録し、3..98 の 96 通りのある A_i に関して i の左右から条件を満たすペアを引っぱって来られないかと考えた。P で割った余りは 10^9 通りになりうるけど、A×A%P が取り得る値は 10000 通りより少ないから、左側のペア×A_i を総当たりしても高々 1000000 通りであり、これは許される。あとは右側のペアが定数時間で選べれば良い。ここでモジュラ逆数が使えるような、使いたいような気がするんだけど、法が素数でないから「a が m と互いに素でなければならず、さもなくば逆元 x は存在しない。」と Wikipedia に書かれていて困っている。A×A×A%P の値が決まっているとき、A×A%P の値が何であれば A×A×A×A×A%P==Q となるか。たぶん１つに定まらないのではないかと思う。ここで詰まった。
Ruby を使う良さってこういうところだよね。ぬるい解法が許されないところ(許されるとそれ以上考えないので)。「Ruby ならではのお楽しみポイント」「この前の日記(20200907p01)で散々 TLE に苦しめられた問題も、C++ なら変数 r を map に、変数 nmin を multiset にすることで、ある範囲のキーを二分探索で検索することも、小さい方からキーを取り出すことも、STL 任せで妥当な時間で行える。適当に速くて短い提出を選んだけどこんな感じ>「提出 #16578878」。トリックは必要ない。」 そこは問題の本質ではないからかかずらいたくないという考えもあるだろうけど、自分が一番楽しめるのはここ。
Ruby で 365 ms の解答が共有されているなあ。見たい、見たくない、見たくない。
典型 90-005 の解説から>「mod の値が 998244353 のような特殊な値ではないので一工夫必要ですが、それでもたとえば 3 種類くらいmod を用意して中国剰余定理で復元する方法などで上手くいきます」。中国剰余定理は Wikipedia やブログを読む機会が何度かあったけど、まだ早い、と理解をあきらめている状態。
最終更新: 2021-06-08T14:11+0900
競プロ典型 90 問の 043 - Maze Challenge with Lack of Sleep（★4）が普通に解けたので、Pond Skater (青diff1968)も解けるような気がした(既視感>20200826p01。根拠は必要ない)。
All AC になるまで死ぬほどバグらせた。これが時間内に解ける未来が見えない。訪問済みフラグが二値ではない。ループの継続条件とキューへの追加条件が同じではない。ループのあいだ無条件にキューに追加していると rand_20_01.txt と rand_20_03.txt の２つのケースでキューが複製要素で膨れ上がってしまう。それ以外のケースでは AC なのに。
無駄に難しくしてる？ そうであってほしい。
比較すると短いし速いし省メモリだと思う。テストケースハック(※テストケースは公開されている)らしき提出を除けば。
訪問済みフラグを水平方向と垂直方向に分けたのが間違いだったろうか。途中からフラグ(二値)ではなくなったし、紆余曲折を経て扱いが同列だし、単にコストとして再定義して書き直せるのでは？
Vh と Vv だったものを C に統合した。さらに短くさらに速くさらに省メモリになった。最初にコストでなく２つのフラグを使って書き始めたのが間違いの始まりだったのだなあ(Maze Challenge with Lack of Sleep（★4）の解き方がそうだったからなんだけど)。
