ABC 080 D-Recording
D - Recording
真っ先にいもす法（今日知りましたが）を適用したくなりますが, そのまま適用してしまうとチャンネルそのままで録画するときの最適解を出せないです. そこで, まずチャンネルごとにいもす法を適用して, 連続で録画できる番組, それぞれのチャンネルでつなげておいて, あとでマージすることを考えます. 同じチャンネルで同時に２つの番組を放送することはないので, 連続している区間をなめらかにつなげます. (具体的に言うと, いもす法で2となってしまう部分を1に直す).
それぞれのチャンネルでこれを行った後, すべての時刻において各チャンネルが録画中かどうかを調べ, 最大値を更新すればよいです. また, S-0.5秒を表現するために配列を倍にしてインデックス1つごとに0.5秒間隔にしました.
ABC093 D-Worst Case
D - Worst Case
A*Bより小さな積となる二組の整数のマッチングを最大化する問題です. ただしA,Bを用いてはいけません.
A,Bを用いないことや重複を考えず, まず貪欲にマッチングを作ることを考えます. A*Bが十分大きいとして, ２項(C,D)(C<=Dとしておきます)において例えばC = 1のとき, Dの値としては1,2,3...A*B-1などが考えられます. 貪欲にマッチングを作りたいので, あとで使えないような整数を使う出来る限り厳しい条件をとり, A*B-1をとります. 同様にして C= 2 のときは, (A*B)/2 (小数点切り捨て)を取りたいです. しかし, A*Bより小さいもののマッチングを探しているのに, A*Bが2の倍数のとき2*(A*B/2)はA*Bと等しくなってしまいます. できる限り厳しい条件を取りたいので, A*Bが2で割り切れるときは(A*B/2) - 1を採用することにします.
同じようにしてC = n を考えると,
D = (A*B)/n (A*B % n != 0)
D = (A*B)/n -1 (otherwise)
という式ができます.
C <= Dとなる組を全部列挙して, 対称性からその個数を二倍すれば, だいたい答えに近い値になります.
Cは1から単調に増加し, Dは単調に減少していくため, C <= Dが満たされている境界のCを求めると, C <= Dとなる組を求めたことになります. ループを回していくと, おそらくO(N^(1/2))かかりTLEとなりますが, 単調性から, 二分探索を用いることができ, O(log max(a,b)) で計算できます.
上で作成した組で, (C,C)となる組やA,Bを用いているものを除くことができれば正答が得られます.
(C,C)となるような組の検出は, 返ってってきた境界のCに対してペアをもう一度計算することで確かめられます. 単調性から, C = Dが成り立つのは境界部分でしかありえないからです.
A,Bを用いているものの数は, Cの単調性からC >= AまたはC >= Bであることを確認すればよいです. 多分必ずどちらかは成り立つので, 1は減らすことに鳴ると思います. Dの方では, 実はBにならないようにマッチングをとりなおすことができるので考えなくてもよいです.
ABC 104 反省
A問題
A - Rated for Me
条件分岐をします.
提出
Submission #2950380 - AtCoder Beginner Contest 104
B問題
B - AcCepted
素直に条件を満たしているかどうか確認します. こういうのをやるときはboolを返す関数をつくると実装が楽なんだなあと解説生放送を見ながら思いました.
提出
Submission #2951814 - AtCoder Beginner Contest 104
C問題
C - All Green
問題をしばらく見つめて貪欲解が全く思い浮かばず, どん詰りの状態でしたがDの制約がとても小さいことから部分集合全列挙を思いつきました. コンプリートする問題の組み合わせを全部調べて解く問題の最小値を更新すればよく,コンプリートする問題がきまっていれば, コンプリートしていない問題の中から貪欲に点数の高いものをとっていけばいいことがわかります. この貪欲にとるとき, コンプリートしてはいけないことに注意が必要です. なにもコンプリートしないことも全列挙のうちに入っているので, あまり深く考える必要はありません.
提出
Submission #2955944 - AtCoder Beginner Contest 104
D問題
D - We Love ABC
コンテスト中いろいろ考えていたものの解けず, 解説を見ても???状態. DPは難しいですね....
こちらのけんちょんさんのブログを見てコードをまね, DPの気持ちを推量.
ABC 104 D - We Love ABC (400 点) - けんちょんの競プロ精進記録
自分の解釈で説明すると, dpの状態は4つあります. また, ?マークが出て文字列が3倍に増えることを分裂を呼称することにします.
dp[i+1][0]･･･Sのi文字目までで分裂した文字列の個数
dp[i+1][1]･･･Sとその分裂のi文字目までで出現するAの数
dp[i+1][2]･･･Sとその分裂のi文字目までで出現するABの数(A,Bは連続する必要がなく, この順番に並んでいればよい.)
dp[i+1][3]･･･Sとその分裂のi文字目までで出現するABCの数(A,B,Cは連続する必要がなく, この順番に並んでいればよい. )
初期値: dp[0][0] = 1 (初期は分裂しておらず１つの文字列)
遷移を考えると,
1.セットアップ(前状態からの繰越)
s[i] == '?'のとき
{dp[i+1][0] = 3*dp[i][0] (文字列の数が3倍になります.)
dp[i+1][1] = dp[i][1]*3
dp[i+1][2] = dp[i][2]*3
dp[i+1][3] = dp[i][2]*3
今まで見てきたA,AB,ABCについて, 文字列の数が3倍となったため, これらすべての量も3倍になります.
}
s[i] != '?'のとき
dp[i+1][0] = dp[i][0] (文字列は分裂しないので文字列の数はそのままです)
2.遷移
s[i] == 'A' のとき
dp[i+1][1] += dp[i][0] (分裂した文字列の数だけAが出現するので, すべて足す.)
s[i] == 'B'のとき
dp[i+1][2] += dp[i][1] (今までに登場したすべてのAに対してこのBを対応させることができます)
s[i] == 'C'のとき
dp[i+1][3] += dp[i][2] (今までに登場したすべてのABにこのCを対応させることができます. )
s[i] == '?'のとき
dp[i+1][1] += dp[i][0]
dp[i+1][2] += dp[i][1]
dp[i+1][3] += dp[i][2]
?はAにもBにもCにもなりうるため, すべての遷移パターンを実行します.
Submission #2960341 - AtCoder Beginner Contest 104
今回のABCはなかなか難しかったと思います...
Rate: 839 → 979 (緑)
AtCoder Mujin Programming Challenge 2018 反省
C問題コンテスト中に解きたかったなあ
A: コンテスト名 - Mujin Programming Challenge 2018 | AtCoder
substrで入力の先頭5文字を見て"MUJIN"になっているかを見る.
Submission #2941754 - Mujin Programming Challenge 2018 | AtCoder
B: セキュリティ - Mujin Programming Challenge 2018 | AtCoder
愚直にシミュレーションしましょう.
Submission #2942432 - Mujin Programming Challenge 2018 | AtCoder
C: 右折 - Mujin Programming Challenge 2018 | AtCoder
曲がる場所に着目して左右上下の空きマスを掛けあわせるとできそうだなあと思いましたが実装がなかなかきつそうだったので後回しに. D問題を解いた後戻りましたが実装に手間がかかり, 最後に最後っ屁をぶん投げるもWA. コンテスト後にいろいろ手直ししてAC. 答えの範囲がint型に収まると思っていましたが, 順序対の対は((2*10^3)^2)^2となるため確かにlong long intが必要です.
Submission #2946178 - Mujin Programming Challenge 2018 | AtCoder
D: うほょじご - Mujin Programming Challenge 2018 | AtCoder
とりあえず実験でいくつかやってみると, ある程度枝刈りすれば間に合うのではないかと思えました. そこで計算過程をみながらいろいろ枝刈りする方法を探していると, 無限ループに入る状態と入らない状態への遷移を見ればある程度計算量を落とせることに気づきました. 状態の遷移を見るので動的計画法を実装しなければなりませんが, 状態の遷移の仕方がかなり不規則であるために順にテーブルを埋めるのは難しいと考え, メモ化再帰で実装しました. 無限ループに入るかどうかはあらかじめmapを用意しておき, ある状態に遷移したら順序対をtrueに設定し, 再びtrueの状態に遷移すれば無限ループ状態と判定しました. 無限ループが確定するまでdp配列を決定することができないため, メモ化再帰がやはりうってつけです.
Submission #2944821 - Mujin Programming Challenge 2018 | AtCoder
AGC 008 B-Contiguous Repainting
いろいろ考えてみたものの, 解法が思いつかず解説を見ました.
B - Contiguous Repainting
この操作において一回以上操作を行うとき, 最後の操作が存在しており, そのときに塗る色は白か黒で, K個の連続した区間を同じ色を塗ることになります. 一回以上操作を行ったときは必ずK個の連続した区間が同じ色で塗られている場所が存在することがわかります. この最後に塗る白か黒の区間を最終区間と呼ぶことにします. では, 最終区間以外の色の塗り方の自由度はどうでしょうか. 最終区間は最後に色を上塗りすれば途中過程はなんでもいいので, 色塗りのワークスペースとして使えます.
ここで, 最終区間をワークスペースとして, 要素全体の右端または左端を含むK個の区間を白または黒で塗り, 左または右に一個ずつずらしていくことで最終区間以外の場所の色はすべて自由に塗れることがわかります. 最終区間の色は白または黒の二通りで, 最終区間の候補をすべて調べればいいことがわかります.
最終区間以外すべて自由に塗れるので, 最終区間以外の0より大きいものをすべて足し, 最終区間を白とするか黒とするか(加えるor加えない)の二択を試せばよいです.
最終区間の候補はN-K+1個あり, それぞれについていちいち合計をためしていると, $O(N^2)$となりますが, 累積和と正の要素のみの累積和の2種の累積和を使うと$O(N)$で求めることができます.
ABC 055 D-Menagerie
D - Menagerie
どこか連続する2つの位置について羊狼の割り当てを決めると, 片側の決まった動物から, すべての場所の配置を決定することができます. よって, 1番目と2番目の羊狼の割り当て(2*2=4通り)を決め, それが条件を満たしているかどうかを確認し, 4つ試して解が存在しなければ-1を出力します. 高々4通りで, 文字列の長さはNであるので計算量はO(N)でおさえられます.
Submission #2920588 - AtCoder Beginner Contest 055
ABC 067 D-Walk and Teleport
D - Walk and Teleport
見た瞬間グラフを作って最小全域木を求めたくなりますが, どの頂点からどの頂点へもテレポートが可能であるため, 辺の数が最悪$10^{10}$以上に膨れることになるため, 最小全域木の構成は辛いです. そのため, 別の解法を考える必要があります.
町は一直線上にあるため, 最小に町を渡ったとき, 徒歩で移動する区間で分割することができます. テレポートで移動したとき, 区間が分割されます. この区間の分割の仕方を考えると, 移動の仕方について, 区間の右端にテレポートして左にいっても, 左端にテレポートして右にいっても同じです(区間の分割の仕方のみによってコストが決定する). よって, 左端から順に, 右に移動するのにテレポートまたは徒歩のコストが低い方で貪欲に移動すればよいことがわかります.
Submission #2919899 - AtCoder Beginner Contest 052
