イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

129. AtCoder参加記録（AtCoder Beginner Contest 264）

プログラミング AtCoder

33回参加でレート 1375 です。

 

 

今回はパフォーマンス 1668 です。

ABCDEを通して、GExは未解答です。Fは通せず。

 

各問題の思考過程など。

A

問題

1分18秒。

C# だと S.Skip(L - 1).Take(R - L + 1) でいいです。

ACコード

 

B

問題

4分41秒。

問題を開いた瞬間に目がやられました。いまいちどう表現して良いのか分からない盤面だったので、とりあえず思いついた書き方で構築しました。

 

真ん中からのチェビシェフ距離だったらしい。なるほど…。

ACコード

 

C

問題

8分6秒。

ちょっと考えて「うーん、全探索しか無さそう」となり、制約を見て「bit全探索か」となりました。微妙に間に合うのか心配でしたが、これ以外思いつかなかったので細かい実装方針を詰めてから書きました。PopCount初めて使ったかも。

ACコード

 

D

問題

4分15秒。

バブルソートするだけでは…となり、そのとおりに書きました。

ACコード

 

E

問題 

初回提出19分19秒、そこからACまで3分43秒。

  1. こういう系は逆から考えるのが定石。逆からなら Union-Find やるだけで良いな、と方針を決定
  2. あとは丁寧に実装する

何故か2WA出て頭を抱えましたが、同一グループに属しているかの判定が一箇所抜けていました。これだけで70近くパフォを落としているので、だいぶ勿体なかったです。

ACコード

 

F

問題

初回提出48分58秒。解けず。

  1. 必ず H + W - 2 手で終わる、右か下かを選択して進めるということでDPっぽい。
  2. 何が状態になるのか考えると、以下の5要素で良さそう？
    1. どの行にいるのか
    2. どの列にいるのか
    3. 0 と 1 どちらのマスを通っているのか
    4. 現在いる行が反転されているか
    5. 現在いる列が反転されているか
  3. 状態数は 2^3HW なのでとりあえず間に合いそう。後は遷移を丁寧に考えれば良いかな…とそれっぽいものを書き、とりあえずサンプルは合うようになった。投げてみると半分以上 WA。
  4. 入力例 1 のDPテーブルを見ながらデバッグ・修正したが、結局 WA の数は変わらず。

（以下、Upsolve）

冷静に考えると、遷移が一部間違っていることを理解した…。どういう状態を持っているのかちゃんと認識できておらず、混乱したコードを書いていたのが敗因。

これは通せた問題だったので勿体なかったです。

Upsolveコード

 

G

Fの遷移を考えていてよく分からなくなったので、こちらも見ました。全然解けそうになかったので5分くらいで見るのをやめました。

 

Ex

見てないです。

 

 

Eのペナがとても勿体なかったですが、とりあえず久々の青パフォで嬉しかったです。F解きたかったなぁ。