塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

AtCoder Beginner Contest C問題 まとめ(随時更新)

D埋めが厳しくなってきたので、C問題を復習しつつ主観的難易度をまとめます。下にスクロールすると解法が(一行程度ですが)バリバリ書いてあるので閲覧注意。


開催されたのが最近になるように並んでいます
☆の数が多いほど難しいです 教育的だなあと感じた問題には教育と書いてあります

ABC128C ☆☆
ABC127C ☆☆
ABC126C ☆
ABC125C ☆☆☆☆ 教育
ABC124C ☆
ABC123C ☆☆
ABC122C ☆☆ 教育
ABC121C ☆
ABC120C ☆☆☆
ABC119C ☆☆☆☆ 教育
ABC118C ☆☆☆
ABC117C ☆☆☆ 教育
ABC116C ☆☆
ABC115C ☆
ABC114C ☆☆☆ 教育
ABC113C ☆☆☆ 教育
ABC112C ☆☆☆ 教育

ABC109C ☆☆
ABC108C ☆☆
ABC107C ☆☆ 教育
ABC106C ☆

ABC103C ☆☆
ABC102C ☆☆
ABC101C ☆☆
ABC100C ☆
ABC099C ☆☆ 教育
ABC098C ☆☆
ABC097C ☆

ABC094C ☆
ABC093C ☆

ABC090C ☆
ABC089C ☆

[ネタバレ]

ABC128C ☆☆
Nがせいぜい10なので、スイッチのON/OFFを全列挙しても最大で1024通りになる だから、そこから全探索して、ランプがすべて点灯するようなスイッチのつけ方をあぶりだせばよい

ABC127C ☆☆
ド典型のいもす法 普通に実装するだけで解ける

ABC126C ☆
確率を求めるだけ pythonだと小数点の扱いに全く苦労しないためイージー

ABC125C ☆☆☆☆ 教育
めちゃんこ難しい D問題か? N個の要素が入ったリストの中でN-1個の要素の最大公約数を求めてあげればよいが、愚直にやったらO(N**2)かかるので無理 最大公約数は計算する順番によって変わらないという性質を用いれば、左からi番目までの最大公約数を持ったリストと右からN-i番目までの最大公約数を持ったリストを参照して、そのL[i]とR[N-i]の最大公約数を見ればよい、という解き方になる

ABC124C ☆
最終状態が黒白......か白黒.......の2パターンしかないのでそれと比較してあげればよい

ABC123C ☆☆
結局最も運べる人数が少なくなるところが律速になるので、それについて考えればよい

ABC122C ☆☆ 教育
累積和が使えれば難しくない Cに累積和、DにDPが置かれることが多い(気がする)

ABC121C ☆
リストをソートして貪欲にとるだけで解ける C問題か?というくらい簡単

ABC120C ☆☆☆
最終状況を考えることに気づかないと難しい 発想寄り

ABC119C ☆☆☆☆ 教育
制約をよく見れば全探索に気づくけど初見は厳しい 4進法を使いましょう

ABC118C ☆☆☆
気づけば簡単 気づけば...... リストの中の最大公約数を求める問題

ABC117C ☆☆☆ 教育
視点を変えて見るのが案外難しい M-1個の区間のうち駒が跨がなくてもよい区間がN-1個あるので、どこをすっ飛ばすかを検討する 距離の長い区間を上からとる

ABC116C ☆☆
扱い方がちょっと難しいかも 伸ばせるところまで伸ばしてしゃくとりっぽく進めていく

ABC115C ☆
ソートして間隔Kで最も差分が近くなるように選ぶだけ

ABC114C ☆☆☆ 教育
最終的な場合の数の少なさから全列挙を想起できるかどうか

ABC113C ☆☆☆ 教育
連想配列の扱い方、あとは0埋めができるかどうか 実装がやや重い

ABC112C ☆☆☆ 教育
入力に必ずh!=0となるようなhが存在することに気づいて、それを使って中心座標についての全探索ができるかどうか



ABC109C ☆☆
初期位置と各座標との差をとり、それらの最大公約数を出せばよいだけ 互除法が使えれば難しくない


ABC108C ☆☆
数学 Kが奇数だったらa,b,cのmodKが0、偶数だったらa,b,cのmodKが0かK//2になればよい 面白くない問題

ABC107C ☆☆ 教育
0から始めて、左端と右端を左→右の順で訪れるのか、それとも右→左の順番で訪れるのかというのを全探索で殴る問題

ABC106C ☆
数列は1以外の数字が入っていればバカ長くなるので、もとの数列を見てK番目まですべて1なら1、そうでなければ初めて1でなくなるところを出力すればよい バグらせがち 



ABC103C ☆☆
結局余りの合計が最大になるのは(全部の数字の最小公倍数-1)を各数字で割ったときの余りを足したものになり、それは各数字をL[i]として余りがL[i]-1と出てくるので、(全部の数字)-(数字の数)が答え これめちゃくちゃ賢い 実験して気付こうねってタイプの問題

ABC102C ☆☆
全ての項に対してbが共通なので、それについて考えればよい A_i-iを出してそれの中央値をとれば(すべてからまんべんなく引けるという意味で)bにふさわしいのでこれが答え

ABC101C ☆☆
最小値は1に他ならないので、N-1個の数字を幅K-1で1に置き換えることを考える

ABC100C ☆
実質全数字を何回2で割れるかを出すだけなので何も難しくない

ABC099C ☆☆ 教育
分からないとめちゃくちゃ難しそうに見えるけど実は単純な動的計画法 dp[i]を、「i円を引き出すのに必要な最短手数」として、引き出せる金額をjとし、dp[i] = min(dp[i-j],dp[[i])で更新していけばよい minを使うので最初のdpリストはinf埋め、dp[0]=0,dp[1] = 1とすること

ABC098C ☆☆
まず左から右に向かってEの人数を数える WEEWWという文字列だったらEast = [0,1,2,2,2]みたいなリストを作る これをWの人数もやると(逆順に数える) West = [3,2,2,2,1]となる 求めるのは、maxEast = ME, maxWest = MWとしたとき、i=0~N-1に対する(ME-East[i])+(MW-West[i])の最小値

ABC097C ☆
K = 5という制約からせいぜい5文字が限界(例えば答えが5文字になるのはaaaaaのようなときの場合のみ)なので、5文字以下の部分文字列を全列挙して比較して、最初からK番目を出せばよい

ABC094C ☆
出てくる数字はソートしたときのL[N//2]とL[N//2-1]しか出てこないので、これより右にあるか左にあるかで判別する

ABC093C ☆
全体の和の偶奇が不変であることに着目するらしいです まあそんなこと気にしなくても脳死でコーディングできます


ABC090C ☆
実験すればN == 1 or M == 1のときとそうでないときで場合分けすればいいことに気づく

ABC089C ☆
数えてコンビネーションするだけ