あとこだ C問題

ご無沙汰してました。

色々やっているうちにC問題(E問題)がちょうど自分の実力にあっているとわかったのでこれを地道に解いていこうと思ってます。

参加記がいくつか溜まっているのでそれも書いていく所存

ARC055 C:ABCAC

題意:文字列が与えられる。これをABCACというブロックに解釈する場合の数を出力せよ

解き方:ABC|ACと分割することを考え分断するラインをまず固定し、AとCとして考えられるものを計算する(接頭辞の共通長を事前に計算)

事前計算O(|str|)、その後の分断ラインごとに考えるのでO(|str|)

反省:与えられた文字列 (=str)とstrのi文字めからのものの接頭辞の最大共通長をO(|str|)で列挙するアルゴリズムがなかなか書けなかった(知識？)

ARC056 C:部門分け(dp,bit,)

題意:N(<18)人の社員がおり、それぞれに信頼度が定まっている。m個のグループに分け、スコアをm*K-(異なる部門に属する人同士の信頼度の和)で定義　このスコアの最大値を求める

解き方:部分集合を走らせるdp dp[S]=max{dp[T]+K-sum}

計算すれば3^Nとわかるので間に合う

反省:まず集合のdpへの経験不足(bitで表示)部分集合を走るようにする実装のテク，i桁目が1かどうかの判定のテクなどなど 実装および発想共に学ぶことが多い問題

ARC058 C:和風いろはちゃん

題意:各項が1~10の長さN(<40)の数列と整数X,Y,Z(それぞれ≦5,≦7,≦5)がある。整数a,b,c,iであって，i項目からa個の和がX、続くb個の和がY、続くc個の和がZとなるようなものが存在する数列は全部で何通りあるか

解き方:a=b=c=1のみのときは後半三項だけ気をつけて条件を満たさないものをdpで計算すれば良い　そうでないときは「後半三項」をうまいこと言い換えるとよい X+Y+Z≦17なので二進表示するといい。(a個を10...0と言い換える)

反省:類似したdpの考えで良かったのに二段階目が思い浮かばなかった　比較的経験か？