ARC081 E: Don't Be a Subsequence

E - Don't Be a Subsequence

解き方

• 部分列でない最小の文字列の、先頭の文字を決める→2文字目以降の文字列について考える、を繰り返すDP
  • DPする時には、後ろから決めていかないといけない
  • どの文字を先頭にするか決めるために、どの文字がどこに現れるかについて前計算が必要

ハマったところ

• 単純にこのDPが思いつかなかった
  • 辞書順最小に対しては、後ろからDPして、最後に経路復元するのが一つのテンプレートらしい。

github.com

ARC081 D: Coloring Dominos

D - Coloring Dominoes

解き方

• 左から順々に見ていく。直前のタイルの貼り方と、次のタイルの貼り方は2*2の4パターンなので、それぞれ場合分けしながら計算する

ハマったところ

• 上下に見ようとしたり、DFSしようとしたり、迷走していた
  • 高さ2と小さいのだから、高さ方向を固定する方が良いということに気づくべきだった。

github.com

ARC081 C: Make a Rectangle

C - Make a Rectangle

解き方

• 2個以上存在する数字を大きい方から2つ選んで長方形を作る

ハマったところ

• 正方形のケース（同じ数字が2回登場する）を忘れていた

github.com

活動記録(2017/8/14-2017/8/20)

競技プログラミング

ARC081

結果: 446th, 1449 -> 1470 (perf 1614)

Cの凡ミスと、Dで無意味に時間を書けたのはもったいなかったなぁ。E、Fは手が出る感じなかったし、今の自分の実力はこんなものなのだろう。

AOJ0121, AOJ0525

蟻本の練習問題

paiza

暇だったので始めた。 とりあえずSランクにしたあと、適当な気分で解いたら色々やらかして平均点が100でなくなってしまった。

その他

• EC2インスタンスを利用したジョブスケジューラを実装したい
• 9月の旅行先を決めた

AOJ0525: おせんべい

おせんべい | Aizu Online Judge

蟻本初級の練習問題にあったので解いた。

解き方

• どの行をひっくり返すかは、全部で2^R通りなので、これについてはすべて試すことができる。
• ひっくり返す行を決めて、ひっくり返した後は、各列で裏と表のうち、多い方の数の和が、最大値となる
• ひっくり返す行の場合それぞれについて、上記のように最大値を求めて、それらすべての最大値の答え

github.com

AOJ0121: 7パズル

7 パズル | Aizu Online Judge

蟻本初級の練習問題にあったので解いた。

解き方

• 終了時点（綺麗に整列した状態）から幅優先探索を行い、各状態から終了状態までの最小回数を求める
  • 状態の個数はたかだか8!個程度なので、この前計算は十分間に合う
• 各クエリについて、上記で求めた最小回数を表示

ハマったところ

• 状態遷移をミス（右上←→左下の移動を禁止できていなかった）
• 開始状態から幅優先探索しようとして、TLEを繰り返した

github.com

ABC070 D: Transit Tree Path

D - Transit Tree Path

解き方

• aからKへの距離とKからbへの距離の和を出力する
• Kから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。

ハマったところ

• 0-indexと1-index混ぜてた
  • 読み込み時に変えておくべきという話はありそう
• 最初全頂点から全頂点を求めようとして、O(n^2)になって困ってた。

github.com