尺のブログ？

やりたいことをやりたいです

AtCoder Beginner Contest 106

ABC106に参加しました。

A

注意に「道の位置が変わっても…」とあるので、
道の位置を右下に寄せてしまっていいです。
こうすると、面積が(A-1)(B-1)であることが簡単に分かります。

B

200以下には105,135,165,189,195しかないです。
このうちN以下のものの数を調べればいいです。

C

5000兆日もあれば2でもめっちゃ増えます。
よって、K文字目まで全部1なら1、そうでないなら最初に出てきた
1以外の数字が答えになります。
ただ、Kが10の18乗だとK文字目まで調べてる暇はないです。
ここで、制約の（Sの文字数）<=100が活躍します。
つまり、K＞100のときは、必ずSの中で、1でないものがあります。
その1でないものの中で最初に出てくるものが答えです。
実際には、（Sの文字数）＜Kの時も、K文字目までが全部1かどうか
調べるには不具合があります。
ここも解決する楽なやり方としては、
「初めて出てくるSの中の1以外の文字の種類と、それがSの何文字目にあるか」を調べます。
そして、「そもそも1以外の文字が出てこないか、または初めて1以外の文字が出てくるのはK文字目以降」なら1を出力,
そうでないなら最初に出てくる1以外の文字を出力すればいいです。

D

Qは100000以下ですが、Nの2乗もせいぜい250000で、
考えられるpとqの組み合わせは、p＜＝qの条件からその半分と少しになるので、
すべてのpとqの組み合わせについて答えを求めてしまって構いません。
一般のp ,qの組について答えを求める方法を考えましょう。
「p番目以降に始まってq番目までに含まれる列車の数の和」は、
「各i=p,p+1,p+2…qに対してi番目から始まってq番目までに含まれる列車の数の和」です。
さらに、「i番目からq番目までに含まれる列車の数」は、
「各j=i,i+1,i+2…qに対してi番目から始まってj番目に終わる列車の数の和」です。
なので、まず２次元配列dを用意します。
そして、各L,Rに対してd[L][R]を1だけ増やします。
これで、「i番目から始まってj番目に終わる列車の数」が用意できました。
次に、各iに対して、jをiから始めて1ずつ増やしながらd[i][j] = d[i][j-1] + d[i][j]とすると、
「i番目から始まってq番目までに含まれる列車の数の和」が求められます。
次に、各qに対して、iをqから始めて1ずつ減らしながらd[i][q] = d[i+1][q] + d[i][q]とすると、
「p番目から始まってq番目までに含まれる列車の数」が求められます。
あとはQ回d[L][R]を出力すれば終わりです。

AtCoder Beginner Contest 105

ABC105に参加しました。

Ａ

均等に配れるなら０、そうでないなら１です。
実生活でも均等に配れるかわからないときって1枚ずつ配りますよね。
こうすれば均等に配れなくても差は１枚になります。

Ｂ

ある数が作れるなら、それより４大きい数も作れますので、
4で割った各あまりごとに作れる最小の数を探せばいいです。
実際、
あまり０→４
あまり１→２１
あまり２→１４
あまり３→７
が作れる最小の数になります。

よって、作れない数は
あまり０→なし
あまり１→１，５，９，１１，１７
あまり２→２，６，１０
あまり３→３
となります。このときだけNoを出力して、それ以外はYesでいいです。

Ｃ

１０進数を他の進数に直す方法は中学か高校でやったはずです。
それを-2に適用すればいいのですが、
プログラミング言語は負の数の割り算に関して気持ち悪い挙動（オイ）をするので
自分で割り算の方法を書いてやる必要があります。
目的は、Ｎ=P* (-2) + Rとなる整数ＰとＲ＝０or１を見つけることです。

Ｄ

「ｌ番目からｒ番目までの項の和がMの倍数」というのは、
「最初からｒ番目までの和から最初からｌ－１番目までの和を引いたものがMの倍数」、
つまり「最初からｒ番目までの和と最初からｌ－１番目までの和をそれぞれMで割った余りが等しい」ということになります。

数列の第０項を０と解釈して、i項目までの和をMで割った数列Sの各項に、
それぞれの数がいくつあるかを調べればいいです。
M項の配列をつくって、Mの「Sの値」番目の項を＋１すれば、S内に各数がいくつずつあるかわかります。

しかし、Mが大きすぎてM項の配列は確保できません。
解説によれば、ハッシュマップというものを使うといいそうです。
私は知りませんでした。（泣）

