AtCoderで通る(通った)嘘解法

 Twitterで, 「この問題難しいのになんでこんなdifficulty低いの…」「当時嘘が通ったかられふ……」というやり取りがそこそこ多い気がしたので思い出せるように. コンテスト後に話題になった記憶があるのが中心なのであまり昔のは無いれふ.

 ものによってはafter_contestという接頭辞のケースが追加されているため, 現在はACになりません.

 

 ABC117-D

 bitごとにXを0にした場合・1にした場合の寄与を求め, 上位の桁から寄与が大きくなる方を(K以下というのに矛盾しない範囲で)選んでいく嘘貪欲が通る.

実際には, N=3, K=4, A= \{ 4,0,0 \} で8と出力される(正しくは13).

ABC137-E

 1からNへの経路上に負の閉路があるかをベルマンフォードで検出しなければならないが, 誤った検出方法でも通る. 解説放送が詳しい.

ABC138-D

 辺がa \lt bであることを根拠に, 必ずaが親でbが子であると仮定したコードが通る. 実際には, N=3, (a_1,b_1) = (1,3), (a_2,b_2) = (2,3)のようなケースがある.

ABC139-E

 O(N^3)解法はTLEとなるが, そのようなケースが1つしか入っておらず, 答えが最大の \frac{N(N-1)}{2}となるものなので, TLEしそうな時にそれを出力するようにすれば通る.

ABC142-F

 答えが存在するとき, 空でない誘導部分グラフを出力しないとまずそうなのだが, K=0として出力してもACになる.

(コンテスト中にこれで通した人はいなさそう)

ABC143-E

 ワーシャルフロイド法を使うとO(N^3)だが, 全部の始点からダイクストラをするとO(N^3 logN)となる. するとTLEで落ちかねないのだが, コンテスト中は余裕で通った.

ABC169-C

 丸め誤差で切り捨ての結果がおかしくなって落ちるケースが無かった. doubleを使うと精度不足で元々落ちたが, long doubleやbを100倍したのみで, 小数部が0.99999...になってしまうようなケースへの対処をしていないようなものが通っていた.

ABC173-E

 最大化を目指す上で貪欲をすることになるが, 負の数は2個セットで選ぶことになる. しかし, 正の数も2個ずつ選んでしまうような嘘が通った.  N=5, K=3, A= \{ -5,-1,1,2,3 \} のようなケースで落ちる.

ABC184-C

(r_1,c_1,r_2,c_2) = (1,1,1,6)で3と出力するコードが通る.

ARC104-C

 N=2, (A_1,B_1) = (2,3), (A_2,B_2) = (-1,-1)でYesと返すコードが通る.

ARC105-B

setを使ってシミュレーションをしてもTLEにならず, 通る. N=2, A= \{ 1,10^9 \} みたいなケースで落ちる.

AGC033-B

 高橋君が右に落とそうとし, 青木君がそれを阻止しようとする. そのために高橋君は'R'を極力採用し, 青木君は'L'を極力採用する. その結果落ちたか否か調べる. これを上下左右すべてで調べると通る. この解法は, H=10, W=2, N=3, s_r=5, s_c=1, S="URL", T="RUU"で"YES"と出力されてしまう.

AGC035-A

 すべてのXORが0なら"Yes", そうでなければ"No"と出力することで通る. N=4, A= \{ 1,1,1,1 \} で落ちる.