ABC090

AtCoder Beginner Contest 090の解説です。

A – Diagonal String

問題

A - Diagonal String
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解説

1行目は1文字目、2行目は2文字目、3行目は3文字目を出力しておわり。

実装

3.times do |i|
  print gets.split("")[i]
end
puts

B – Palindromic Numbers

問題

B - Palindromic Numbers
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解説

AからBの整数について、一つずつ回文数かどうかをチェックしてカウントするだけです。

実装

A,B = gets.chomp.split.map(&:to_i)
ans = 0
A.upto(B) do |i|
  ans+=1 if i.to_s == i.to_s.reverse
end

C – Flip,Flip, and Flip……

問題

C - Flip,Flip, and Flip......
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解説

実際にカードの反転処理をシミュレートして解こうとすると、計算量がO(N^2)になってしまって現実的では無いです。

そのため、計算で解くことにします。

まず基本的な考え方です。最初はカードは表を向いているので、全ての操作を終えた後に「カードを偶数回操作していたら表」「カードを奇数回操作していたら裏」となります。

カードの操作回数 = カードが隣接(上下左右と斜め方向)するカードの枚数+1(自分)

これをカードの場所毎に場合分けして考えると、

・周囲が全て囲まれている場合:9回(奇数)
・四隅:4回(偶数)
・端:6回(偶数)

具体例として5×5のケースのを見てみると、以下のようになります。

偶偶偶偶偶
偶奇奇奇偶
偶奇奇奇偶
偶奇奇奇偶
偶偶偶偶偶

つまり、5x5の場合は、(5 – 2) x (5 – 2) = 9 となります。
よって、NとMが3以上の場合は、(N – 2) x (M – 2)で一般化できます。

これを表にまとめると、以下のようになります。

M
1 2 3≤
N 1 1 0 M-2
2 0 0 0
3≤ N-2 0 (N-2)x(M-2)

あとは、NとMの場合分けで実装・・・ということになるのですが、もっとシンプルにすることが出来ます。

まず、NまたはMが2の場合、(N – 2) x (M – 2) は0になります。
また、N=1かつM=1の場合は、(-1) x (-1) = 1になります。
よってこの場合は一般化した式がそのまま使えます。

残りの「N=1かつMが3以上」と「Nが3以上かつM=1」の場合ですが、これはそのまま一般化した式で計算すると値が負になるのですが、符号を反転させればそれが正解になります。

よって、全てのケースについて、(N – 2) x (M – 2) の絶対値を返すことで結果が得られます。

実装

ほぼワンライナーのようなコードになりました。

n,m=gets.chomp.split.map(&:to_i)
puts ((n-2)*(m-2)).abs

D – Remainder Reminder

問題

D - Remainder Reminder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解説

a mod b が K 以上になるN以下のa、bの組み合わせを数える問題です。

まずKが0の場合はN^2が解となるので、以降はKが1以上の場合で考えます。

bで割った余りなので、まずはbを固定して考えます。

bの取りうる範囲はK+1〜Nです。(理由:bがK以下の場合、絶対に a mod b のはK以上にならないため)

aの取りうる範囲は1〜Nですが、これに対して a mod b は次のような数列になります。

1, 2, … , b-1, 0, 1, 2, … , b-1, 0, .., N mod b

よって、このうちK以上のものの数を数えればよいです。

そしてこれを定数時間で求めることが出来れば、K+1〜Nのbに対してそれぞれ計算して合計をとれば答えになり十分間に合います。

それでは、bを固定した場合のaの数え方について続いて考えます。

前述の数列の 1, 2, …, 0 (長さb)の繰り返しに着目します。この中で、K以上のものは b-K 個です。

そして 1, 2, …, 0 の繰り返しは N/b 個出現します。

また、N/bが割り切れない場合の最後の端数の部分は 1〜N mod bとなり、このうちK以上のものはmax(0, (N mod b)-(K-1)) 個になります。

つまり、bを固定したときのaの組み合わせは、以下の式で求められます。

N/b*(b-K)+max(0, (N%b)-(K-1))

これを各b(K+1〜N)に対して計算して和をとれば解になります。

実装

N,K=gets.chomp.split.map(&:to_i)
ans=0

if K==0
  puts N*N
  exit
end

(K+1).upto(N) do |b|
  ans += N/b*(b-K)
  ans += N%b-(K-1) if N%b-(K-1) > 0
end
puts ans

コメント

タイトルとURLをコピーしました