おはようございます。しほみんです。
ABC168に参加しました。前回に引き続きよい感じで問題を解けましたね。ただ、E問題の壁は厚いなあと思いますね。この難易度ジャンプを超えられないと水色はきつそうです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在48回参加、ほぼ1年。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABCD、55分でした。パフォーマンスは1144で、緑後半でした。レートも818→855で、緑維持です。地味にパフォーマンスが3回連続1000超えたのでこのペースを維持したいですね。
ミスをしなくなったのがよかったです。もうちょっとD問題早く解きたい。E問題は方針自体はある程度考えられましたが実装までは至らず...ここは壁が大きいなって感じますね。
今回はD問題まで振り返ります。今回から実装例は省こうかなと思います。思考の過程をメインに置きます。詳しくはコードの方が分かると思うので...コメントもついてるし。
A問題
日本語で鉛筆を数えるときの「本」
下一桁によって読み方が違います。
数字Nが与えられるので、以下のように出力してください。
Nの下一桁が
・2,4,5,7,9のときはhon
・0,1,6,8のときはpon
・3のときはbon
まあ普通に下一桁の数を出して、その数に応じて場合分けすればよいだけです。
工夫できることは
・Nをstring型で読んで、一番最後の文字をint型で出力。
→string sとすると、s[s.Length -1] - '0'とすると下一桁を出せます。
・if文でbonとponを出して、honはelseで出す。
→条件分岐は少ない条件を書いた方がコード量が減ります。
B問題
英小文字からなるSがあります。
Sの長さがK以下であれば、Sをそのまま出力します。
それ以外では、SのK文字目まで出して、それに...を追加してください。
まあ、K文字目までを知りたい。その続きあるか見たいってときに考えるやつですね。
sをstring型で読み込ませれば、s.Lengthが長さです。
よって、s.LengthがK以下かそれ以外かで判定すればよいのです。
s.LengthのK番目までを出力するのには
・s.SubString(0,K)を使う
・K回forループを回して、s[i]で出していく
が考えられます。
工夫できるところとしては、
・K以下であることを例外条件としてif文で取り出してreturn;で終わらせると
elseを書かずに楽かもしれません。（人による）
C問題
時針、分針がA,Bセンチの時計があります。
このときH時M分で、2つの針の先端は何センチ離れていますか
方針はどっちかだと思います。
・時針と分針で基本的に三角形ができます。
2つの辺とそのなす角度が分かります。
よって、余弦定理を使えばよいのです。ググれば一発です。（三平方の定理のイメージがあればすぐ出るかと）
・時計の中心を(0,0)として座標設定し、時針と分針の先端の座標を求めます。
2つの座標の距離から求めます。
人によると思いますが、自分は前者が楽だったのでそれで求めます。
工夫する点としては、
・0時0分を基準として、分針と時針の角度をそれぞれ求める。その差を適応する。
ところですかね。面倒な角度も基準を決めれば余裕です。
あとは2π=360°に注意して、角度を出します。
分針は1分で6°進むので、M/60×2π
時針は1時間で30°進み、1分で0.5°進むので、(H/12+M/720)×2π
あとは余弦定理で完成です。
D問題
洞窟にはN個の部屋とM個の通路があります。
それぞれ部屋1からN，通路1からMの番号が付いています。通路Miは部屋NiとNj（i≠j)がつながっています。
部屋1は入口の入り口がある特別な部屋です。
洞窟内は暗いのでそれぞれ各部屋に道しるべを置くことにしました。
その道しるべはその部屋と通路でつながっている部屋を示します。
洞窟内は危険なので部屋1以外の部屋で以下の条件を満たす必要があります。
・その部屋を出発して道しるべを通じて部屋1に戻ることができる。
これが達成できるか判定して達成できるならその配置を出力してください。
まず問題文が長い....普通にわかりづらい.....
ですが、根気強く読んでいくと以下のことが分かります。
・部屋は必ずどこかとつながっている。
ということで、絶対、いろんな部屋を経由して1とつながっているわけです。
そうすると道がある限り必ずすべての部屋から脱出できます。（Noを出す必要がないので重要）
あとは道しるべをどう置くかですが、部屋1から幅優先検索（BFS)をすればよいのです。
つまり、1につながっているすべての部屋を1に戻るようにする。
次にそのつながった部屋につながっているすでに決定済み(1と1につながっているすべての部屋）の部屋以外はその部屋につなぐ。
これを繰り返せばよいのです。
ここで根付き木で根を1とした木から判別していけばよいのです。
根付き木ってどう実装するか悩むのですが、C#では
List<int>[] tree = new List<int>[n];
として、配列内にList型を使えるようにすると見通しがよいかなと思います。
つまり、tree[i]はi+1を親としている子のノードが入ります。
注意点はこのtree[i]はまだ宣言していないので、
for文とかでtree[i] = new Lisnt<int>();と宣言が必要なところです。
あとは、今回無向グラフなので、1以外はどっちが親か子かわからないです。
なので、双方に入れて、先に判定した場合はその後判定しないようにすればよいのです。
まとめると、
1. BFSをおこなうためのtreeを準備（インスタンスの作成）
2. treeに双方を入力する。
3. tree[0]からBFS、答えの数字は別に配列として保持。このとき、すでに答えが入っている場合はその組み合わせは省くようにする。
4.答えの数列を出力。
ちなみにBFSですが、Queueを使うと便利です。Queueの中に入った数はすべて同じ深さという前提で処理するとよいです。
詳しくはコードを見てください。
最後に....
真面目に考え方書くとやっぱり長いですね....分けて書こうかしら....
ではでは。
