茶coderが1カ月だけ競プロをガチってみる

1カ月でどこまでいけるか。

【14日目①】解説のコードを読んでみて気づいたこと

昨日書き忘れましたねはい。ので今日二日分書きます。

まずは先日の最強学生プログラマー選手権(だっけ?)のE,F問題を軽く振り返って。まずF問題は座標圧縮が必要になってきそうなので明日学習しようと思う。ちょうど良さげな問題も見つけた。

atcoder.jp

んで問題のE。解説読んだ時からこりゃ実装がえらい難しそうだな…と思ったのだが、案の定自力での実装は難しかったので、解説のところにあった解答コードを読み解いて学習することにした。確か黄レベルだったと思うから今の段階で自力で解ける必要も必ずしもないと思っているし(まずは水レベル以下を確実に解けるようにしたい)。

そこでいくつか気づいたことを↓

問題自体について
  • 「折りたたむ」って文字通りSを折りたたんでいるのか。折りたたみつつ各文字の出現頻度を加算していく。自分は折り畳まずに各ユニットの先頭要素の位置と長さを記録しておいて後からSをたどって出現文字を加算していこう、としたから実装できなかったのか。

  • 正直これを自力で実装できる自信は全くない()

実装について
  • valarray, partial_sortは存在を知らなかった。iotaは前やったけど存在忘れてた。今度から使えそうなら使っていこう

  • 先頭、末尾からコンテナの要素を参照するのに、先頭からの時は順に[]演算子でアクセスしているのに対し、末尾からのときは一要素ずつpopしながらback()でアクセスしているのは何か意味があるのか?そのほうが高速なのか?

結構こうやって熟練者のコードを読むのも勉強になるなと思った。これからも少しずつ取り入れていこうと思う。