2021/02/16
解読 (Deciphering)
JOI 難易度8
以下のように定義する。
dp[i]:i番目の文字で終わる原文からi-1番目の文字まででできる原文を引いた総数
cnt[i][a]:i番目の文字までを考慮したとき、文字aで終わる原文の総数
dp[i]=sum(cnt[i-1][a](文字aとi番目の文字が連続することは禁止されていない) a='A'~'Z') - cnt[i-1][i番目の文字]となる。sum(dp)が答え。実際にはcntは一次元配列で実装した。
散歩
JOI 難易度8
N-1回の散歩で各交差点に何回訪れたかが分かれば解くことができる。(0,0)にはN-1回訪れている。(0,1)には(N-1+(0,0の最初の文字)==東?1:0)/2回訪れているって感じで求めていく。
Skate
黄diff
twitterを見る限り典型らしい。解説動画を見た。
行と列を分けた二部グラフを作る。#は辺になる。「この二部グラフが連結になる」と「スケートリンクに無駄はない」は同値。
日記
いろはコンDay1の残りを脳内ACした。明日実装する。
