競技プログラミング」カテゴリーアーカイブ

AtCoder Beginner Contest 124に参加してみました録

 1週間前のABC123に引き続きAtCoder Beginner Contest 124にも参加してみました!!

 この競技プログラミングコンテストは4問出題され、難易度順にA問題、B問題、C問題、D問題とある内の今回はA,B,C問題を答えることができました。

 前回から、とりあえずABCの過去問にあたってみたところ、D問題はまずよく分からなくて、C問題も解けるか解けないか、まあ大体解けないんですけど、みたいな感じでありました。

 して今回の目標はC問題を時間までにどうにか解くという感じなので今回のはいやあ、良かったです。

 とりあえず次の目標はD問題か…あ…むず…できない…ああ、ああ、

 …ということで今回の問題を解いた時の感想をば。

A問題

atcoder.jp/contests/abc124/tasks/abc124_a

 とりあえず入力例出力例を追ってみることにしてみました。まずこんな図を書いて、なんだ(A,Bのうち大きい方)+(それ-1)じゃないかと思ったんですが、

 A=Bの時だけ(A,Bの大きい方)×2になるということで、その時だけ場合分けしました。

B問題

atcoder.jp/contests/abc124/tasks/abc124_b

 とりあえずH1の旅館からは必ずSEAが見えるということで、まず出力k=1とかしておいて、あとはHnがH1~Hn-1以上かどうか調べてみて、そうだったらその都度k++;するプログラムを、勘違いとかコンパイルエラーとか無いように(当然これは重要)、頑張って書くという感じでやってみました。

C問題

atcoder.jp/contests/abc124/tasks/abc124_c

 1と0が隣り合わないようにするということで、結局のところ0から始まる0101010101…という数列か、1から始まる1010101010…という数列のどちらかにするしかありません。じゃあどっちにしたらより少ない変更回数でできるかという問題になります。

 10101010…にするには奇数番目の0を1に、偶数番目の1を0にしなくてはならず、変更回数は

 (奇数番目の0の個数)+(偶数番目の1の個数)

 であり一方、0101010101…にするには奇数番目の1を0に、偶数番目の0を1にしなくてはならないので変更回数は

 (奇数番目の1の個数)+(偶数番目の0の個数)

 ということになります。よって上の2つの式のうち小さい方が答えという気がしたのでそうしてみました。

D問題

atcoder.jp/contests/abc124/tasks/abc124_d

 

 今回はC問題まで解けた所で時間がまだあったのでD問題も考えてみたのですが、まず0と1の連続する個数を記録する配列を作っていろいろ場合分けしたらまあできなくはないんじゃないかと思ったんですが、残念ながら文字列の扱いが難しくまずその配列が作れずという感じでした。うーむ勉強しないと…ああ…。

終わりに

 とりあえずC問題と戦えるようにはなったので、次はD問題もちょくちょく触っていけたら…難しい…ああ…と思います。

 なんか難しい問題の典型パターンみたいな技を全然しらないこと、まだプログラムを書きなれてない感じもあるのでまだ上達する余地はあるかなーということで頑張れたらいいなと思います。

今回のレート変化 : 17 → 98

AtCoderの筆者マイページ:

atcoder.jp/users/aoiatuage

AtCoder Beginner Contest 123に参加してみました録

 競技プログラミングというのに初めて参加してみたので感想を記しておきます。楽しかった!

 とは言っても、全4問中簡単と思われる前半2問しか解けなかったんですが、それでも、楽しかった! 

 自分はそもそもプログラミングというものについて、大分前にC言語のやつをポインタの話が出てくる前あたりまでの話を聞いた程度の存在でありました。補足コーナーで、ポインタって数字を入れ替えるのに使うんだーへー面倒なんですねいろいろ・・・みたいな感じでした。

 しかしこの度競技プログラミングというものを知り、いかにもパズルみたいなやつで楽しいのかなと思って一念発起、勉強してみたという次第であります。

 少しググってみたらなんかC++というのが競技プログラミングでは実質的な標準的な言語らしい?という情報を得たのでC言語を勉強してからC++言語を勉強してみました。いや、難しい・・・。

 してよく分からないまま入門書を読み終わったことにして来たるべき4月7日、どうやら始めたての人に良いコンテストがあるという事で、いや、ポインタとか、クラスとか、継承とか、コンストラクターとか、全然わかってないんですけど、参加することに相成ったわけでございます。

 そんなこんなで、あれ、cin >> a;だっけcin << a;だっけとか言いながら今回の問題を解いてみた感想をば。

A問題

 基準値と5つの整数値が与えられて、5つの整数値のなかで最大のやつと最小のやつの差が基準値よりでかいかどうか考えてくださいという問題でありました。

 とりあえず与えられる整数が6つあるということなので6つの配列を作って、5つの整数値のうち全通り引き算を実行し、その差のなかから最大のやつをとってきて基準値と比べればいいやという事でやってみました。

 引き算が負になる場合を考えてなかったので何度か間違いながらもどうにか提出しました。

 しかし、後になって見返してみたら5つの整数値の条件として問題文に 

 a<b<c<d<e

 とありましてね。

 思えば子供のころから問題文をきちんと読まないで読み落としてきた人生でした…。ああ…。全部引き算をしなくてもe-aをしとけばすぐ解ける…ああ…。

ああ…。

B問題

 5つの、出てくるまでの時間が決まってくる料理、を注文するんですけどどういう順番で頼めば一番時間が短くて済むか、という問題でした。

 問題の前提として重要な点は10n分にしか料理が頼めないということで、結局のところ最後の料理以外はかかる時間分の一の位を切り上げた分かかるということなので、最後の料理を頼んで出てくるまでの時間のところを考えさえすれば良いだけということでした。

 というわけでとりあえず5つの料理をa[5]みたいな配列、それぞれのかかる時間の1の位を切り上げた数をb[5]に入れておいて、b[5]の総和sを計算しておいてからfor文でs-b[i]+a[i]のうち最小のやつを見つけるだけでよかったので分かりやすい問題でした。

C問題

 人数と、6つの街の間の5つの交通手段で輸送できる最大人数が与えられて全員が目的地に移動するまでにかかる最小時間を求める問題でした。

 よく分からなかったので紙に書いているうちに結局のところ一番人数が運べないところが全体で何分かかるかということを見抜けたまでは良いのですが、なんと一番人数を運べない輸送手段を割り出すことができなくて、ああ、とけてない、ああ…。

ああ…。

D問題

 見る時間が・・・!無かった・・・!

まとめ

 そういうわけで初参加となったコンテストでしたが、100点とか200点の問題が身構えていたよりは簡単だったこと、そして自分は問題文をよく読まなければならないことを再確認できてよかったと思います。何より楽しかったのが一番良かったでした。

 次回は一週間後にABC124があるらしいので参加したいと思います~

 少しは過去問とかで勉強しようかな…。1週間後か…。

レート:0 → 17