0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

7/12 ICPC2016国内予選のA, B, C問題を解きました(今更)

ICPCの国内予選が目前に迫ってきているわけですけど, 実は自分は昨年はICPC参加してないんですよね. AOC-ICPCでも昨年の問題は最後に残しておこうと思って, 今日まで解かずに温存してありました. というわけで, 今日はABCまで解いてみました. ABCは難しくなかったかなぁという印象. なるべく高速に解きたいところだけど, 本番で緊張すると意外とできなかったりするんだろうなぁ.

 

AOJ-ICPC

  • Selection of Participants of an Experiment | Aizu Online Judge [解答]

    ソートして要素間の差を取って最大値を求めるだけ. 瞬殺したい問題. こういう問題は読解力勝負だなぁと.
  • Look for the Winner! | Aizu Online Judge [解答]
    地味に問題文が複雑で本番だとテンパりそうで怖い. 一票ずつ開票して, その状態である候補者と他の候補者の得票数の開きが残り票より大きければその人が当選. 後から気づいたけれど, 制約が厳しくないから一票ごとにソートして1番目の候補者と2番目の候補者の差を見るだけでもよいかも. こっちのほうが実装楽そう.

  • Bamboo Blossoms | Aizu Online Judge [解答]
    エラトステネスの篩みたいなことをすると解ける問題. 問題文に最大ケースの答えが出ているので, その値+1の大きさの配列を用意する. 最初は全部trueで初期化しておく. m番目から順にtrueな要素を見つけたらその倍数をfalseにするのを, trueな要素がn個見つかるまで繰り返す. そのあとに出てくる最小のtrueな要素のインデックスが答え. エラトステネスの篩って, O(Nlog(logN))とかだったと思うのだけれど, これもそれぐらいで求まるんですかね.