👌

AtCoder ABC369 Cを自力で解く!!!

2024/09/01に公開

AtCoder

idea

AtCoderに挑戦してみた。 ABC 369

Cの問題を自力で解く

結論から言うと、Cの問題すらコンテストに解けなかった。悔しかったのである程度試行錯誤を繰り返して解答に辿り着いたのでそのプロセスを書く。

きっかけ

今回が競プロ初参加。
元々プログラムを書くのは好きで、競プロの記事なんかも見て、過去問を軽く解いたこともあり少なからず興味があった。
また、業務でのちょっとしたスクリプトだったり、趣味でコードを書いたりするときにPythonを使用しており、自分がどれだけやれるのかなというのを知りたかった。

結果と感想

A, B完答、Cでタイムアップ。
正直、過去問をやってみたときにDくらいの問題が自分の壁なのかなと思っており、最初の10分でABCまで解いて残りを30分ずつかけて攻略できればと楽観的に考えていた。
蓋を開けてみればAの問題から少々考えさせられる問題で、そこから焦りが出始めC問でなかなか答えが合わなくて非常に焦ってしまった。
途中から完全に思考が回らなくなり、上のような結果だった。
Dくらいまでは解けるかなと思っていたこともあり、かなりショックでした。競プロの解説記事なんかを書かれている方々は相当なトレーニングをされているのだな感じた。
Cの問題が解けなかったのが悔しいので、そちらについて書く。

ABC 369 C コンテスト中に書いたコード

問題文についてはこちら

問題文を見たときに(l, r)の組み合わせの全探索で解こうとコードを書き始め、以下のようなコードを書いた。

N = int(input())
A = list(map(int, input().split()))

count = 0
for l in range(N):
  for r in range(l, N):
    if l == r or r - l == 1:
      count += 1
      continue
    d = A[l+1] - A[l]
    flg = True
    for k in range(l, r-l):
      d_ = A[k+1] - A[k]
      if d_ != d:
        flg = False
        break
    if flg:
      count += 1
print(count)

rの範囲をl≦rで探索しているので、少しは工夫出来たかとなんて思っていた。
例にある3つ目のテストケースを実行すると25となり、あれ、どこか間違えてるなとなった。
結論から言うとkの動く範囲が緩く、range(r)と書くべきだった。
焦りが募りすぎて、そんな簡単なミスに気付くまでに時間がかかってようやくそれに気づいて修正できたのがコンテスト終了10分前くらいだった。
いざ、直して実行してみるも今度はTLE、時間オーバーのコードという具合だった。
言われてみればNが非常に大きく、lが小さい、rが大きいという条件ではN^3(なおかつNがでかい)のループになっていて、確かに遅い。
途中答えが合わないと奮闘しているときに、Aの差分を取ったlistを用意してそこから数えらえるという考えにも至ったが、パニックになりすぎて方針を変えられなかった。
ひとまず最初の方針でコードを書ききったので、後から浮かんだ案で実装しようと思ったところで時間切れ。
テスト後はBまでしか解けなかったことがショックで、復習もせず終わった。

コンテスト後の実装

Aの差分を取ったlistを用意し、前から順に読んで、同じ値がいくつ連続しているかで組み合わせの数を数えれば答えにいきつくいうのを実装した。

具体的での計算を以下に示す。

A = [87, 42, 64, 86, 72, 58, 44, 30]

に対して

D = [-45, 22, 22, -14, -14, -14, -14]

とすれば、22が連続する箇所では2通り、-14が4連続で並ぶ箇所では10通り。
長さが1の部分列も必ず等差数列とカウントするので(r, r)のような組も条件を満たす組になるので以下のように実装した。

N = int(input())
A = list(map(int, input().split()))

D = []
for i in range(N-1):
  D.append(A[i+1] - A[i])

def sub(n):
  return int(1/2 * n *(n+1))

count = N

i = 0
sub_count = 1

while i < (len(D) - 1):
  if D[i] == D[i+1]:
    sub_count += 1
  else:
    count += sub(sub_count)
    sub_count = 1
  i += 1

# 最後の分
count += sub(sub_count)

print(count)

countの初期値をNにしているのは(r, r)の組を最初に数えたいから。
whileを抜けたとき最後の部分列の分が足されないので忘れずに足しておく。
さて、最もらしい解答が作成できたし、問題の例にある3つもテストしてうまくいったのでAtCoderに再度、採点をかける。
ところが、ここではWAで1ケースだけ間違ているという判定だった。

通らなかったテストケースの思案

なんとか自分で正解に辿り着きたいのでテストケースがわかればと思って検索したが、見つからず。
そこで考えたのが、テストケースをたくさん作成し、自分のコードの実行結果と、解答の実行結果を見比べてそれらが異なるテストケースを探し出せばという考えにいたった。

数列のそれぞれの成分が10^9通りあるので、それらをすべてテストするのは不可能。落ちているテストは1ケースなのでなにか特殊な条件下か境界条件あたりかと推察していたので次のようなテストケースを作成するコードを書いた。

N = 8
A = [random.randint(0, 2) for _ in range(N)]
print(N)
for a in A:
  print(a, end=' ')
print('')

python generate_test_case.py > test1.txt
python generate_test_case.py > test2.txt
･･･
と100個ほどテストケースを作りたいので、今度はChatGPTの力を借りてシェルスクリプトを作成。

#!/bin/bash

NUM_TESTS=100
PYTHON_SCRIPT="test_c.py"
OUTPUT_PREFIX="./test_c/test"

for ((i=1; i<=NUM_TESTS; i++)); do
    OUTPUT_FILE="${OUTPUT_PREFIX}${i}.txt"
    python "$PYTHON_SCRIPT" > "$OUTPUT_FILE"
done

このスクリプトを実行し、テストケースを100個生成した。今度は実際に自分のコードと解答のコードを実行していきたいので、シェルスクリプトの第二弾を作成。

#!/bin/bash

NUM_TESTS=100
PYTHON_SCRIPT="c_improved.py"

for ((i=1; i<=NUM_TESTS; i++)); do
    INPUT_FILE="./test_c/test${i}.txt"
    echo "----test${i}"
    ./cpp/a < "$INPUT_FILE"
    python "$PYTHON_SCRIPT" < "$INPUT_FILE"
done

ここまでくれば、落ちたテストがどんな内容だったかわかるだろうとシェルスクリプトの結果に目を凝らすが、どうにもすべて結果が一致していまい、再度テスト生成→テスト実行としたが、それでも見つからず。
冷静に考えてみると、境界条件でもあるN=1が怪しいのではと思い、次のようなテストケースで実行してみた。

1
1

そうすると、自分のコードでは出力が2, 正解のコードでは出力が1とついにうまくいかないテストケースが判明。
差分を取る段階で、N=1だったらというのをもう少し考慮しておけばハマらなかったかもしれない。
結果的には差分列Dを計算する処理の前に、次のコードを入れることでようやくAtCoder上で正解に。

if N == 1:
  print(1)
  exit()

終わりに

シェルスクリプトまで書いて意地でも解いてやろうとしたが、その部分は結果的には不要だった。どうしても落ちているテストケースがわからない場合は上のようなプロセスでテストケースを探し当てられるかもしれない。
今回の結果については非常に悔しいと思っているので、リベンジしたい。