ABC211の感想

A,B,Cの3問解いて600点という結果でした。

C問題に時間かけすぎてD問題に手を出せませんでした。

ABCのABCを解くだけの人間になっててわろた。

今回のC問題はいつもより難しかったぽくてパフォーマンスがいつもより高く出ました。

C問題　C - chokudai

入力された文字列から8文字取り出したときに順序を変えずに「chokudai」と読めるものは何通りあるのかという問題。

例えば「chchokudai」では「chchokudai」「chchokudai」「chchokudai」の3通りがあります。（間違ってたらすいません。）

この時に大切なのは「chchokudai」の色付きの部分です。hの前にはcが1つあるので「chchokudai」のように「chokudai」を1つ作ることができます。一方で、hの前にはcが2つあるので「chchokudai」「chchokudai」のように「chokudai」を2つ作ることができます。次に「chchokudai」のoについて考えてみましょう。oの前には「chokudai」を1つ作ることができるhと「chokudai」を2つ作ることができるhがあります。このhhを用いて「chokudai」を3つ作ることができることがわかります。kの前には「chokudai」を3つ作ることができるoが1つあるだけなので、このoを使って3つの「chokudai」を作ることができます。u、d、a、iについても同様に考えます。これらの文字の前には3つの「chokudai」を作ることができるk、u、d、aがあるので結局3つの「chokudai」を作ることができるとわかります。

じゃあどうやって実装するんだ？って話です。

簡単のため「chchokudai」を例にして話を続けます。

私はc, h, o,...に対応するvector（配列）を考えて解きました。例えば配列hのi番目にはi + 1番目のhから何個の「chokudai」を作れるかをメモします。「chchokudai」の場合はh[0]には1、h[1]には2とメモをします。配列cには何をメモするかが課題となりますが、cを見つけたら1とメモをしておくと楽になります。配列oにはh[0]=1とh[1]=2の和を用いてo[0] = h[0] + h[1] = 3とメモをします。

具体的に実装したプログラムの動きは以下のようになります。

「chchokudai」の1文字目を見ます。1文字目は1番目のcなので配列cの0番目に1とメモします。

「chchokudai」の2文字目を見ます。2文字目は1番目のhです。配列cにはc[0] = 1と書かれています。このことからこのhの前にcが1つあるとわかります。「chokudai」が1つ作れると言えるのでh[0] = 1となります。

「chchokudai」の3文字目を見ます。3文字目は2番目のcなので配列cの1番目に1とメモします。

「chchokudai」の4文字目を見ます。4文字目は2番目のhです。配列cにはc[0] = 1、c[1] = 1と書かれています。このことからこのhの前にcが2つあるとわかります。「chokudai」が2つ作れると言えるので配列cの値の総和をとり、h[0] = c[0] + c[1] = 2となります。

「chchokudai」の5文字目を見ます。5文字目は1番目のoです。配列hにはh[0] = 1、h[1] = 2と書かれています。このことから、このoの前のhを使って「chokudai」が2つ作れると言えます。配列hの値の総和をとり、o[0] = h[0] + h[1] = 3となります。

このように「chokudai」の中に含まれる文字を見つけた時にはその一つ前の文字の配列の総和をとり、値を代入していくことを繰り返す（cの場合は1を代入する）ことで答えを導くことができます。

文字列「chchokudai」を読み取った後は配列iの総和を求めて出力することで答えが出ます。

考え方は以上となりますが、一々配列の総和を求めるのは計算時間がかかりすぎると考えたので、配列c, h, o...の他に配列c, h, o...の現在の総和をメモする値としてsum_c, sum_h, sum_o...を用いて計算時間を短縮していました。

 軽く解説して振り返るつもりがめっちゃ長くなってしまった。

間違っている部分もあるかもしれませんが多めに見ていただけると幸いです。

今回の反省としてはC問題に時間をかけ過ぎたことだと思います。単純に知識が不足しているのを感じます。

アホブログからアホ（天才）ブログに改名しました。

理由はアホかどうかは自分で決めるものではなく他人が決めるものだと思ったからです。

ABC210の感想

A,B,Cの3問解いて600点という結果でした。

D問題には40分くらい残すことができましたが、解法が思い付きませんでした。

過去問でのC問題の打率は4割程度といった感じだったので自分としては上振れだと思っています。

C問題　C - Colorful Candies

N個並んでいるキャンディから連続したK個を持ってくる。キャンディにはそれぞれ色（番号）が振られていて出来るだけ多くの色のキャンディを持ってくるという問題。

「連続したK個を取り出し、重複要素を削除して種類数を求める」ことを繰り返すアルゴリズムを組んだ結果時間内に計算が終わらなかった。連続したK個のキャンディの種類を繰り返し求める際には、先頭要素と最後の要素のみを調べれば良いことに気づき解くことができた。

D問題　D - National Railway

• 最小化するためにどの動作を繰り返せば良いのか分からなかった。
• 10^6の要素から異なる2つを選ぶことを全てのパターンに対して行った結果計算量が爆発して人生終了した。

自分としては満足した成果をあげることができたと思っています。

しかし、計算量を見積もる能力の低さや動的計画法はなんとなく知ってるけど実際に問題を解くときにはどうすればいいか分からなくなってしまうという自身の弱みが露呈してしまいました。次回に向けて動的計画法の問題を解きつつ、計算量の見積もりはいつか出来るようになると神に祈ることにします。