こんにちは、しほみんです。
昨日に引き続き競技プログラミングの話をします。
普段はC♯で書いています。競技プログラミングもコンテスト参加し始めて5ヶ月が経ちました。正直大学でアルゴリズムとか勉強したことはなくコンテスト参加しかしてないので成長は遅めだなと思います。回数は十分に参加しているので単純にへたくそなだけです。
なのでまあアルゴリズム初心者の目線で問題の話をできたらなあと思います。
今回はABC143についてお話します。atcoder.jp
ABCとは…
atcoder beginner contestの略で問題は6題あります。問題の名前はA問題、B問題、C問題、D問題、E問題、F問題で、配点は100,200,300,400,500,600となっており、難しいほど得点が高いです。また実装時間は100分です。
またこのコンテストは初心者向けなので最初に参加するにはうってつけです。
後ろのは回数なので今回は143回目になります。
自分はABCDの問題を解くことができて1000点、82分かかりました。
ABC問題まではすぐに解けたのですがやはりD問題がまだまだで鍛錬が必要だなあと思います。
それぞれの問題のコメントをしたいとおもいます。
A問題
カーテンの長さがAのとき、2枚のBの長さのカーテンで覆えるかどうか
覆えない場合はその長さ、覆える場合は-1をこたえる
まあ普通にA-2Bが残るカーテンの長さなのでA-2B≦0なら覆えます。
そのときは-1で、それ以外はA-2Bで出力すればいいです。
B問題
たこ焼きがN個あり、それぞれのおいしさはdi(i = 1 -N)です。
すべてのたこ焼きから2個選んで食べるとおいしさはその二つの積なります。
すべての食べ方のおいしさの総和を求めます。
B問題程度だと計算量を気にしなくていいことが多いので二重ループですべての組み合わせのたこ焼きを選び、その時の積を積み上げればいいです。
（ここで勘違いして1回間違えたのは大きい...）
C問題
長さＮのスライムで同じ文字が連続していると合体して縮小するらしい。
その時の文字数を求めます。
例えばaaaabbbbbcccffdgのスライムは合体するとabcfdgなので6になります。
すごく単純に頭からひとつ後の文字を比較して違った場合はカウントして、同じ場合は無視すればいいです。ただし、最後に数を1足す必要があります。
（理由）
最後の一つ前のとき
異なる文字
〇ab このときaとbを比較してaとbが違うのでカウントしますがbの分がカウントできないです。
同じ場合
〇aa このときaとaを比較して同じなのでカウントしませんがaaの分がカウントできないです。
よって最後に1足します。
D問題
任意の長さの数列から3つの長さを取り出してその三角形ができるかを判定。
すべての組み合わせを考えるが辺の数が10の3乗で全部出しても考えるだけだと10の9乗で計算が制限時間に間に合わない
よってここで3辺をa, b, cとしてa<b<cとすれば
三角形がなるためにはc<a+bだけを判定すればいい。
さらにソートして大きい順に並べて、c,bを固定すればaがどこまで満たすかを調べ、満たさなくなったらbを減らすようにしていけばいい。（この工夫でなんとか計算量を半分に抑えてクリアできる）
E問題
方針は決まったけどどうやって最短距離を出すかがわからず断念。
後々調べるとワーシャルフロイド法で求まるらしい。計算量もNの3乗でN=200が上限なので間に合う。
まずは問題の条件を無向グラフという行列にして表現する。
（例えば町1と町2の距離が3なら行列（1,2) = (2,1) = 3を入れる）
このあとこの行列にワーシャルフロイド法を使う。
この配列に対して新たに車がその町に到達できるかどうかの無向グラフを作る。
到達できるなら1。できないならInfを入れる。
これにもう一度ワーシャルフロイド法を適応。
あとは条件にそってこのグラフから取り出すだけ。
（ワーシャルフロイド法は動的計画法の一種らしい）
F問題
分からない。まだこの問題を解く段階でもないのでスルー（難しいしわからん）
自分が書いたコードはこんな感じです。
次の記事で落としておきます。
競技プログラミングは奥が深いなあと思います。
もっと簡単にコード書きたいよな...
ではでは
