よもやま話β版

よもやま話を書きます。内容はぺらぺら。自由に書く。

はじめてのAtCoder

お世話になっているコミュニティで、競技プログラミングの話題があがった。前から気になっていたので参加させていただいた。(あのぶるさん主催「RailsGirls競プロ同好会」にお邪魔しております!ありがとうございます!)

atcoder.jp

最初に何をやるべきかをまとめてくださったドキュメントをいただいたので(感謝…!)、それに沿って始めてみた。

まず最初に

  • AtCoderにログインした。新規登録しようとしたら、もうアカウントはとってあった。完全に忘れてただけらしい。
  • Ruby書きなので、AtCoderで使われているRuby2.7.1をローカルで利用する準備をした。
  • https://atcoder.jp/posts/37チュートリアル)のページを読んだ。

practice contest

チュートリアルに従い、https://atcoder.jp/contests/practice(A)Welcome to AtCoder を確認する。 すでに解答例が掲載されていた。

# 引用・Rubyでの解答例
# 整数の入力
a = gets.to_i
# スペース区切りの整数の入力
b,c=gets.chomp.split(" ").map(&:to_i);
# 文字列の入力
s = gets.chomp
# 出力
print("#{a+b+c} #{s}\n")

入力が与えられるので、1行分を gets で取ってきて、どうにかこうにかする…というのがテンプレートパターンと考えてよさそうだ。また、最後には改行が必要らしい。一回見ずに実施してみたら、そのあたりでうまくテストが通らずに失敗した。問題の最下部にあるフォームにソースコードを貼って「提出」を押すと、しばらく経ったあとに結果が表示される。

テスト通らずに失敗した感じの記録が残った…。

AC は「Accepted(正答)」、WA は「Wrong Answer(誤答)」の表記とのこと。他にも色々略語があるようで、慣れるまでは用語集を都度参照することになりそうだ。参考: 用語集 - AtCoder Beginner Contest 074

AtCoder Beginners Selection

次に、勉強会参加前に、AtCoder Beginners Selection(https://atcoder.jp/contests/abs)をRubyでちょっとやってみた。以下はログ。

  • PracticeA - Welcome to AtCoder提出) … practiceの問題と同じだった。
  • ABC086A - Product提出)… Rubyには奇数偶数を処理するメソッドがあるので助かる。
  • ABC081A - Placing Marbles提出) …要するに足し算すればよかろうという理解。
  • ABC081B - Shift only提出・AC)…むむっ、やや難しくなってきた…。自分は賢い数学的脳みそは持っていないので強引に突破した。脳筋...? require が使えること、利用しない変数を宣言するのがNGということを把握。あと偶数のところをなぜか"素数"と思い込んでいてめちゃめちゃ失敗した。問題文はよく読もう。コードテストのタブが便利ということを改めて認知した。

ここでちょっと力尽きた。なかなか難しい。

はちゃめちゃ失敗してる(勘違いのせい)

「RailsGirls競プロ同好会」でモブプロ!

夜にdiscordでRubiest5〜6名が集まり、和気藹々とモブプログラミングが実施された。 最初の1問は予習しておいたので大丈夫だったが、あのぶるさんがピックアップしておいてくださった問題が難しくて頭から煙が出るかと思った。問題に対してああだこうだ言いながら解き方を一緒に探していくのがとても楽しかった!みなさんありがとうございました!

1問目(おまけ)

おまけというレベルではなかったが大変面白かった。
049 - Fibonacci Easy (mod 1000000007)

最初にみなさんの話を聞きつつ書きながら考えてみたが、数の大きい入力値でタイムアウトしてしまい、正答ならず。書き途中だったが自分のコードを参加者のみなさんにチェックしてもらうことになった。

n = gets.chomp.to_i
queue = [1, 1]
(n - 3).times do
  queue.push(queue.sum)
  queue.shift
  puts queue.to_s
end

puts "last queue"
puts queue
puts queue.sum
#=> timeout

プリントデバッグ感がすごい。見逃してください。 そしてモブプロ後、参考にして手直しして提出したものが以下↓

VERY_LARGE_PRIME = 10 ** 9 + 7

n = gets.chomp.to_i
queue = [1,1]
(n - 3).times do
  queue.push(queue.sum % VERY_LARGE_PRIME)
  queue.shift
end

puts queue.sum  % VERY_LARGE_PRIME

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/37637324

2問目

メニューがカオスだな、5品しか無いのか、とかのあたりはツッコんではいけない。
B - Five Dishes

まず問題を図にしてみる、ということがとても効果的であることを感じた問題だった。ワイワイする中で、重要ポイント「10分区切りまでが一番遠いメニューを発見すれば勝てる」は早々に見つかったものの、解決のためのアプローチが参加者各自で色んな案が出ていて、プログラミングというのはやはり千差万別、多種多様なんだな〜ということが再実感できて良かった。

ワイワイやりつつ個人的にも書いていて仕上げたのがこちら。

menus = 5.times.map do
  n = gets.chomp.to_i
  { value: n, fill: (10 - (n % 10)).digits[0] }
end
 
puts (menus.sum{|x| x[:value] + x[:fill] } - menus.map{|x| x[:fill] }.max)

提出: https://atcoder.jp/contests/abc123/submissions/37619771

その他、GETした細かい知見

  • a^ba ** b と書ける。完全に失念してた。b.times.map{ a }.inject(:*) とかしてた。
  • 10^9 + 7 (= 1000000007) は良い感じにデカい素数としてよく用いられるらしい。
    • あのぶるさんが書いていた VERY_LARGE_PRIME = 10 ** 9 + 7 すごく良いのでマネさせていただこう… 🙏
  • デカい値はとりあえず小さくできないか考えたほうがいい。タイムアウトとかの原因になりがち。
  • 再帰するより愚直に書いた方が良いことも多そう。めちゃくちゃデカい値が渡されたときに再帰だと stack level too deep に陥ることがある。
  • 競プロにおける「典型的パターン」がいくつかある様子。それを積極的に把握・活用していくのが上達の近道っぽい。※その典型的パターンの習得にそもそも時間がかかるという問題はあるが、それはそれ。
  • 問題文のカオスなところは突っ込んではいけない(例: とある条件のボールを箱に入れると気を失う高橋君

また定期的にあるようなので、時間帯とお仕事状況によるところではあるが、積極的に参加していきたい。引き続きよろしくお願いいたします!

おっと、2022年最後の記事だ。良いお年を〜🎍