Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ABC135 反省会

AtCoderの初回でいきなりABC2完というのをやらかしてしまい、これはちゃんとAtCoder自体を勉強しないと強くなれないということがわかり、AtCoderの問題を解きまくり、ABC3完、ABC4完と毎回上げてきた。ここからは4完を安定させて、あわよくば5完出来るというレベルを目指していく。

参加したコンテストとか解法に感動した問題については記事にしていく方が長い目で見ると実力の伸びもよくなると思うので、そうすることにする。

AtCoder Beginner Contest 135 - AtCoder

B

これは見た瞬間に転倒数だと勘違いしてしまい、気づいた時にはパニックになっており、数列が連続してることを忘れていた。しかしNが超小さいので、愚直にやっても間に合うと思い、スワップしてソートされているかを全探索した。Rustだと3msで解けていた。

C

これは解法は思いつくけど、エディトリアルに書いてあるように、最大流に帰着すると証明出来るというのは全く気づかなかった。これがグラフに見えるようにならないといけない。

D

解法自体は難しくないと思ったが、実装で手間取った。

0から9に遷移させたいのに、0..9と書いていて、数が足りなくてサンプルが通らない自体に陥り、パニックになった。

Rustの0..9はexclusiveである。Rubyではこれはinclusiveで、exclusiveは0...9となっていて、言語の名前が似ていることもあり、混乱した。

しかし、現在AtCoderが使っているRust1.15では使用出来ないものの、最新のRustではこのような構文が利用出来る。この構文は競プロをする上では正確に書ける確率が上がると思うので、バージョンアップが待ち遠しい。あと他にも、dbg!マクロだとか、競プロが楽になる機能が追加されている。それになにより、おれのライブラリはBITが1.15でコンパイル出来ない。

fn main()
{
    for i in 0..=9 {
        println!("{}", i);
    }
}

E

マンハッタン距離と聞くと、軸ごとに分離か?と第一感思ったがそういうことでもなかったらしい。

エディトリアルには、こんなの思いつくかーいというミラクル解法が書かれているが、私は時間内に、例えばK=11である場合、2回の試行を(7,4),(-6,-5)のように1つずらして動くことによって(1,-1)のように長さ1を作り出すことが可能なことに気づいた。正負を逆にすれば4方向作れるはずである。このように、例を示せ系の問題では、単位になるものを作るというアイデアはたまに見ることがあるから、これが想定なのかと思った。あとは、(-1,-1)などでたどり着けるところにジャンプして、微調整して終わるのかなぁと思ったが、実装するまでの時間はなかった。

F

上位層はEよりFの方を先に解いていた。従って5完を狙うならこちらの方が解けるべき問題であるように思う。実際にこれは典型問題の範疇だと思った。

解法は、ローリングハッシュを使ってs内の各オフセットからtをマッチ出来るかを計算した上で、グラフ内の最長パス探索に帰着させるというものだが、これは配列をループではなく再帰関数で操作していけば実装出来る。こいつの最大値を調べるという感じ。

visited = [False] * LS
dp = [None] * LS
  
def dfs(i):
  if visited[i]:
    if dp[i] is None:
      return INF
    return dp[i]
  visited[i] = True
  if not match[i]:
    dp[i] = 0
    return 0
  x = dfs((i + LT) % LS) + 1
  dp[i] = x
  return x