AtCoder Text(cat) 傾向と対策
これは IQ1 Advent Calendar 2019 の 2 日目の記事です
adventar.org
これは 2019/12/02 当時の情報で、ここから更新する気はあまりないです。
ここには 103 問存在していると思います
AC 時の得点が一意である問題
答えが一意である問題
- 当然ギャグが多い
- https://atcoder.jp/contests/tenka1-2013-quala/tasks/tenka1_2013_qualA_a
- https://atcoder.jp/contests/tenka1-2013-qualb/tasks/tenka1_2013_qualB_a
- https://atcoder.jp/contests/tenka1-2014-quala/tasks/tenka1_2014_qualA_a
- https://atcoder.jp/contests/gwcontest2015/tasks/gw2015_a
- https://atcoder.jp/contests/tenka1-2015-quala/tasks/tenka1_2015_qualA_a
- https://atcoder.jp/contests/yuha-c88/tasks/yuha_c88_f
- https://atcoder.jp/contests/yuha-c88/tasks/yuha_c88_j
- https://atcoder.jp/contests/tenka1-2015-qualb/tasks/tenka1_2015_qualB_a
- https://atcoder.jp/contests/code-festival-2015-relay/tasks/cf_2015_relay_a
- https://atcoder.jp/contests/code-festival-2015-relay/tasks/cf_2015_relay_f
- https://atcoder.jp/contests/tenka1-2016-quala/tasks/tenka1_2016_qualA_a
- https://atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_a
- https://atcoder.jp/contests/jag2017summer-day1/tasks/jag2017summer_day1_j
- https://atcoder.jp/contests/xmascon17/tasks/xmascon17_a
- https://atcoder.jp/contests/xmascon17/tasks/xmascon17_g
- https://atcoder.jp/contests/xmascon18/tasks/xmascon18_a
- https://atcoder.jp/contests/xmascon18/tasks/xmascon18_b
- https://atcoder.jp/contests/iroha2019-day3/tasks/iroha2019_day3_j
答えが一意でない問題
- これはけっこう雑に置いてもなんとかなる
- これはまた特殊
- a-z を 2 回ずつ繰り返せば任意の入力に対して対応できる
- 唯一の rated 問題
- まぁつらい
- めっちゃつらい
AC 時の得点が一意でない問題
答えが一意である問題
- そんなものはない
答えが一意でない問題
- いわゆるマラソン問題。マラソンっぽくない問題も多い。入力が固定長もしくは存在しないで出力が定数行、もしくは自由な行数出力できる場合に Text(cat) で AC できることが多い
- なお、多くの場合点数は 0 点になるが、verdict が AC ならば何も問題がない
- https://atcoder.jp/contests/utpc2012/tasks/utpc2012_06
- https://atcoder.jp/contests/geocon2013/tasks/geocon2013_a
- https://atcoder.jp/contests/kupc2013/tasks/kupc2013_g
- https://atcoder.jp/contests/tenka1-2013-qualb/tasks/tenka1_2013_qualB_e
- https://atcoder.jp/contests/birthday0410/tasks/birthday0410_a
- https://atcoder.jp/contests/birthday0410/tasks/birthday0410_f
- https://atcoder.jp/contests/arc019/tasks/arc019_4
- https://atcoder.jp/contests/kupc2015/tasks/kupc2015_b
- https://atcoder.jp/contests/chokudai002/tasks/chokudai002_a
- https://atcoder.jp/contests/xmascon16/tasks/xmascon16_b
- https://atcoder.jp/contests/rco-contest-2017-qual/tasks/rco_contest_2017_qual_a
- https://atcoder.jp/contests/rco-contest-2017-qual/tasks/rco_contest_2017_qual_b
- https://atcoder.jp/contests/rco-contest-2017-final-open/tasks/rco_contest_2017_final_a
- https://atcoder.jp/contests/rco-contest-2017-final-open/tasks/rco_contest_2017_final_b
- https://atcoder.jp/contests/xmascon17/tasks/xmascon17_b
- https://atcoder.jp/contests/xmascon17/tasks/xmascon17_c
- https://atcoder.jp/contests/rco-contest-2018-qual/tasks/rco_contest_2018_qual_a
- https://atcoder.jp/contests/rco-contest-2018-qual/tasks/rco_contest_2018_qual_b
- https://atcoder.jp/contests/future-contest-2018-qual/tasks/future_contest_2018_qual_a
- https://atcoder.jp/contests/future-contest-2018-final-open/tasks/future_contest_2018_final_a
- https://atcoder.jp/contests/rco-contest-2018-final-open/tasks/rco_contest_2018_final_a
- https://atcoder.jp/contests/rco-contest-2018-final-open/tasks/rco_contest_2018_final_b
- https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_i
- https://atcoder.jp/contests/kupc2018/tasks/kupc2018_c
- https://atcoder.jp/contests/future-contest-2019-qual/tasks/future_contest_2019_qual_a
- https://atcoder.jp/contests/future-contest-2019-final-open/tasks/future_contest_2019_final_a
- https://atcoder.jp/contests/pakencamp-2018-day2/tasks/pakencamp_2018_day2_h
- https://atcoder.jp/contests/ddcc2019-machine/tasks/ddcc2019_machine_a
- https://atcoder.jp/contests/rco-contest-2019-qual/tasks/rco_contest_2019_qual_a
- https://atcoder.jp/contests/rco-contest-2019-qual/tasks/rco_contest_2019_qual_b
- https://atcoder.jp/contests/hokudai-hitachi2018/tasks/hokudai_hitachi2018_a
- https://atcoder.jp/contests/hokudai-hitachi2018/tasks/hokudai_hitachi2018_b
- https://atcoder.jp/contests/hokudai-hitachi2018/tasks/hokudai_hitachi2018_c
- https://atcoder.jp/contests/rco-contest-2019-final-open/tasks/rco_contest_2019_final_a
- https://atcoder.jp/contests/rco-contest-2019-final-open/tasks/rco_contest_2019_final_b
- https://atcoder.jp/contests/caddi2019/tasks/caddi2019_a
- https://atcoder.jp/contests/iroha2019-day3/tasks/iroha2019_day3_i
- https://atcoder.jp/contests/iroha2019-day3/tasks/iroha2019_day3_l
- https://atcoder.jp/contests/future-contest-2020-qual/tasks/future_contest_2020_qual_a
- https://atcoder.jp/contests/hokudai-hitachi2019-1/tasks/hokudai_hitachi2019_1_a
- https://atcoder.jp/contests/hokudai-hitachi2019-1/tasks/hokudai_hitachi2019_1_b
- output_checker がゆるいのか、空文字列をジャッジしてくれる
- AC を取るまでも普通に難しい問題もたまにある
- JOISC のマラソン問題のジャッジは入力が1ケースしかなくかつ与えられているので、Text(cat) で問題なく AC できる。
- https://atcoder.jp/contests/joisc2007/tasks/joisc2007_packin
- https://atcoder.jp/contests/joisc2007/tasks/joisc2007_packing2
- https://atcoder.jp/contests/joisc2007/tasks/joisc2007_packing3
- https://atcoder.jp/contests/joisc2007/tasks/joisc2007_packing4
- https://atcoder.jp/contests/joisc2007/tasks/joisc2007_packing5
- https://atcoder.jp/contests/joisc2008/tasks/joisc2008_election1
- https://atcoder.jp/contests/joisc2008/tasks/joisc2008_election2
- https://atcoder.jp/contests/joisc2008/tasks/joisc2008_election3
- https://atcoder.jp/contests/joisc2008/tasks/joisc2008_election4
- https://atcoder.jp/contests/joisc2008/tasks/joisc2008_election5
- https://atcoder.jp/contests/joisc2010/tasks/joisc2010_simroad1
- https://atcoder.jp/contests/joisc2010/tasks/joisc2010_simroad2
- https://atcoder.jp/contests/joisc2010/tasks/joisc2010_simroad3
- https://atcoder.jp/contests/joisc2010/tasks/joisc2010_simroad4
- https://atcoder.jp/contests/joisc2010/tasks/joisc2010_simroad5
- https://atcoder.jp/contests/joisc2011/tasks/joisc2011_ufo1
- https://atcoder.jp/contests/joisc2011/tasks/joisc2011_ufo2
- https://atcoder.jp/contests/joisc2011/tasks/joisc2011_ufo3
- https://atcoder.jp/contests/joisc2011/tasks/joisc2011_ufo4
- https://atcoder.jp/contests/joisc2011/tasks/joisc2011_ufo5
- https://atcoder.jp/contests/joisc2012/tasks/joisc2012_broadcasting1
- https://atcoder.jp/contests/joisc2012/tasks/joisc2012_broadcasting2
- https://atcoder.jp/contests/joisc2012/tasks/joisc2012_broadcasting3
- https://atcoder.jp/contests/joisc2012/tasks/joisc2012_broadcasting4
- https://atcoder.jp/contests/joisc2012/tasks/joisc2012_broadcasting5
- これは複数ケースに対して別々の答えを返すべき問題だが、output_checker がゆるく余分な出力があっても無視してくれるので AC できる
ジャッジが正常でない問題
ジャッジが壊れている問題
- テストケースが登録されておらず、CE にさえならなければ AC になる
- ジャッジの浮動小数点数に対するエラー処理が甘く 'nan' と出力すると AC になる
- なぜか '1' と出力すると AC になる(なぜ?)
ジャッジが用意されていない問題
- ジャッジが準備中な問題もたまにあり、CE にさえならなければ AC になる
- ソースコードを運営と共有するために使われたらしい
その他
マラソンならば Text(cat) で AC できる?
- No
- 例えばこういうのは入力で与えられた条件を満たす必要があるため無理
- これは一見できそうに見えるが、output_checker が出力を読んだあと空かどうかを判定しており、とりあえず 3000 行出力する、という提出が WA となる
- これも入力サイズが不定な上満たさなければならない制約が存在し無理そうに見えるが、実は Text(cat) で AC できる
その他
- 一部の問題はジャッジが壊れて WA や IE しか出ない状態になっていたりしており(おそらく言語アップデートの影響?)、本来 Text(cat) で AC できるのにできないようになっている問題が存在する
- Text(cat) の言語 ID は 2 種類存在する
- 言語アップデート時に振り直されており、アップデート前は 17、アップデート後は 3027
- Text(cat) で AC 可能な問題を探すため、全問題に対し Text(cat) の AC 提出があるかクローリングするプログラムを書いた
- AtCoder への負荷を減らすため最低限 O(問題数) くらいの fetch しかしないようにはしているが、それでも問題数が多いのでどうしようかなとなっています