yakataの情報奮闘記

プログラミングの話をします

ABC100で初めて全問通した話

AtCoder Beginner Contest 100 - AtCoderのリンク

 

タイトルの通りです。ABC099 C問題(chokudaiさんとかが難しいとツイートしていたDPを使って解くやつ)の解き方というか、コンピュータリソースの使い方を見てからワンランク上がった気がします。

※以下のコードはすべてRubyコードです。表示バグってます。直し方教えてください……。

 

目次

 

A問題について

入力フォーマットの誤植(※修正済み)と出力が変わり種になっていて、引っかかりました。

 

考え方

隣り合うケーキを取っては行けない→1人が最大個取るには交互に8個取るのが最善→2人とも最大8個取ることは可能

 

実装

  1. a,b = gets.chomp.split.map(&:to_i)
  2. if a<=8 && b<=8
  3. puts "Yay!"
  4. else
  5. puts ":("
  6. end


B問題について

考え方

100で0回割り切れる100番目の数は100じゃなくて101だよ

※サーバーが重かったのもあってここで間違えた答え出すとロスが厳しかったようですね。

実装

  1. d,n = gets.chomp.split.map(&:to_i)
  2.  
  3. if n != 100
  4. puts n*(100**d)
  5. else
  6. puts 101*(100**d)
  7. end

 

C問題について

考え方

最終的な出力が回数なので3倍する話は無視でいい

結局aiは何回2で割れるのかということを実装すればOK

 

実装

  1. _ = gets.chomp.to_i
  2. ary = gets.chomp.split.map(&:to_i)
  3. count = 0
  4.  
  5. ary.each do |ai|
  6. quot = ai/2
  7. remainder = ai%2
  8. while remainder == 0 && quot!=0
  9. count += 1
  10. remainder = quot%2
  11. quot /= 2
  12. end
  13. end
  14.  
  15. puts count


 

D問題について

最初絶対値で評価するのを見逃していてとんちんかんな実装をしていた。

考え方

合計の絶対値の和で比較

→-をつけるかつけないかだけ(最大値比較なので、-になったら無視される)

→綺麗さ・美味しさ・人気度の3つの項目において+-の組み合わせ(2^3通り)全てで調べる

 

試行が定数倍増えても気にしないのがコンピュータのいいところ。

実装

  1. n,m = gets.chomp.split.map(&:to_i)
  2. ary =
  3. n.times do
  4. # ary[0][2]→z1
  5. ary << gets.chomp.split.map(&:to_i)
  6. end
  7. ans = 0
  8.  
  9. # +-の組み合わせで8通り試す
  10. plmi=[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
  11. plmi.each do |i|
  12. eva =
  13. ary.each do |xyz|
  14. eva << (xyz[0]**1
  15. end
  16. # 降順ソート
  17. eva.sort! {|a, b| b <=> a }
  18. tmp_ans = 0
  19. m.times do |i|
  20. tmp_ans += eva[i]
  21. end
  22. ans = [ans,tmp_ans].max
  23. end
  24.  
  25. puts ans

+-全通り調べるために配列手書きしているところとeva(評価evaluation)の代入がほとんど繰り返しなのはリファクタリングしたほうがいい。ただ、ネストが深くなりそう。

 

まとめ

このABC100で茶色になれました

パフォーマンス1576なので、毎回これくらいの成績を取ると水色だよってことですね。

ただ、今回のような実装は簡単、思いつくのが少し大変というものは比較的得意なのですが、

前回のC問題のような一目見てDP問題だとわかってからが勝負みたいな、実装に対する知識?場数?が要求されるものだとまだまだ厳しいです。

*1:-1)**i[0])+xyz[1]*((-1)**i[1])+xyz[2]*((-1)**i[2]