出力を入力へ

プログラミングに関する基本的な事を中心にまとめます

SRM619Div2Medium ChooseTheBestOne

アルゴリズム的に何か難しいわけではないけど、
実装上の工夫?として必須だと感じたのでメモ。

TopCoder Statistics - Problem Statement

問題の概要は以下の通り。
N人を円状に並べ、1〜Nで番号付けする。
1番目の人から時計回りに以下の操作を繰り返す。
t番目の操作に対して、t^3番目の人を円から削除する。
t+1番目の操作は削除した人の次の人から開始する。
このとき最後まで残された人の番号を求める。


解法としては、単純にシミュレートすればよい。
各操作の起点となる番号からt^3番目の人を選んで削除する。
N<=5000のため、t^3をループで回すとTLEになるが、
円に残された要素数の剰余だけシミューレトすれば十分。

ポイントとしては2つある。
1つ目として、直線ではなく円に要素を並べる場合、
要素へのアクセスに要素数の剰余を利用すると便利であるということ。
剰余計算が遅いとはいっても、これが時間制約に影響することはほとんどないはず。

2つ目として、要素を順番に抜いていく場合は
配列ではなく、リストを利用すると実装が簡易化できるということ。
最初に解こうとした時、要素が削除済かを管理する配列を
参照・更新しようとしてしまい、無駄に複雑化してしまった。
削除した要素はその後考慮不要なので別途管理は不要。

https://gist.github.com/f2083c57bc5b18bba1a8