AtCoderめッ！難しい問題出すんだからッ！
『AtCoderとは、プログラミングを用いて戦う頭脳スポーツ「競技プログラミング」のコンテストサイトの一つ』だそうです(サイトから引用)。
知るきっかけは先輩が毎週参加しており、「出てみん？」と言われたこと。
当時C#を勉強中？の私はBigginerコンテストに参加をしたが全然歯が立たず...。
まぁ今でも歯が立ってるとは思いませんが。
特に悩んでいたのはC問題。ここを毎回突破できずにいました。
なぁんとなくそれっぽいコードを書くことはできるんですけど、実行時間の制限に引っかかってしまい。そうなんですよ、実行時間にも制限があるんですよ。
そんな私を救ったのが、『Dictionary』ってわけ☆
というわけで今回はC#のDictionaryのお話し、始まり始まり。
語るまでもないか？Dictionaryの話
Dictionary君、何が便利なのか。
個人的な使用感としては「タグ付け」のイメージ。
こんなこと言うと『貸せ！Dictionaryってのはこう使うんだよ！』と怒られるかもしれませんが、そこは個人の使用感&プロコンでしか使ったことがない、なので目をつぶっていただきたい。
var fukuro = new Dictionary<int, int>();
DictionaryにはKeyとValueが存在している。前半のintがKeyにあたり、後半のintがValueにあたるものとなる。
Keyが先ほど言っていたタグ、Valueがそのタグに紐づけられた何かしらのものであり、Keyで検索をかければ目的のもの(Value)をｻｯと取り出したり、逆にValueに変更を加えることができる。
今回はintとしているが、ValueをstringやListなどにもできるのでそこは自分が何を必要にするかに応じて変更すること。
この説明ではまだピンと来ないはず、ということで実際に問題を解いてみましょう。
早速使ってみようじゃあないか
というわけでDictionaryを使って問題を解いてみませう。
今回は2024年8月10日開催『AtCoder Beginner Contest 366』のC問題を。
上のリンクからアクセスできますが、問題も画像で貼り付け。
要約してしまえば、「数字を書いたボールを、袋に入れるか出すかするから、こっちが『袋に入ってるボールに書かれた数でユニークなものは何個』って聞いたらその都度答えてね」といったところ。
さて、まずはDictionaryのKeyとValueを明確にしておきましょう。
今回の問題において、Keyはボールに書かれた数字、Valueは袋の中のボールの数、とします。このように設定しておけば、例えば、『1と書かれたボールを袋に入れる』という操作の場合、Keyが1となっているものを引っ張ってきて、紐づいているValueに+1するなんて操作が行える。
百聞、百イメージは一見にしかず、実際に書いたコードをご覧あれ。
var num = int.Parse(Console.ReadLine()); #何回操作を行うかを格納
var fukuro = new Dictionary<int, int>(); #Dictionary爆誕
var final = new List<int>(); #OutputのためのListも用意
for (int i = 0; i < num; i++) {
var line = Console.ReadLine().Split(); #入力を読み込んで操作を確認
if (line[0] == "3") {
final.Add(fukuro.Count); #操作3は出力となるためDictionary内のKeyの数を格納
}
else
{
var siji = int.Parse(line[0]); #1だったら袋に入れる、2だったら袋から出す
var checknum = int.Parse(line[1]); #対象とするボールに書かれた数字
if (siji == 1) {
if (fukuro.Keys.Contains(checknum)) {
fukuro[checknum] += 1; #KeyがDictionary内にあるならばそのKeyのValueに1追加
}
else {
fukuro[checknum] = 1; #KeyがDictionary内にないならば新たにDictionaryに追加
}
}
else if (siji == 2) {
fukuro[checknum] -= 1; #対象のKeyに紐づいているValueから1個減らす
if (fukuro[checknum] == 0) {
fukuro.Remove(checknum); #減らしたうえでValueが0ならKeyごと削除する
}
}
}
}
foreach (var item in final) {
Console.WriteLine(item); #操作3のタイミングで出力されるはずの数字がまとめられたリストを出力
}
コードで行っていることとしては
・何回繰り返すかをチェック
・袋に入れる、袋から出す、ユニークな数字の数の確認の3操作の確認(繰り返される部分)
→(袋に入れる場合)すでに袋の中に対応する数字があるならばValueに+1、存在しないならばKeyを追加してそのValueを1とする
→(袋から出す場合)対応するKeyのValueを-1、その際Valueが0になるならばKeyを削除
→(ユニークな数字の数の確認の場合)Listにその時点でのKeyの数を格納
・最終的にListに格納した数字を出力
といったところ。
あぁなんて便利なDictionary君。今後も彼の活躍からは目が離せない。