結果
人生2度目の5完を目指すも叶わず。4完が少しずつ安定してきたことに成長を感じます。
A問題
全桁の数字に111をかけて足し合わせてAC。A問題を少し工夫して解くことができたのは初めてです。
B問題
前の台から愚直に大小比較していきました。今の台の高さ>=次の台の高さの時、高橋くんは動かなくなりbreakです。
C問題
各数字が何番目に登場するかを辞書を使って記録していきました。例えば"5"がa0、a3、a7に登場するときはdictionary[5]:[0,3,7]です。数字xiの登場回数がki回を超えている時は、dictionary[xi][ki-1]を出力します。1を引いているのはlistが0-indexedだからです。
D問題
dequeを使って、愚直にシミュレーションしました。まだ生成されていない数字が新たに作られた時のみdequeに追加することで、計算量は必ずO(10**6)におさまります。各数字を生成するのに必要な回数をlistに格納していき、目的の数字が生成される、もしくはdequeが空になったらbreakです。
E問題
解けませんでした。まず、コンテスト中にクラスカル法のアルゴリズムを復習しました。必要知識をコンテスト中にググった問題が解けたことはほとんどありません。解けぬべくして解けなかったと言えます。クラスカル法は重みの小さい辺から順に選んで、閉路にならないのであれば採用していくというアルゴリズムだと分かったので、新たに追加される重みwの無向辺がuとvを結ぶとき、wよりも重みの小さい辺でuとvが結ばれうるのであれば、追加辺は最小全域木を構成する辺になり得ない、それ以外は追加辺になる。と考察したのですがWA。最後まで何が違うのかがわからずタイムアップしてしまいました。
コンテスト後、実装が考察を反映できていなかったことに気づきました。勝手に連結判定しているつもりでしたが、できていませんでした。
総括
E問題が解けない問題から解けそうな問題に変わってきた実感があります。5完が当たり前になる日を夢見て、少しずつ精進していきたいと思います。
余談
kaggleに興味があるのですが、何から始めたらいいのか分かりません。春休みに入ったら少しやってみようかなと思ったり思わなかったりです。
