AtCoder Beginner Contest ABC406 解法メモ
文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです
ABC406
ABC406A - Not Acceptable
解法
(A,B)>(C,D)かどうかみればよい
ACコード
メモ
A>C or (A==C and B>D)かどうかみてもよい
ABC406B - Product Calculator
解法
初期値
再び
ただし、制約が大きいため、そのままではオーバーフローするので、移項して
a<=(10^K-1) div A[i]
かどうか判定すればよい
ACコード
メモ
オーバーフローの確認をしなかった
ABC406C - ~
解法
条件を検討するには、
その配列
(1..<N).toSeq.mapIt(P[it]-P[it-1]>0)
を用意すると、
条件を満たすのは、この配列の中の
trueで始まり（条件2）、
途中でfalseになり（条件3）、
またtrueに戻る（条件4）塊のことである
ひとつの塊に対して、
初めのtrueと、終わりのtrueの個数の取り方分だけ別種が作れるので、
種類数は、両trueの個数の積となる
これは、ランレングス圧縮をすれば簡単で、
圧縮後の配列を先頭から一つずつずらしながら、
両trueの個数の積を足し合わせていけばよい
ACコード
メモ
前項との差をとった数列を作ってしまい、
条件を満たすか判定するステップフラグを用いて実装しようとして手間取った
ABC406D - Garbage Removal
解法
各行、列毎にゴミの位置を保存する配列と、
あわせて行、列毎の個数の合計値を記録する配列を用意しておく
クエリ毎に、まず指定行、列の合計値を答え、
その行、列のゴミの位置で交差する
列、行の合計値を
指定行、列の合計値を
ACコード
メモ
各行、列のゴミをHashSetで持って忠実に管理してもよいが、ゴミを捨てるときにclearを使うとTLEとなるため、initHashSet[int]()に置きなおすとよい（ACコード）
Nimで各行、列のゴミをnewSeq[HashSet[int]](n)で持つとMLEとなるため、Table[int,seq[int]]としておく必要がある
Discussion