競プロ

ATCODER に登録したら解くべき精選過去問 10 問をC++初心者が解く 競プロ#1

こんにちは、チズチズです!

昨日はAtCoderで競プロ大会がありました。

2完でレートが上がりました。

僕の今のスキル

競プロに関してはまだ入門者です。

  • Pythonでしか実装できない
  • 再帰の発想が中々出来ない
  • Python使ってるからTEよく出る

Pythonでしか競プロやってないんですが、もうそろそろさすがにC++出来るようになりたいと思います。

C++難しいですが実行速いし大会だとC++限定あるから覚えたいです。

まだ茶色コーダーです。緑目指してます。

ATCODER に登録したら解くべき精選過去問 10 問

AtCoder Beginners Selection

これらの問題は競プロ入門者向けの問題です。

10問あるのでやっていきます。初めてやるので内容はよくわかりませんが、徐々に難易度が上がるものと思います。

今回のルール(自分用

  • Pythonを使わずにC++のみで実装
  • 初めはサンプルや解説見ずに自力で解く
  • 終わったら復習コード書く

こんなルールを設けました。では早速やってみます。

はじめてのアットコーダー

このような入力がされるので、a + b + cとsを出力して下さい。 という問題です。

1回目のエラー:数字と文字の間に空白がなかった → ” “を挟んだ

2回目のエラー:sが1文字しか入っていない → char型は1文字だけどstringにしたら全部入った

初歩的なミスでしたが、何とかAC取りました。

Product

2つの数字が入力され、積が偶数なら”even” 奇数なら”odd”を出力。

普通にabの積が2で割り切れるかどうかを判定させれば出来ます。

1回目のエラー:全てエラー even oddだった → スペルミス Even Odd に修正

ただ表示させるだけなら{}付けなくてもいいらしいです。

これでも動きました。

Placing Marbles

3つ並んで入力されます。1か0が書いてあって1の数の合計を取得させなさい。という問題です。

エラー s[i] == “1” → ’1’にしたら直った

C++では”と’が区別される!(初耳

  • 文字列(2文字以上)は”(ダブルクオーテーション
  • 文字(1文字)は”(シングルクォーテーション

Pythonはどちらでも構わないため、”で統一していたらエラーが出ました。

scanf()で数字として取得したら和を出力すれば終わるっていうコード書いてる人がいて確かにと思いました。

1の数=和 ですよね……

Shift only

A1~ANまでの数が最小で何回2で割り切れるかというものです。

こちらはエラーがありませんでした。

奇数か判定させてから2で割る という処理がキチンとできていれば通りそうです。

Coins

500円玉A枚

100円玉B枚

50円玉C枚

X円の支払いに何通りの支払い方法があるか(上の硬貨の枚数で

全探索ではなく2分の1探索になりました。

後は500未満だったら500の探索はさせないとか書けそうですが面倒だったので辞めました。

時間だけで言うと全探索と変わりませんでした。C++は高速です…

Some Sums

1以上N以下の整数について各桁の和がA以上B以下のものはいくつあるか。

全探索でゴリゴリと各桁の和を計算させてifでカウントさせました。

和を計算するのにどうしようかなと思いましたが、普通にwhile回せば大丈夫でした。

Card Game for Two

大きい数から2人で取っていって最終的に2人の取った数の和の差を求める問題です。

逆ソートで偶数番目と奇数番目の総和出して最後に差出せば完了です。

Kagami Mochi

dの中に違う値がいくつあるかという問題です。(要約しまくり

size()が便利

要素数を取得してくれます。本当便利

Otoshidama

1万円札、5千円札、千円札の枚数がN枚でY円になったらその枚数、ならなかったら全部-1を表示させてください。

さすがに全探索は厳しいですw

時間の計算は面倒なのでやりませんが、工夫で減らします。

a,b,cの和は必ず9だからaとbを決めておけば必然的にcが決まるため、二重ループでおkです。

フラグを立てておいて、条件成立したらループを抜けてもらいます。(

こっちもそこまで苦労はしませんでした。

白昼夢 / Daydream

“dream”, “dreamer”, “erase”, “eraser”を組み合わせて作れる文字列かどうかを判定します。

考えましたが、、、 C++での実装が思いつきませんでした。実装できませんでした!

解けませんでした!(言い訳:Pythonではできる

しかし、C++には便利な関数があるらしいです。それを使って見ます。

regexを使うと瞬殺できるそうです。

Traveling

tiのときにxiとyiにいるという条件が成立するかどうか…です

Pythonだったとしてもわかりません。方法が思い付きませんでした。

tが奇数ならx+yは必ず偶数になるから…

加えて、1回で1マスしか移動できないからx+yがtを超えてもおかしいよっていう感じで出来ますね。

気付いたら簡単そうでした。

まとめ

C++やっぱ爆速!

全探索でも速いです。C++

最初の方の問題はPythonで早く解いて後半のめっちゃ再帰する問題はC++で解けるようになりたいですね。

まだ別解を見ていないので、色んな解き方を見てみたいです。

DPとかやったことないのでやってみたいです。

参考にした記事

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~

AtCoder に登録したら解くべき精選過去問 10 問を別解で解いてみた

お読みいただいてありがとうございました。

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です