AtCoder Beginner Contest 103

ABC103に参加しました。

Ａ

絶対値の差は数直線上の2点間の距離です。
つまり、問題文を読み替えると

数直線上に3点をとる。
好きな点からはじめて、すべての点を一度は通るとき、どのようにすれば最短距離になるか。

という問題です。
当然、端の点からはじめて、中央の点を通って、もう片端の点に向かうときが最短です。
よって、その距離は、与えられた3点のうち最も大きいものと最も小さいものの差になります。

Ｂ

入力例1を見るとよくわかりますが、2回回転したものは、最後から2文字を切り離して、先頭に付けたものです。
ここからちょっと考えると、n回回転したものは、最後からn文字を切り離して先頭に付けたものです。
これをすべてのnについて試せばおしまいです。

Ｃ

それぞれの余りをすべてa-1にできればもちろん最高です。
実は、aたちの最小公倍数から1引いたものをｍとすれば、これが実現できます。
このとき、それぞれの余りはa-1となるので、足し合わせて答えはaの総和-Nです。

Ｄ

DP（？）でやります。
直感的にわかりやすくするため、西を左、東を右とします。
また、橋を取り除くことを「落とす」、取り除かれた状態を「落ちている」とします。
とりあえず、i番目の島までしかないとします。
そして、このときに最小値num(i)本の橋を落とせば、うまくいっているとします。
このとき、bがi以下である要求がすべて満たされています。

i+1番目の島を追加します。
このとき、うまくいっているかどうかを考えます。
まず、ｂがi+1である要求の中で、最も厳しいものは、aが最大であるものです。
このaをbN(i+1)とします。
実際、それが満たされているとしたら、bがi+1であるそれ以外の要求も満たされています。
というのも、i+1番目の島から左に向かってある島に行けないとしたら、その島より左の島にも当然行けないからです。
なので、aが最大である要求だけを考えることにします。
aが最大である要求がすでに満たせていれば橋を落とさなくてもいいし、そうじゃなかったら落とす必要があるので、すでに満たせているかどうかを考えます。
i番目の島までしかなかったときの要求をすべて満たしたとき、最後に落とした橋をlast(i)番目の橋とします。

last(i)がbN(i+1)より小さいなら、橋を落とす必要があります。
このとき、この先のことを考えると、できるだけ右側の橋を落とした方がいい（これは覚えておいてください。この先で何度も使います。）ので、最後に落とした橋はi番目の島とi+1番目の島をつなぐ、i番目の橋となります。つまり、last(i+1) =iとなります。
また、追加で1本橋を落とす必要があったので、num(i+1)=num(i)+1となります。

last(i)がbN(i+1)以上なら、橋を落とす必要はありません。
つまり、last(i+1)=last(i)、num(i+1) =num(i)となります。
でも、これでいいのでしょうか。
というのも、今は落とさなくてもいいけど、この先のことを考えたら落としといたほうがいいんじゃないか、という場合もあるかもしれません。
大丈夫です。その心配はありません。
その理由を説明します。
まず、今やれることは、i番目の橋を落とすことだけで、それ以外のことをするのならi番目の橋を落とした方がいいです。
そして、i番目の橋を落としておくことが今後に与えるメリットは、i+2番目の島を追加してからi+1番目の橋を落とすメリットより小さいです。
だから、わざわざi番目の橋を落としておく意味はありません。

もう一つ疑問があります。
それは、途中までに落とす橋の本数を最小にし続けるのが本当に良いのか、という問題です。
ですが、これも大丈夫です。
なぜなら、できるだけいい状況がどんな状況かを考えると、できるだけ落とした橋の本数が少なく、できるだけ右側の橋が落ちている（落ちている橋の番号の最大値が大きい）状況です。これを考えると、最小値より2本以上橋が多く落ちている状態は無駄です。なぜなら、橋を落とす本数を最小値で済ませて、さらにi番目の橋を落とした方が両方の観点からお得だからです。
同様に、最小値より1本だけ多く橋が落ちている状態も、その一本だけ多く落ちている橋がi番目の橋でないと無駄です。
さらに、先にも書いた通り、わざわざ今必要でないのにi番目の橋を落としておくのも無駄です。
以上から、途中までに落とす橋の本数を最小にすればいいことがわかりました。

num(N)を出力しておしまいです。

最後に、javaのコードを貼っておきます。

abc103.contest.atcoder.jp