半年だけ競プロやってみた!!!

コンテストの内容を含むのでネタバレ注意です。半年くらい競プロ続けたらどうなるのかワクワクしてる。

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]=1h[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問題に時間をかけ過ぎたことだと思います。単純に知識が不足しているのを感じます。

 

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

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