みんなのプロコン 2019予選
うーん、3完早解きです。DはDPのDだと覚えます...。
[(N+1)/2]個選べます.
1つの街が3個道を持つとダメなので各街の持つ道で積を取りました.
A枚まで増やした後は一生ビスケットを叩くか交換し続けるか得な方をします.
最後の1回でお金をもらってもしょうがないことには注意しましょう.
2時間近く溶かしました.つらい.
ABC117
36分5ペナで全完です(Unratedだからって提出デバッグしてはダメ)
世界Bと世界Aでの経過時間の比はX*t:tで,X*t=TとなるX,Tが与えられるのでtについて解きましょう.
定理が与えられているので辺の長さの合計をS,最長の辺の長さをLmaxとしたとき
S-Lmax>Lmaxかどうかを確認しましょう.
これ証明なしで解いてしまいました・・・.
最初に駒を置く場所は自由なのでN箇所までは移動なしで埋まるため,残りのN-M箇所をなるべく動く量を減らして移動したいです.
よって隣接する目標地点との座標の差を持つ数列aを作ったときにaの小さいほうからN-M個の合計を取ったものが答えとなります.
(追記)貪欲嘘らしいので話半分に読んでください・・・
(追追記) これだけ最上位桁以外を取る時で落ちるので最上位桁を取らない場合でも貪欲を試しましょう.(最上位桁を取らなければ他の全パターンを考慮して貪欲できるため)
こういうのは上から決めたいって過去問で見ました.
Kの値を超えないように上からビットを検討していきます.(上のビットの方が数字が大きく,答えに与える影響が大きいため)
各A[i]とXORをとった和を最大化したいのでXのjビット目を1にするべきかはA[i]&(1<<j)の数が半分未満であるかどうかで判別できます.ちょうど半分のときは検討するビットをなるべく増やすために含みません.
全国統一プログラミング王決定戦予選
ABC遅解きなので会場には行けません,悲しいね
なんでこんなややこしいのを100点にしたのでしょう.
集合ができればできます.
文字列A,B,Cが与えられます.
i文字目が3つとも同じなら0回,1つ同じなら1回,すべて異なるなら2回変える必要があるのでその合計を求めます.
これ実装に実力がでる気がします.
お互いに相手との差を最大化したいので各料理iに対して相手の得るはずだった幸福度と自分の得る幸福度すなわちAi+Biを求めておきます.
これが大きいほど自分が選んだ時得をしますがさらにこの値が同じとき高橋君はAiが大きいほど青木君はBiが大きいほど得をするのでそのような選び方を実装する必要があります.(この部分不要みたいです)
ABC116
D分かりませんが
(追記)D通しました.ぷらいおりてぃきゅーがわからないのでチョットキタナイ
よく見ると角ABC=90°と書いてあるのでAB*BC/2で終わりです.(面積が整数とも書いてあるので)
シュミレーションして間に合うので.
sが偶数のときs=s/2,奇数のときs=3s+1をやりましょう.
一番左の花[i]<h[i]となるiの高さを増やすときになるべく右側までまとめて増やしたほうがお得なのでiの高さを1増やすたびにi<k<j(花[k]<h[k])となる[i,j]で高さを1増やしてあげましょう.
ソートしただけでTLEしたから分かりません.
貪欲した後種類を増やしていくんではないんですか.
(追記)方針はあってた.
貪欲する時に各種類の寿司の価値が2番目以下のものを覚えておいて新しい種類の寿司が来るたびにそこの最小のものと入れ替えます.
これは種類を増やさないなら貪欲が正しいことが自明,種類を増やすなら貪欲から種類を減らさないような最小のものを取りだして新しい種類の寿司の中から最大のものと入れ替えればいいことから分かります.
KEYENCE Programming Contest 2019
3完(遅)でした,つらいね.
4つの数字がそれぞれ異なることが求められているので
A1~A4のどれかが1,9,7,4であることをそれぞれ確認していけばいいです.
keyenceになる文字列を求めましょう.含むじゃありません(1WA).
全パターンの取り除き方を一度に試すのは書くのが大変なので,前/後ろからi文字削るパターンとi文字目からj文字目までを削るパターンは別々に調べてあげましょう.
後者はsubstr(0,i)+substr(i+j)とかです.
これも変換後の数列を出力するかと思いました.(ちゃんと読みましょう)
まず準備度の総和が必要分を下回ると魔法の力でもどうにもなりません.
さらに準備度が下回っている試験はすべて変える必要があって余裕のある試験はなるべく変えたくありません.
そこで準備度が足りている試験の必要分との差を数列aとして持っておくと,aを降べきの順に累積和を取ったときに初めて準備度の不足分を超えるときのaの要素数と準備度が足りてない試験の数の和が答えとなります.
AISing Programming Contest 2019
冷え冷え2完
(*追記)C普通にBFSで解けるじゃん
縦に(n-h+1)横に(n-w+1)マス自由に動かせることは実験すればすぐ分かります。
同じ問題を別のコンテストに使えないので1問目候補,2問目候補,3問目候補のうち最も数の少ないものと同じ回数だけコンテストは開けます.
各黒について幅優先探索っぽいことしたらTLEしました(それはそう)
(*追記)これ行き来できる部分の(黒マスの数)*(白マスの数)の和が答えになるので間に合いますね.
元々のコードが各黒マスからBFSっぽいことをしてたので改良して,一度調べたマスと行き来できることを確認したマスについては調べないようにしたら普通に通りました(なぜこれがコンテスト中に思いつけないのか)
CADDi 2018 for Beginners
CADDi 2018 for Beginners - AtCoder
よく見る気がする問題.
10で割ってはx=2(mod10)かどうかを確かめ続けましょう.
縦と横で数字が2つありますがi番目が満たすべき条件はa[i]>=h&&b[i]>=wと独立した比較なので簡単です.
†実装力†
ちゃんと実装できますか.僕はできないのでペナがいっぱいつきました.
2^40>10^12なのでn>=40ならば公約数が2以上でpを超えてしまうため必ず答えは1です.
各素因数の数がk個のときに最大公約数はその素因数を[k/n]個持つので後はn==1だけ例外にして(ans=p)素因数分解の気持ちになりましょう.
30を言ったら(勝ち/負け)のゲームみがありました.
まず各りんごの数を自分の手番で0にできれば自明に最後のりんごも食べれます.
りんごの数を0にするためには相手が食べた時に残りが1になる必要があることを考えて一般化すると相手が食べたときに奇数個,自分が食べたときに偶数個にできるように操作できれば勝てます.
プレイヤーは各りんごの数を0or1個減らす操作ができるので各りんごの偶奇の状態は現状維持以外の全ての場合をとれます.
よって最初の状態で全てのりんごが偶数個ならルンルンの勝ち、それ以外ならあなたが勝ちます.