CODE THANKS FESTIVAL 2018(Parallel)
400解けません
だいたい書いてある通り。片方しか解けないときや1問目しか解けないときを気にしてあげる。
x>yのときにx=3yにできれば解けることは自明なので
x>3yならば不可能,x<3yのときはx-=1,y-=3し続けてx=3yにできれば可能なことが分かる
交流するのに必要なコストは2人の距離と等しいので
昇順でsortした後にコストの総計を考えると|xj-xi|の和になるので(0<=i<j<n)
i人目とi+1人目(0<=i<n)の間の移動にかかるコストは
(i+1)*(n-(i+1))回使われるのでそこにコスト(a[i+1]-a[i])をかけてあげればよい。
これ指示通りの操作を前からするだけで解けてしまいませんか
先頭の文字を覚えておいてそれより辞書順でそれ以上のものを見つければ覚える文字を更新してカウントも1増やしましょう。
ABC113
DはDPなんですか、僕には分かりません
素直にx+y/2で出ます.
各地の平均気温とAとの差の絶対値が一番小さい場所を覚えておきましょう.
ちょっと詰まった.
成立年順に見て各市に県内での順番を付けてあげて,後は市の番号順にIDを出力してあげましょう.
こうじちゅう
過去問埋め2
B - Between a and b ...(ABC048)
0≦a≦b≦10^18,1≦x≦10^18となるとき
a≦k≦bとなるkのうちxで割り切れるものの個数を求める問題
制約が0以上であることに注意しなければならなかった
b/x-(a-1)/xとかすると多分a=0でアなのでb/x-a/x+!(a%x)とかにするべき
長さのnの数列a,b,cについてai<bj<ckとなるパターンを数える
制約的に愚直にはできないので二分探索する。
初の二分探索だったがバグらせたので要精進。
めぐる式考えた人天才か?(これchokudaiさんなんですね)
これ天才限定パズルでは?
dpな気がしてならなかったけどx<=1000000000なので無理
簡単に言ってしまうと1+2+3+....+t>=xとなる最小のtが答えとなる
(このようなtのときある部分集合{1,2,...t}の和がxとなる)
n個のビスケットが入った袋から自由に選び(合計%2==p)となる組み合わせの数を求める
全ての袋に偶数枚のビスケットが入っていればans=0 or 2^n
それ以外のときans=2^(n-1) (i個目以外のn-1個の選び方を決めたときiを選ぶか選ばないかのどちらかが条件を満たすため)
C - Takahashi's Information(ABC088)
あまり難しくはないが一つ決め打ちして矛盾を調べるのは汎用性が高そう
Tenka1 Programmer Beginner Contest
Cまで順調に解いてパフォ1600だったので満足です。
これはいつもより易しめな気がします。
2文字ならそのまま、3文字なら1文字目と3文字目を逆にして出力してあげましょう。
これも問題自体はだいぶ読みやすかった。
奇数ターンと偶数ターンでどちらが動くか決めて後はクッキーが奇数なら-1して相手に半分あげましょう。
実装時はだいぶお気持ちで通しました。
よく考えると最大化するときに中央値よりも大きいものから小さいものを引けばいいことが分かるので大きいものと小さいものを交互に並べてあげましょう。偶数個のときは一意に、奇数個のときは2パターンできるので大きい方を見てあげましょう。
集合の数決め打ちは天才だと思いました。
CODE FESTIVAL 2018 qual B
CODE FESTIVAL 2018 qual B
早解きできなくて人権がありませんでした。(これは罠でDまで解けないのが悪いです)
A - Probability of Participation
見た目ややこしいですがサイコロの出目が1から100の100通りになってるので
100/N*100で参加しない確率p(%)が出るため答えは100-pです。
(100/Nで1-100までに何個Nの倍数が入ってるかが分かります)
N人に字の綺麗さaiと顔の面白さbiが与えられそれぞれのスコアはai*biです。
X人まで字の綺麗さを1上昇させられますがスコアが乗算で出るので顔が面白い方からX人を選ぶのが効率がいいです。後はスコアの和を取れば答えとなります。
C - Special Cake for CODE FESTIVAL
1辺の長さがNの正方形が与えられるので十字型で効率よく塗ろうという問題です(はみ出すのはあり)。
塗る回数が201800回なので基本的には1つの十字で5個塗っていかなければなりません。
真ん中を桂馬飛びで塗る場所を決めていけば効率よく塗れるので後は端の塗りこぼしを適当に塗ればよいです。(ここはかなり適当でも制約を守れます)