おはようございます。しほみんです。
今日は、競技プログラミングについてお話しします。年始二回目のABC151についてです。一応初心者として初心者なりに考えていることを共有するために更新しているので、プログラムについて考えたい人はぜひ読んでみてください。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは700目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約25回参加、7か月。
・目標はD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回はC問題まで解いて、Dも実装時間が足りずって感じでした。C問題も戸惑ってしまったので結局1時間ぐらいかかり、パフォーマンスも614で、前より若干レートが下がってしまいました（682→675)。
D問題も方法は思いついたのですが、実装できずに終わってしまいました。ゆっくり見直して考えたいなと思います。
早速問題に移っていきます。話もコードもD問題まで載せます。
A問題
アルファベットz以外を考えます。
アルファベット順で次のものを出してください、
例）a→b,o→q
これは一度char型をint型にします。すると文字は数値になります。
この数値は基本アルファベット順に並んでいます。aがある数値になるなら、bはある数値+1です。
よって、int型で1足してchar型に戻してあげればよいです。
B問題
ある人には目標の平均点があります。最後の1教科以外は返却済みです。最後の１科目が何点以上であれば、満たすか答えてください。不可能なら-1を出力します。
最後の1教科以外の点数の総和をsumとします。n教科で平均点をm点以上とすると、
あと１科目はm*n-sum以上であればよいです。
ただし、この値が最高点を超えたら不可能、この値がマイナスなら0点でよいので、そこに注意して分岐します。
C問題
競プロをもしたやつです。いろんな問題を提出してAC,WAがあるので、その情報をもとにAC数とWA数を出します。
基本的には頭から判定しますが、注意するべきなのはACしていない問題のWAの数はカウントされないことです。よって、それぞれの問題でACとWAの数を数えて置いて、あとでACした問題のみWAの数をカウントする工夫が必要です。
また、一度ACするとそれ以降の判定は関係ないのでそこはcontinue文を使って判定を飛ばせばよいです。
ちょっとどよめいた問題らしいですが、ちゃんと問題文を理解して解きたいものです。
D問題
迷路が与えられます。この迷路の最大経路数を求めてください。
いろんな方法が考えられますが、自分はワーシャルフロイド法を選択しました。N=20しかないので、Nの3乗時間かかっても解くことが可能だからです。
ただ、ワーシャルフロイド法を実装するのに勘違いして時間内に解けませんでした。
というか普通に迷路の入力形式を勘違いしていたので終わってしまいました。
よく問題は読みましょうって感じでした。
ワーシャルフロイド法はすべてのありうる経路にそれぞれコストを代入して、それに対して、全部の途中の経路を介したとき最小となる経路はどこかを出して更新します。つまり、ある2点を行くのに最小の経路数を出します。このうち一番大きいものを選べば、答えです。
ワーシャルフロイド法を使うためにいくつかコードを工夫したので詳しくはコードを見てください。
最後に...
最近は最初から解けないってより、解法はわかってもうまく実装できていないってことが増えてきました。アルゴリズム自体は少し理解を進めた一方、実装力が足りないなって感じです。問題をやっていくことでだんだんいろいろ理解できている気はするので、ちゃんと解くをもっと強めたいです。プログラミングに興味があるならまずはA,B問題を解いていく形でスタートするといい気がします。ではでは。
