バイトがクソ忙しくて全然問題を解いていません。全部コロナが悪いんだ。
もうちょっとでMedium100が終わりそうなので、頑張っていきたいと思います。
目次
1.ARC093C問題
キーワード:数直線、取り除く、総和、先に全体のコストを求めておく
N個の観光スポットの内一つ訪れない場合のコストの総和を求めます。
まず全ての観光スポットを訪れる場合のコストを求め、その全体のコストから一個前のスポットから訪れないスポットまでのコストと、訪れないスポットから次のスポットまでのコストの和を引き、最後に一個前のスポットから次のスポットまでのコストを足せば、そのスポットを訪れない場合の全体のコストが計算できます。
図に表すと次のようになります。
また、スタートとゴールは決まっているので、訪れるスポットにスタートとゴールである0の座標を入れています。
2.ABC068C問題
問題:C – Cat Sunuke and a Voyage
キーワード:グラフっぽい問題、移動、可能/不可能
島1から島Nまで定期便2つを使っていけるかどうかを調べる問題。グラフの問題っぽいですが、島の数が多いため愚直にやるとTLEします。
解説ではいろいろな方法で実装できることが書かれています。ハッシュテーブルだとO(1)らしい。
私は全く解けなかったので、他の人の解答を参考にしました。
今回の問題は島1から島Nへ行ければいいので、島1を出発する定期便と島Nに到着する定期便さえわかっていれば、あとは繋がっているかどうかの判別だけで済みます。
そのため、まずは定期便の中からそれに合致するものを入力の時点で探し出し、それぞれ保持しておきます。この時、グラフのようにa[出発元]={到着先}という風にしておきます。到着側では、ある島から来た場合trueにするbool型のvectorで表します。
ここまでやると、出発元が島1である場合の到着先を一つずつ取り出し、到着側と照らし合わせて到達可能かどうかを判別して答えが出せます。(19~25行目)
3.ABC137C問題
キーワード:アナグラム、数え上げ、ハッシュテーブル
長さが等しい複数の文字列が与えられるのでアナグラムになっているものの個数を数える問題。難しそうに見えますが、解説を見れば何となく分かると思います。
まず、アナグラムになっているものはソートすると同じ文字列になります。
次に、一度出現した文字列を管理する必要がありますが、今回は探索を高速に行いたいのでハッシュテーブルを用います。
C++のハッシュテーブルでは、探索してなかった要素はハッシュテーブルのkeyとして登録されます。めっちゃ便利です。
最後に考えるのは、同じ文字列が出現した時の数え方です。2つ目が現れると答えに1を加算、3つ目が現れると答えに2加算のように、出現回数-1を答えに加算していきます。
同じものの数え上げとかはハッシュテーブルが便利だと思いました。しかし、ハッシュテーブルのkeyとvalueを順番通りに取り出そうとすると、ハッシュテーブル内は入れた順序では格納されていないので、そのようなときはmapを使おうと思いました。
4.ABC072D問題
キーワード:順列,swap,最小回数,やるだけ
順列の要素をスワップして、要素番号と要素の値が異なるようにしたいという問題です。
実装は、問題文をそのままコードに落とし込めれば勝ちです。
単純に要素番号と要素の値が一緒ならば次の要素とスワップして、そのときにカウントを1増やせばいいです。最終的にカウントを出力すればOK。
次の要素とスワップしてるだけなので、スワップ後に、もしかしたらどこかで要素番号と一致してしまうのではと思ってしまいますが、要素番号と一致した要素を後ろに回して、次(まだ判定していない部分)の要素(今見ている要素番号とは絶対に一致しない値)を前に持ってきているだけなので、一致することはありません。
5.ABC089C問題
問題:C – March
キーワード:パターン列挙、数え上げ
条件を満たすように3人を選ぶ方法を求めよという問題。
条件は問題を見てもらえばいいですが、名前がM,A,R,C,Hのどれかから始まり、かつ同じ文字から始まる人が複数いないというものです。
例を挙げるならば、Mから始まる名前の人、Aから始まる名前の人、Rから始まる名前の人というように3人を選びます。
結局やることは、M,A,R,C,Hから始まる人の名前の人をそれぞれカウントして、最後に場合の数の総和を求めれば答えが出ます。
しかし、場合の数の総和を求めるときに問題があり、今回は5種類のグループから3種類のグループが選べるので5C3で10通りのパターンがあります。それぞれについて場合の数を計算するわけですが、普通に書くとめちゃくちゃめんどくさい。
そういうわけで、今回は選びうるパターンを3つの配列を用いて予め表しておくと、コードがスッキリします。(22~24行目)
この記述の仕方は他人のコードを参考にしました。(どのコードを参考にしたかはわからなくなりました。)
6.ABC158D問題
キーワード:文字列、文字列操作、反転、分割して考える
文字列に対してある操作を行います。ある場合は文字列を反転、ある場合は、文字列の先頭あるいは最後尾に文字を追加します。
これを真面目に実装するのは簡単ですがTLEします。そのためうまい方法を考える必要があります。
今回ボトルネックになっているのはreverseの計算量。これがTLEの原因ですので、毎回reverseしないようにしたいです。
ここで、文字列は先頭がどっちかわかっていれば文字の追加ができるため、文字列の先頭がどっち側にあるかでreverseの処理を代替します。
また、文字列の追加についても、文字列の前に結合する文字列、後ろに結合する文字列を作成しておき、最後に結合すれば良さそうです。
結合するときにそれぞれの文字列のreverseし忘れに注意です。
7.ABC118C問題
キーワード:最小値、繰り返し
モンスターが別のモンスターを攻撃すると、攻撃されたモンスターは体力が攻撃したモンスターと同じだけ減らします。最終的に生きているモンスターの最終的な体力の最小値を求める問題です。
私の解法は、最小値と操作後の最小値の2つを持っておきます。そして、最小値で全てのモンスターの体力を割り、全てのモンスターの体力をその余りに替えます。この余りの最小値を次の最小値とします。この操作を繰り返し、最小値と次の最小値が同じになるか、次の最小値が1となれば操作終了です。
8.ABC058C問題
問題:C – 怪文書
キーワード:文字列、文字カウント、辞書順、char型→int型、int型→char型
複数の文字列が与えられるので、全ての文字列に含まれている文字とその個数で作れる辞書順で最小の文字列を出力せよという問題。
やることは単純です。
まずは、ある文字列の出現する文字とその数を数えます。この時、tmp_alpha[26]という配列にその個数を入れていきます。
char型のaを0と対応させる時、次のようにするとうまくいきます。逆の場合は足せばいいです。
alpha[c - 'a']++;
数え終わったら、alpha[26]という1つ目の文字列で出現した文字とその数を入れた配列と比較し、値が小さくなっている部分はtmp_alpha[]の値に更新します。これを繰り返すと、全ての文字列に出現した文字とその数の最小値が求まります。
その次にこの出現した文字を辞書順に最小な文字列として出力する必要があります。
alpha[26]は0番目にaの数、1番目に1の数・・・を格納しているので、配列の前から取り出していけば勝手に辞書順になります。
あとは、その個数分文字を出さないといけないので、次のように実装しました。
rep(i, 26) ans += string(alpha[i], 'a' + i);
string型で任意回数繰り返す文字列を作る場合は、stringクラスのコンストラクタを用いて
string(回数,繰り返す文字)
と書けます。
ちょっと前に話題になったらしいですが、"文字列"を繰り返す場合、C++だとfor文で書かないといけません。Rubyなら
puts "hoge" * 10
で書けるらしい。便利ですね。(参考:C++での文字列の繰り返し)
9.ARC098C問題
キーワード:一次元、最小値
ある人の方を向いていない人の数を最小化する問題です。
愚直にやるならば、リーダー(向きの中心)となる人を決定して、その場合において向いてない人を全て数え上げるという方法があります。
しかし制約条件を見るとこれはTLEしてしまうことがわかります。
これは、毎回配列を最初から最後まで見るからであるので、そうならないよう工夫します。
まず、一番西を向いていない人を数え上げます。その次に、西から一人ずつリーダーにします。このとき、リーダーになった人が東を向いていたら、最初に数え上げた人の数を1減らします。その次に、リーダーより西にいる人が出た場合は、西を向いている人をカウントします。この2つの値の総和が最小となったときが求める答えになります。