2021/08/28
柚木麻子のBUTTERを読了した。結構面白かったのだが、上手く感想が言語化できなかったので、雑に箇条書きで思ったことを綴ろうかと思う。
実在の結婚詐欺事件をモチーフにしたもの。記者である主人公里佳が容疑者のカジマナに取材のため接触するうち、その独特な価値観と語りに影響され、日常が変化していくというあらすじ
カジマナの価値観は、自らの欲望に忠実にありつつも、旧来の「女性らしさ」を良しとするもの。特にグルメに関して強いこだわりを持つが、料理サロンに通うまでは単に料理を男性を喜ばせる手段としか考えていなかった。男性に対する依存性が強いが、かつて自分が惹きつけてきた男性の中身のなさに辟易していたようだ。現代社会における女性の生きづらさ(スリムかつ綺麗であれという重圧が鬱陶しいというのは書かれていたが、他あったかな……？)を皮肉ったところがあり、そういう点に主人公は感銘を受けていたように思われる。その尖った価値観から一部の人間にカリスマ的影響を与えていたが、女性のコミュニティに馴染めなかったり、理想とする「男性との関係」を構築できなかったりで可哀そうといえば可哀そう。自らの醜い容姿のために尖った価値観(問題なのは男性への依存性か)を醸成し、結局幸せになれなかった。実は容姿が醜いと救いがないのでは？？？
そういえば容姿については、男性も同様の圧力は受けている。例えば垢ぬけない雰囲気の男性なんかは、いかにもな「オタク」だとか「理系大学生にいそう」とか馬鹿にされたりする。もちろん要求の重さや、容姿の重要性は異なるであろうが、見た目の努力については人類が抱えている悩みであるし、そういった悩みを無視するカジマナの生き方は、ある種心地よく理想的な生き方ではないだろうか
里佳が恋人の誠と別れるシーン。これは僕が男性だから思うのかもだけど、いや気に食わねーーーーーーーーーー。そうはならんやろ？？っていう。別れるまでの時系列をまとめると、里佳が太ったのを厭う発言を誠がする→里佳イラっとする→誠が推しのアイドルに対し、太ったからという理由で急に冷める→イラっとする→誠からの連絡をしばらく放置する→誠怒る。え、何？別れるの？→里佳: え、そんなこと考えてなかったけどそんな気になってきちゃった。私これからデスクになって批判とかされるかもよ→誠: じゃあそうならないよう努力しろよ→別れる って感じなんだけど、いやいやいや「そうならないよう努力しろよ」という流れは不自然では？ 作者が単に物語上二人を別れさせたくて、その決定打を作りました感が見える気がする。描写的に誠の方もあっさり別れたあたり、この女付き合う価値あるか？と思っていた可能性が高いが、世の中のカップルこういう感じで別れていくんだよな。すーーーーーぐ冷める。我々はあと何回別れるのを繰り返したら理想のパートナーと出会えるんですか？ 300年か？ いやわかるよ。わかるけど、世知辛くて悲しいね
物語中の事件の真相については明かされず。まあこれは実際の事件をモチーフにしたもので、その事件の真相は明らかになっていないためであろうか。変に真相書いちゃうと、木嶋佳苗事件の真相はこうだったのか？とか変に印象ついちゃうし、仕方ないところがあるのかもしれないが、個人的にはやはり不完全燃焼感
不満点ばっかり書いてしまったが、総評的に考えることの多い良い作品であったと思う。
Codeforces 73C: LionAge II
Difficulty: 1800
問題概要
英小文字で構成される長さNの文字列Sと整数kが与えられる．連続する2文字にはスコアが存在し，文字列のスコアは，隣接する2文字のスコアの合計である．Sをk文字まで好きな文字に置き換えることが許されるとき，取りうる最大のスコアは何点か？
N <= 100
k <= 100
解法
次のようなDPを考える．
DP[n][z][k] := n番目までを考えて，最後の文字がzで総置換回数がk回以下のもののうち，最大スコア
最後の文字ごとに状態を分けることがミソ．DP[n][z][k]は，
1) S[n] == zのとき，DP[n-1][*][k] のうち最大
2) S[n] != zのとき，DP[n-1][*][k-1]のうち最大
で求められる．
int euph[26][26] = {}; int dp[110][26][110] = {}; // dp[n][z][k] := n番目までを考えて，最後の文字がzで総置換回数がk回以下のもののうち，最大euph signed main(int argc, char const *argv[]) { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int len = S.length(); int K; cin >> K; int N; cin >> N; REP(i,N){ char a,b; cin >> a >> b; int c; cin >> c; euph[a-'a'][b-'a'] = c; } // 初期値セット REP(i,110) REP(j,26) REP(k,110) dp[i][j][k] = -INF; REP(i,26){ REP(j,110){ if(S[0]-'a' != i && j == 0){ continue; }else{ dp[0][i][j] = 0; } } } // 遷移 for(int i = 1; i < len; i++){ REP(j,26){ REP(k,110){ if(j == S[i]-'a'){ REP(l,26){ dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][k] + euph[l][j]); } }else{ if(k == 0) continue; REP(l,26){ dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][k-1] + euph[l][j]); } } } } } int ans = -INF; REP(i,26){ ans = max(ans,dp[len-1][i][K]); } cout << ans << endl; }
Codeforces 82D: Two out of Three
Difficulty: 2000
問題概要
待ち行列を考える．今N人の人が一列に並んでいて，レジにてサービスを受ける時間待ちをしている．ある人iがサービスを受け終わるのにかかる時間はAiである．このレジは先頭3人の内，2人選んで同時に捌くことができる．このときにかかる時間は，2人の人をそれぞれi，jとすると，max(Ai，Aj)である．全員がサービスを受け終わるのに，どのような捌き方をすればよいか
N < 1000
解法
重要な観察として，ある時点でまだサービスを受けていない人の集合は，番号が若い人iと，人j(>i)以降の人全員と表されることがわかる．ただし1人の場合は例外であるので，注意する．よって現在の列の状態は２つの数字iおよびjで一意に表すことができる．そこで，次のようなDPを考える．
dp[i][j] := 今列に残っているのが人iと，j(>i)以降の人全員であるとき，彼らを全員捌くために必要な最小のコスト
遷移は，
1) i番目とj番目の人を捌いてから残りはdp[j+1][j+2]
2) i番目とj+1番目の人を捌いてから残りはdp[j][j+2]
3) j+1番目とj+2番目の人を捌いてから残りはdp[i][j+2]
の3つである．
const int MAX_N = 1010; int dp[MAX_N][MAX_N] = {}; // i番目の人が残っていて，j(>i)からNまでの人が残っているときの最小コスト signed main(int argc, char const *argv[]) { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; VI A(N); REP(i,N) cin >> A[i]; if(N==1){ cout << A[0] << endl; cout << 1 << endl; return 0; } dp[N-1][N] = A[N-1]; dp[N-2][N-1] = max(A[N-2],A[N-1]); dp[N-2][N] = A[N-2]; for(int i = N-3; i >= 0; i--){ for(int j = N; j >= i+1; j--){ if(j == N) dp[i][j] = A[i]; else if(j == N-1) dp[i][j] = max(A[i],A[N-1]); else{ int t1 = max(A[i],A[j]) + dp[j+1][j+2]; int t2 = max(A[i],A[j+1]) + dp[j][j+2]; int t3 = max(A[j],A[j+1]) + dp[i][j+2]; dp[i][j] = min({t1,t2,t3}); } } } cout << dp[0][1] << endl; //復元パート int left = 0; int right = 1; REP(i,(N+1)/2){ if(right == N){ cout << left+1 << endl; return 0; } if(dp[left][right] - dp[right+1][right+2] == max(A[left],A[right])){ cout << left+1 << " " << right+1 << endl; left = right+1; right = right+2; }else if(dp[left][right] - dp[right][right+2] == max(A[left],A[right+1])){ cout << left+1 << " " << right+2 << endl; left = right; right = right+2; }else{ cout << right+1 << " " << right+2 << endl; right = right+2; } } }
Codeforces 5C: Longest Regular Bracket Sequence
Difficulty: 1900
問題概要
開きカッコと閉じカッコの２種類からなる文字列Sが与えられる．この文字列の部分文字列で，"対応が取れている"ものの中で最も長いものの文字列長と，その数を答えよ．
ただし，"対応が取れている"文字列とは，どの地点まででも閉じカッコの数が開きカッコの数より大きくならず，2種類の文字列の数が同じものである．
解法
DP的なイメージで解く．
まず，どのような部分文字列をとっても，ある閉じカッコに対応する開きカッコは不変であることがわかる． ある閉じカッコ(S[i])に対して，dおよびcを次のように定める．
d[i] := 対応する開きカッコの場所(存在しないなら-1)
c[i] := 閉じカッコS[i]で終わるような"対応が取れている"文字列のうち，最も長いものの始点
dはスタックを使えば容易にわかる．c[i]はd[i]であるか，それより左の可能性がある． 具体的には，c[d[i]-1]である．
後は文字列を前から順に見ていき，dおよびcを更新していけば良い．答えはcを見ることで得られる．
int d[1123456] = {}; int c[1123456] = {}; signed main(int argc, char const *argv[]) { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int len = S.length(); REP(i,1123456) c[i] = -1; stack<int> st; REP(i,len){ if(S[i] == '('){ st.push(i); }else{ if(st.empty()){ d[i] = -1; }else{ int x = st.top(); st.pop(); d[i] = x; c[i] = d[i]; if(c[x-1] != -1){ c[i] = min(c[x-1],d[i]); } } } } map<int,int> mp; int ans = -INF; REP(i,len){ if(S[i] == '(') continue; if(c[i] == -1) continue; if(ans < i-c[i]+1){ ans = i - c[i] + 1; mp[ans]++; }else if(ans == i -c[i]+1){ mp[ans]++; } } if(ans == -INF){ cout << "0 1" << endl; return 0; } cout << ans << " " << mp[ans] << endl; }
Codeforces 118D: Caesar's Legions
Difficulty: 1800
シンプルなDP．多分どうやっても解ける感じの問題だが，状態数が多いのでスマートに実装を行わないと沼にハマる．
問題概要
n1人の歩兵とn2人の騎兵を一列に並べる．歩兵はk1人を超えて連続してはならず，騎兵はk2人を超えて連続してはならない． 歩兵同士，騎兵同士の区別はできないとき，条件を満たす並べ方の場合の数を求めよ．
n1 = n2 = 100, k1 = k2 = 10
解法1
自分がやったやり方．実装が辛くてバグりまくったので，センスは良くない．
次のようなDPテーブルを考える．
dp[i][j][k][l] := i番目まで見て，騎兵(l=1)または歩兵(l=0)がj人連続しており，まだ並べていない歩兵がk人いるような，条件を満たす場合の数
配るDPを考え，次に歩兵を並べる遷移，騎兵を並べる遷移を考えれば良い．実装は以下の通り．
mint dp[210][210][110][2] = {}; int n1,n2,k1,k2; cin >>n1>>n2>>k1>>k2; dp[0][0][n1][0].x = 1; for(int i = 0; i < n1+n2; i++){ //配るDP for(int l = 0; l < 2; l++){ if(l == 0){ // 連続しているのが歩兵の場合 for(int j = 0; j < k1; j++){ for(int k = 1; k <= n1; k++){ dp[i+1][j+1][k-1][l] += dp[i][j][k][l]; //歩兵→歩兵 } } for(int j = 0; j <= k1; j++){ for(int k = 0; k <= n1; k++){ dp[i+1][1][k][1] += dp[i][j][k][l]; //歩兵→騎兵 } } }else{ // 連続しているのが騎兵の場合 for(int j = 0; j< k2; j++){ for(int k = 0; k <= n1; k++){ dp[i+1][j+1][k][l] += dp[i][j][k][l]; //騎兵→騎兵 } } for(int j = 0; j <= k2; j++){ for(int k = 1; k <= n1; k++){ dp[i+1][1][k-1][0] += dp[i][j][k][l]; //騎兵→歩兵 } } } } } mint ans = 0; REP(j,110){ REP(l,2){ ans += dp[n1+n2][j][0][l]; } } cout << ans.x << endl;
解法2
Codeforces 118 D: Caesar’s Legions – mplancer を参考にした．
DP[i][j][k][l] := 今歩兵がk人，または騎兵がl人連続しており，残り歩兵i人と騎兵j人を並べる並べ方で，条件を満たす場合の数
メモ化再帰でシンプルに書ける．美しい
mint dp[110][110][15][15] = {}; int k1,k2; mint solve(int n1, int n2, int x1, int x2){ if(n1 == 0 && n2 == 0) return 1; mint res = dp[n1][n2][x1][x2]; if(res.x != -1) return res; res = 0; if(n1 > 0 && x1 < k1){ res += solve(n1-1,n2,x1+1,0); } if(n2 > 0 && x2 < k2){ res += solve(n1,n2-1,0,x2+1); } dp[n1][n2][x1][x2] = res; return res; } signed main(int argc, char const *argv[]) { cin.tie(0); ios::sync_with_stdio(false); REP(i,110) REP(j,110) REP(k,15) REP(l,15){ dp[i][j][k][l] = -1; } int n1,n2; cin >> n1 >> n2 >> k1 >> k2; cout << solve(n1,n2,0,0).x << endl; }
AtCoder Beginner Contest 139 F: Engines 解説の解説
考察のはじめの一歩が難しかったので記録
全体の方針
エスパーをして，最終的に座標(x,y)にたどり着くのが最適であると知っていたとする． もちろんこのような点は複数ある場合もある．
では最適なゴール(x,y)に辿り着くためには，実際にどのようなベクトルの組み合わせをすれば良いかわかるだろうか？ ゴールまでのベクトルgをg=(x,y)とする．あるベクトルとgの内積が正であった場合そのベクトルを採用し，内積が負であった場合そのベクトルを採用しなければよい．
逆にそうしなければ，たどり着いたゴールが原点から最も離れた地点であるという仮定と矛盾する．
では次のような愚直な方針を考える．
愚直な解法
ある座標(a,b)が最適なゴールであったとする． このとき，上で述べたようにベクトルを選択する．・・・(1)
選択したベクトルの和が，(a,b)と一致しなかった場合，それは最適なゴールではない． 一致した場合，それは最適なゴールだったかもしれない．暫定解として記録しておく. ゴールとしてありえる座標を全探索し，最もスコアが高いものが最適解である．
当然のことながら，ゴールとしてありえる座標の候補は膨大なため，TLEする． しかし，よくよく考えてみると(1)で選択する組み合わせは相当限られてくる．具体的には，ある直線が存在して，その直線の右側区間(or 左側区間)に存在するものを選んだものである．
実装
与えられたベクトルを，偏角でソートしてやれば良い． 基本的に外積の正負によってベクトル間の順序を決める比較関数を用いてソートすればよいのだが， これだけだと一周回った付近が全順序集合を満たさないので，どの象限に属しているかの情報を用いる．
ここまで来たらあとはsnukeさんの放送を見ればよい(投げ)
