こんばんは、しほみんです。
今日は競技プログラミングについて久々に話します。実はこの前にABC147もやったのですが、C問題でビット探索を使うことを知らなかったのでまともに解けませんでした。そのため、ちょっとABC147については飛ばすことにしました。ただ、きちんと見直して今後には生かしたいのでいつかまとめるかもしれません。
前置きが長くなりましたが今日は昨日行われたABC148について話したいと思います。今回はぶっちゃけかなり簡単で取り組みやすかったです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは700目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約25回参加、7か月。
・目標はD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回は取り組みやすかったので、ABCDEと5完でき、時間も約50分でした。パフォーマンスも1127と実は過去最高です。まあ水色パフォでもう一歩だったので今度はとりたいなって思います。スコアは583→654と大幅に向上です。ここまでうまく解けると楽しいですね。もっと早く解きたいとは思いましたが....
解説というか話は今回Fまでしようかなと思います。正直Fは木の問題で自分がなじみなくて苦しいので概念だけ理解したって感じです。コードはEまでを公開します。
AからEまでほとんど複雑なことを考えずに、素直に考えると解けたので、コードもかなり素直にまとめられたなって感じます。本来のAtcoderに触れられたなって思います。
ここから以下ネタバレです。
A問題
1,2,3の三択問題の正解を選ぶ問題です。A,Bで間違った選択肢が与えられるので、正解を導き出します。
例えばA=1,B=2なら正しい答えは3です。
これはいくつか考えられますが、自分はA+Bの和から答えを出すようにしました。
つまり、A+B=3なら答えは3、A+B=4なら答えは2、A+B=5なら答えは1です。
なぜ、AとBそれぞれで判定しないかというと、コードが長くなるからです。
たとえば、A=1,B=2とA=2,B=1は答はおなじ3ですが、AとBでそれぞれ判定すると二つのifが必要なので厄介です。
むしろ答えが同じならA+Bで考えてしまえばいいってなります。
ちなみに実際の解答例は6-A-Bで、確かにこれなら1行でとても良いです。
B問題
2つの文字列が与えられます。
それぞれの1文字目から1文字ずつ取り出して並べます。
たとえば、 3文字列でabcとdefならadbecfと並べます。
もう素直に2つの文字列を読み込んで、それぞれ頭からchar型で取り出していけばいいです。C#だとcharからstringへ再構成するのは結構面倒なのでcharでConsole.Writeしましょう。
Writeだと改行しないで書きだします。一方、WriteLineだと書き出したら改行します。
C問題
参加者はA人またはB人です。このときお菓子を配ろうとしますがちょうど配り切りたいです。このとき、最小で何個必要ですか？
もう素直にAとBの最小公倍数を求めます。
最小公倍数はa×bを最大公約数で割った数です。ここで最大公約数はユークリッドの互除法で出ます。これはプログラムとして確立しているのでコードを参照ください。
D問題
N個の数列が与えられます。その数列はいくつか消すことができて、最終的には、1,2,3...と小さい数からならべられれば良いです。それをよい数列として出力します。一方それができないなら悪い数列として-1を出力します。
まあ、残った数列はたかが1からans(ansは答）までの数列です。
よって、頭から1,2,3と数えていって、並べて行ける数だけやればいいです。いわゆる貪欲法で解けます。
並べられた数以外を壊せば実現できるので、答えはN-ansです。
E問題
f(N)= 1(N=0,1のとき）、f(N)=N×f(N-2)(N >= 2のとき）で成り立つf(N)があります。
このf(N)は0が何個続くか求める問題です。
まず問題を少し深堀します。下に続く0は要するに10を何回かけたかです。
10は2×5なので2の因数と5の因数が出てきた回数で最小の方です。
今回はNとN-2なので偶奇で場合分けできます。
奇数の場合、
因数に2も5も出ないので、答えは0です。
偶数の場合、
2の方が5より因数として出てくる回数は多いので、5が出てくる回数を求めればよいです。
因数は常に偶数であるので2×5をまず出る回数を探します。
これはN/10で出てきます。
次に、2×5×5を考えてみます。先ほどの2×5では5が1回だけカウントされています。つまり2×5×5の2回目の5はカウントされていません。よってN/50で割った数はさらに5の因数をカウントできます。
次も同様です。2×5×5×5を考えたとき、2×5×5までは数えたのでもう一つの5を数えます。
つまり、10,50,250,1250と割った数を単純に足していけばいいです。途中で割る数がNより大きくなったらそれ以降はないのでそこでwhile文を形成します。
F問題
うわさの木の問題です。
木の問題ってそもそも取り掛かりが不明すぎてあんまりうまく解けないです。
問題も厄介ですが要するに鬼ごっこで鬼が捕まえるのに必要な手はいくつかを求める問題です。
鬼が最初にいる位置を根として、逃げる人が鬼に捕まる前に最初にいる位置から移動できる葉の位置を全部出します。その一番遠いところが答えです。
やり方は深さ優先探索でできるみたいです。自分がまるで分らんのであれですが勉強してできるようになりたいです。
今回はアルゴリズム要素が少し薄いかもしれませんが、きちんと考察してとれたのは大きいです。今後も続けていきたいです。ではでは。
