AtCoder Beginner Contest 313参加記（A～B）
第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）に参加したので記録を残します。
ただ、Unratedで途中参加（50分遅れ）です。引き続き体調悪いので、成績は一旦気にしないこととして、とりあえず参加だけしました。
単純にABCとして参加しているので予選云々は私としては特に関係ありません。
A - To Be Saikyo
最大値を取得して、1番目との差分 + 1を出力すればいい… と思ったのですが、既に最強である場合は「+ 1」がいらないのと、最強タイの場合は「+ 1」だけ要るので少し分岐が必要となってしまいました。
分けるとしても、既に最強の場合とそうでない場合の2パターンにまとめてもよかったかも。
fun main() {
val n = readLine()!!.toInt()
val p = readLine()!!.split(" ").map { it.toInt() }
val max = p.max()!!
val diff = max - p.first()
if(diff != 0) {
println(diff + 1)
} else if(p.count { it == max } == 1) {
println(0)
} else {
println(1)
}
}
B - Who is Saikyo?
競技プログラマーの番号が頂点、強さを辺とした有向グラフとして考えることができます。
「全ての情報が正しくなるように、全ての相異なる2人組にどちらが強いかを割り当てる方法が少なくとも1通り存在する」ということなので、サイクルや多重辺や自己ループなどはなさそう。
入力される値をそのままグラフ化すると強い人から弱い人に向かって辺が伸びますが、個人的にはなんとなく逆のほうがイメージしやすいと思ったので逆で扱いました。
最初はDFSなりBFSなりで探索するのかなと思ったのですが、よく考えると（上の通り逆バージョンの場合）最強の人からは辺が伸びないことになります。グラフを隣接リストで扱う場合は各頂点から伸びる辺を可変長リストで持ちますが、最強の人に対応する頂点ではその辺のリストが空になります。なので、辺リストが空となっている頂点を単純に線形探索すれば答えを求められます。
辺リストが空の頂点が複数あった場合は、そのうちの誰が最強なのか不明なので答えが-1になります。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val graph = Array(n + 1) { mutableListOf<Int>() }
repeat(m) {
val (a, b) = readLine()!!.split(" ").map { it.toInt() }
graph[b].add(a)
}
val list = (1..n).filter { graph[it].size == 0 }
if(list.size != 1) {
println(-1)
} else {
println(list.first())
}
}
意味不明な考察をして一回WAを出したのは内緒
C - Approximate Equalization 2
この時点でもう残り10分しかなく、また不調脳ではもう限界だったので解いてません。
感想
ABしか解いていないですが、それでも楽しいですね。今まで調子が悪い場合はUnratedでもなく不参加としていましたが、Unratedでも不参加よりかは楽しいとわかりました。
もちろんRatedで参加するのが一番楽しいですが、もうちょっと回復してからでないと厳しいですね。
全然競プロとは関係ないのですが最近は疲れ方が異常だし、頭も動かないしでだいぶ健康を害してしまっていると思ったので、健康状態の改善を頑張りたいと思います。
かといって完全に競プロとか数学から離れるとそれはそれで辛いので、ウォーキング中に問題を考えてみるとか、無理しない程度にやっていこうと思います。
直近のレートは捨てるとしても、長期的に見たらまた上がっていくはずなので…（小声）
（執筆時間: 25分14秒）
Discussion