Q.一週間たってからとか遅ない？
A.話の途中ですまないがE4の群れだ
今回も艦これイベントやばいですね(震え声
結果
A,B,CはAC。Dはスルー。Eは提出したけどTLE。D,Eは後日解説見ながらAC。Fは解説見た(見ただけ)。
B - Guidebook
C#の場合OrderByとThenByDescendingを使えば良いです。
なんか都合良い機能あったよなーと探してるうちに15分経過していました。悲しい。
C - Switches
スイッチは最大10個、つまり状態は最大。
電球も最大10個、状態確認は電球1個あたりせいぜい10回なので最大100回。
合わせてせいぜい10万オーダー。全列挙いってみよう。
でぐるぐる回して値をスイッチの状態に割り当てると楽(ビットで考える。0なら全部off、1ならスイッチ1だけon、
なら全スイッチonみたいなの)。
余談
パッと見全然わかりませんでしたが、Cなのでなんか方法があるはずと問題文じっくり読んで計算量考えたら全列挙でいけるやんと気づきました。これがD以降として出題されてたら諦めてましたね・・・。計算量の確認大切大切。
D - equeue
解説通りですね。全探索いける計算量、操作C,Dの筒に詰める=手元から宝石を捨てる、ということに気づけば。
気を付けるところがちょくちょくあるので注意というか引っかかった。
var lmax = Math.Min(K, N);//A+B<=min{N,K} //for (var left = 0; left < lmax; ++left)//0は選択しない、なので<=でlmaxまでいるよ for (var left = 0; left <= lmax; ++left)
余談
今回は、そのう・・・まだあまり把握していないのだが・・・ナップザック問題の亜種を？ DP*1を・・・使って？ワカラナイ！アーッ！
ｶｶｯとスルーしました。C問題で計算量確認の大切さを思い知ったのにこの体たらくよ。
E - Roadwork
解説通りですが図にするとわかりやすくなりますね。 まず工事から逆算すると、工事にぶつから出発時間帯がわかります。
に出発すると工事iにぶつかる。近場の工事優先。
と工事にぶつかる時間帯を突き合せていけばよいですが単純にやると
でTLE*2。
工事の発生、終了時刻で処理(時刻より前のを判定、工事中リストに工事を追加/削除)を行っていくと間に合います。
C#だと工事中リストにSortedDictionary使うと楽です。出力部にちょいと小細工が必要でしたが。
小細工
これだとTLE。
foreach (var d in dst) { WriteLine(d); }
間に合った。(ボックス化してるかも…)
StringBuilder ans = new StringBuilder(); foreach (var d in dst) {ans.Append($"{d}\n");} WriteLine(ans);
なおこれは最初のよりもっとダメ。stringは不変型なので編集ごとに作り直してるから仕方ないね。
string ans = string.Empty; foreach (var d in dst) {ans += $"{d}\n";} WriteLine(ans);
F
そのうちやるかも
所感
演算量！
出力多い場合気を付けてね！
