結果

A,B,C,Dの四完

A - Odds of Oddness

N/2の切り下げで偶数の個数が出ますので。これから奇数の個数を出して計算してもいいし1-偶数の確率でもよい。整数型と浮動小数点型が入り混じってグヌってました。

B - Roller Coaster

LinQ使うと楽ですね。H.Count(h=>h>=K)とでもすればよいです。

C - Go to School

登校したとき(本人含めて)n人いれば登校した人はn番目。出席番号と生徒の数を紐づけて、数でソート、番号を出力。 KeyValuePair使ったけど

for (var i = 0; i < N; ++i)
    no[A[i] - 1] = i + 1;
WriteLine(String.Join(" ", no));

と書けばちょっとかっちょいい。ような気がする。

D - Disjoint Set of Common Divisors

公約数のうち、なので対象は最大公約数以下。これに対して素因数分解、その数+1(+1は1の分)。素数求めればよい理由はあんま考えてない･･･。

なお最大公約数に対して約数求めてそれぞれに対して素数判定しても十分間に合うもよう。

ちなみにこの問題で1時間吹っ飛びました。

原因

f:id:trsing:20190929092626p:plain

f:id:trsing:20190929093340p:plain

はい、最大公約数に対して約数列挙してそれぞれについて素数か判定するガバガバ判断の上long型が必要なところでint型を使いオーバーフローでホゲってました。悲しみ。昔書いたのから持ってきたので気づくのがより遅れましたね悲しみ。涙の味を堪能すると良いでしょう。この手のミス結構やらかしてます注意しないと･･･。

と対策に「もっと注意する」を採用する~~クソ企業ムーブ~~は愚の骨頂、コンパイラさんに任せましょう。

ビルドの設定。ローカルで確認可。 docs.microsoft.com
f:id:trsing:20190929093923p:plain

checkedキーワード使用。提出先でも検出可(RE)。 ufcpp.net

設定を忘れそうな気配。~~もっと注意しよう。~~

E - Get Everything

~~DPらしい。ワカラナイ･･･~~

解説見ました聞きました。手持ちの鍵で開けれる宝箱を状態をbitで表現。状態0(鍵無し)から推移(鍵を買う)させていけばよいです。状態が巻き戻ることはないので0から順に鍵を付与していけばよく $O(2^{N}M)$ ですかね。

F - Pure

やってみたらとても簡単だった。条件を見ると内部に閉路を持たない閉路(内部に閉路があれば入出次数1が満たされない)を検出すればよいことがわかります。最小の閉路であればこれを満たす(最小じゃなくても満たす場合あるけど)。各ノードを始点にDFSして始点に戻ってきたら辿ってきたノード、パス長を記録。パス長が最小のものが答え。計算量はO(NM)かな。BFSだと最初に検出した閉路がその始点に対する最小閉路になるから計算量ちょっと減らせるか。