Codeforces Round964(Div.4) A,C,D,E,G1,G2非公式日本語解説
日本時間2024年8月6日23:35より行われたCodeforces964(Div.4クラス)の
日本語解説(もちろん非公式)です。
https://codeforces.com/contest/1999
なお、B問題、F問題については解けていないので、今回はスキップしています。ご了承ください。
それぞれの問題は、問題紹介→解法→提出コード（→補足）の順に記載しております。
A問題 A+B Again?
問題
2桁の正整数 n が与えられます。10の位と1の位の数字を足し合わせた和を求めてください。
t 個のテストケースが与えられます。それぞれについて答えてください。
制約
1 <= t <= 90
10 <= n <= 90
入力例
2
77
21
出力例
14
3
解法
やるだけといえばやるだけですが、どうやるかはひと工夫必要かも。
簡単な方法のひとつは、受け取った n に対して
「10で割った余り（=1の位）」と「10で割った商（=10の位）」を求めて
足し合わせる方法かと思います。
各位を直接足し合わせようとするのは案外厄介なイメージ。
提出コード
C++（本番での提出）
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<n; ++i)
using namespace std;
int main(){
int n;
cin >> n;
rep(i,n){
int a;
cin >> a;
cout << a%10 + a/10 << endl;
}
}なんとなくの癖で、テストケース数 t を n 、各入力を a として受け取ってしまっています。
Python（後で書いたやつ）
こちらは問題文に合わせた変数名としています。
t = int(input())
for _ in range(t):
n = int(input())
print(n%10 + n//10)補足
ちなみにですが、もしも、それぞれの入力が2桁の正整数ではなく、
t 桁以下の任意の桁の正整数だったらどうすればいいでしょうか。
たとえば「9147147」の桁の総和を求めよ。と言われた場合です。
この場合には、「nが0でない間、nを10で割った余りを答えに足して、
nを10で割っていく」という方法が有効です。
Pythonコード
t = int(input())
for _ in range(t):
n = int(input())
ans = 0
while n:
ans += n%10
n //= 10
print(ans)イメージとしては、いちばん小さい位の数字(右端の数字)を
順番に足していく感じです。
これなら、桁数がかなり大きくなっても（おおよそ10の7乗～
10の8乗程度の桁数（n = 10^(10**8)ってこと）までなら）対応可能です。
C問題 Showering
問題
コンピュータ学徒のアレックスは、大変難しい問題に直面しています——それはシャワーを浴びることです。毎日頑張っていますが、時間があまりにもありません。
彼は s 分間シャワーを浴びます。
しかし、ある日には家に帰ってからの時間が m 分しかないこともありました。
さて、彼はある日、タスクを n 個抱えていました。
i番目のタスクは区間(Li, Ri)として表現され、
それは彼が時間 Li から時間 Ri までをそのタスクに費やすということです。
複数のタスクを同時に行うことはありません。すなわち、複数のタスクの区間が重なっていることはありません。
さて、この日のアレックスはシャワーに入る時間を取ることはできますか？
すなわち、この日のアレックスにはタスクのない自由時間が s 分間ありますか？
"Yes"ないし"No"で答えてください。
t 個のケースが与えられます。それぞれについて答えてください。
制約
1 <= t <= 10^4 (テストケースの数)
1 <= n <= 2 * 10^5 (タスクの数)
1 <= s <= 10^9 (シャワーに要す時間)
1 <= m <= 10^9 (その日の自由時間)
0 <= Li < Ri <= m (Li、Riは i 番目のタスクの開始時刻、終了時刻)
ただし、すべてのケースにおけるnの総和は2*10^5未満である。
また、1以上の i 番目のタスクについて、L(i) > R(i-1)である。
入力例
1
3 3 10
3 5
6 8
9 10
出力例
Yes
（時刻0-3の間にシャワーに入れます。）
解法
愚直な考え方として、シャワーに入り始める時間を順番に決め打ち、そこからs分間にタスクが存在するかを0からmまですべて調べるような方法があります。しかしこれでは実行時間に間に合いません。
なぜなら、時間の候補はm個、すなわち10^9個程度ありますが、これはコンピュータが数秒で実行できる10^8回程度の計算回数を超えてしまっているからです。
制約を見てみると、時間に関する制約は s (シャワーの時間)と m (自由時間)ですが、いずれも10^9となっています。ここからのアプローチは難しそうです。
逆に、それぞれの日のタスクの個数は小さい値ですので、こちらからアプローチしてみることにします。
さて、それぞれのタスクは連続した時間で行われます。つまり、タスクをやっている間にシャワーに入ることは絶対にできません。
裏を返せば、シャワーに入ることのできる可能性のある時間は、タスクとタスクの間か、あるいは家に帰ってから最初のタスクを始めるまでの間か、すべてのタスクを終えてから自由時間が終了するまでの間、このいずれかにしかないということになります。
この可能性のある時間のかたまりの数は、タスクの数+1個程度しかありません。すなわち、最大でもn = 2 * 10^5程度です。これならそのすべてをチェックしても間に合いそうです。
それぞれのタスクについて、1つ前のタスクの終わりの時刻と、今のタスクの始まりの時刻の間が s 分間以上あるなら、そこでシャワーに入ればよいです。そういう区間が1つでもあるなら答えはYes、どこにもなければNoです。
時間計算量は各ケースO(n)程度、制約よりnの総和が十分小さいので、
実行時間制限には間に合います。
提出コード
q = int(input())
for _ in range(q):
n,s,m = map(int, input().split())
p = [[0,0]]
for i in range(n):
u,v = map(int, input().split())
p.append([u,v])
p.append([m,m])
ok = False
for i in range(1,len(p)):
if p[i][0]-p[i-1][1] >= s:
ok = True
print("YES" if ok else "NO")各テストケースでまずリストを作り、そこに各タスクの始めの時刻と終わりの時刻を入れています。ただし、最初のタスクを始める前の時間と、最後のタスクの後の時間にもシャワーに入れる可能性があるので、リストの最初に[0,0]、最後に[m,m]を入れて、そこもチェックできるようにします。
（[0,0]の本質は後者の0で、[m.m]の本質は前者の m のみです。
そうでない方は飾りで、実際のチェックには使われていません。）
あとは、それぞれのタスクの間の時間がsより長いかをチェックしていき、
1つでも条件を満たすならbool変数 ok をTrueにします。
補足
タスクはまとめてやって、風呂にはちゃんと入れよ
おすすめは家に帰った直後に風呂に入ってしまうことです…
いったん座ると立ち上がるのにまた元気が必要になるので…
D問題 Slavic's Exam
問題
非常に大変な試験を受けているスラブ人があなたに助けを求めています。
ある文字列 s があり、これは英小文字と "?" から成っています。
また、ある文字列 t があり、これは英小文字のみからなります。
試験の内容は、s の "?" を任意の英小文字に変えることによって、文字列 t が s の部分文字列(連続でなくてよい)とできるかどうかを判定することです。
これが可能かどうか、また可能な場合はそうした操作後の文字列 s を1つ、スラブ人に教えてあげてください。
t 個のケースが与えられます。それぞれについて答えてください。
制約
1 <= T <= 10^4 (テストケース数)
1 <= |s| <= 2 * 10^5 (文字列 s の長さ)
1 <= |t| <= |s| (文字列 t の長さ)
文字列 s は英小文字と"?"、また文字列 t は英小文字から成る。
なお、すべてのケースにおける|s|の総和は2*10^5未満である。
入力例
2
a????
bxb
ab??e
xac
出力例
Yes
abaxb
No
解法
そもそも「t が s の部分文字列である」というのは、「sから順番を変えずに任意の文字を抜き出してそれらを繋げたときに t と一致させられる」という意味です。
上記の出力例のケース1では、s = "abaxb"、t = "bxb"となっています。
sの2文字目、4文字目、5文字目を取り出し、順番を入れ替えずに並べると"bxb"となり、tと一致させることができますため、これが正解の1つとなります。他に、s = "aabxb"なども正解となります。
さて、愚直解法として、文字列 s のそれぞれの"?"を個別にどの英小文字にするか決め、文字列 t が s の部分文字列となったかを判定する方法がありますが、
これは実行時間に間に合いません(最悪 O(26^(2*10^5)))。
部分文字列を扱う際の1つの方法として、「先頭から決めていく」というのがあります。これも愚直な、貪欲解法と言えましょう。
「tをどこまで完成させられたか」を変数として持っておきます(ここでは変数check)。
sを先頭から順に見ていき、sの最後に到達したときにcheckの値がtの長さに一致する、すなわちtが最後まで確認できたなら、tが部分文字列になるような s を構成できたということにできます。
説明のため、具体的な例で考えてみます。
手元で紙に書きながら確認してみることをおすすめします。
以降、s = "a??b?"、t = "bxb"とします。
さて、tをどこまで完成させられたかの変数として、変数checkを持っておきます。初期値は0です。
このときやりたいことは、tをできるだけ早く、大きな値にしていきたいです。つまり、tを加算できる状況になったらすぐに加算します。
現時点で、目標となる文字は t の1文字目、"b"です。
ここから、sを先頭から順番に見ていきます。
まずは1文字目、s = "a??b?" の1文字目は"a"です。これは、目標としている文字とは一致していません。sのうちすでに英小文字のものは変更できないので、今回は進展なしでした。
2文字目。s = "a??b?" の2文字目は"?"です。チャンス。"?"は任意の英小文字に書き換えられますので、これをいま目標としているbに書き換えれば、1つ目標を達成できます。ということで s の2文字目を"b"に変えます。この時点での文字列 s は"ab?b?"となっています。また、checkを1つ増やします。ここで目標の文字がtの2文字目、"x"に移りました。
3文字目、s = "ab?b?" の3文字目は"?"です。またチャンス。先ほどと同様に、"?"をいま目標としている"x"に書き換えればまた1つ目標を達成できますので、sの3文字目を"x"に変更し、checkを1つ増やします。これにより、s = "abxb?"、次に目標となる文字は t の3文字目である"b"となりました。
4文字目、s = "abxb?" の4文字目は"b"です。この文字は"?"ではないものの、いま目標としている文字"b"に一致しています。よって、書き換えなしに目標を達成できます。sは書き換えず、checkの値のみを1つ増やします。さて、これによってcheckの値は3となっており、文字列 t の長さと同じになっています。よって、すべての目標を達成し、tが部分文字列となるような s を晴れて構築できたことになります。実際、この時点でs = "abxb?"であり、sの2～4文字目をそのまま抜き出すことでt = "bxb"に一致しました。
これ以降の文字はどう書き換えようが、それ以前の部分には影響しませんので、以降の"?"は何に書き換えても大丈夫です。5文字目は適当に"a"にでも書き換えておきます。
これで、s = "axbxa"となり、これは t = "bxb"を部分文字列として持っていますので、解決しました。
具体例を持ち出したために説明が長くなってしまいましたが、
つまるところ、tを先頭から見ていき、sに埋められる最速の段階で埋めていって、これで最後まで遂行できたらOK、ということになります。
時間計算量は各ケースO( |s| )程度、制約より |s| の総和は十分小さいので、実行時間制限に間に合います。
提出コード
q = int(input())
for _ in range(q):
s = list(map(str, input()))
t = list(map(str, input()))
now = 0
for i in range(len(s)):
if now == len(t):
if s[i] == "?":
s[i] = "a"
continue
if s[i] == "?":
s[i] = t[now]
now += 1
else:
if t[now] == s[i]:
now += 1
if now == len(t):
print("YES")
print("".join(s))
else:
print("NO")E問題 Triple Operations
問題
アイビーは黒板に L 以上 R 以下のすべての数を書きました。
彼女は以下の操作をすることができます。
「黒板に書いてある数のうちから x と y の2つの数を選び、それらを黒板から消し、新たに 3*x と floor(y/3) を黒板に書く。」
黒板に書いてある数の合計を0にするのにかかる最小の操作回数はいくらですか？
なお、与えられた制約の中では有限回の操作で達成することが証明できます。
t個のテストケースが与えられます。それぞれについて答えてください。
制約
1 <= t <= 10^4 (テストケースの数)
1 <= L < R <= 2 * 10^5
入力例
4
1 3
2 4
199999 200000
19 84
出力例
5
6
36
263
解法
はじめに、Lが必ず正の数である以上、黒板の数字が負の数になることは絶対にありません。
したがって、総和を0にするという最終目標は、「黒板に書いてある数字を全て0にする」ことと読み替えられます。
(黒板に書かれている数字が負の値になりうる場合には、たとえば-1,0,1が黒板に残っても条件を満たしたことになるので、完全に別の話になります。)
もう1つ大事なこととして、0は何倍しても0になるということが挙げられます。そんなの当たり前だろうがという声が聞こえますが、これはすなわち、ある操作における x として0を選べば、操作で黒板に書かれる 3*x は0のままだということです。逆に、0より大きいすべての整数は、3倍すると3倍の値になります。
黒板に書かれたすべての値を"0"という最小値に近づけようとしているわけですから、値が大きくなってしまうことは基本的に望ましくないと考えられます。実際、たとえば黒板に1と書かれていた場合に、これを0にするためには1回の操作(yとしてこの1を選ぶこと)が必要です。いっぽう、xとして1を選びその後黒板に書き直される値は3になりますが、この3を0にするのにかかる操作回数は2回です(3→1→0)。1回値を大きくしてしまうとそれを小さくするのに追加のコストがかかってしまうことになります。
ということは、基本的に x として1以上の整数を選んでしまうことは望ましくない(ゴールから遠のいている)ということになります。
こうした考察から得られる結論は、「とりあえず最初に爆速で0を作って、残った数字は0を相方にしてちっちゃくすればいいんじゃね？」ということになります。
ではこの考察を基にコードを書いてみます。
まずは、とりあえず爆速で0にする値をどれにするかという話です。
これは、明らかに最初から小さい値を選んだほうが良いので、黒板に書いてあるうち最小の値、つまり L とします。
では、この L を0回にするために何回かかるかを記録しておきます。Lが0になるまで、3で割って切り捨てという操作を行いつづけます。このとき、変数ans = 0として、割るたびに毎回 ans に2を足しておきます。
ここで足す値を2としているのは、Lを減じるために増やされる相方が必要であり、その相方がこのあと0にされるのに必要な回数が増えてしまっている分です。噛み砕いて書くと、Lを0まで減らす操作をしたぶんと、さらにそこで増えてしまった相方が元の値に戻ってくるまでの操作をしたぶんをまとめて計算しているというところです。
次に、黒板に書かれている "0" (元々 L だったもの)以外の値について考えます。すでに黒板には0があるので、xとして0を選び続ければ、黒板に書いてある数が増えることは絶対にありません。つまり、L+1からRまでのそれぞれについて、3で割って切り捨てる操作を何回やればいいのかを全て計算して総和を求めればよいということになります。
ただ、ここで問題があります。実行時間制限に間に合わないケースの存在です。制約から、最悪ケースとしてL = 1、R = 200000の場合が考えられ、これが20000回のテストケースすべてで送られてきた場合、テストケースごとに1つずつ黒板の数字を計算しているとO(t * (R-L) ) = O(10^9)程度の時間計算量になってしまいます。これは実行時間制限に間に合いません。
この問題を解決するうえでポイントなのは、「黒板に書いてある数字はすべて連続している」ということです。連続している部分の和を求めるには、「累積和を用いた区間和の計算」が利用できます。すなわち、黒板に書かれている可能性のある数についてそれぞれ何回の操作で0にできるのかをあらかじめ計算しておき、テストケースごとに「0からRまでの総和」から「0からLまでの総和」を引くという形で区間和を求めることができれば、実行時間制限に間に合う計算が行えます。
ということで、テストケースを貰う前に、あらかじめ計算をしておきます。
0 <= i <= 2 * 10^5となる i それぞれについて、必要な操作回数を数え、それをリストに入れておきます。その後、その累積和を求めます。
各テストケースでは、先のとおり最初の0を作るまでの回数を記録した ans をまず計算します。その後、L+1からRまでのそれぞれについて必要な操作回数の総和を求めます。これには、累積和を用いて「0からRまでの総和」から「0からLまでの総和」を差し引いた値を求めます。
これをansに足し合わせて、答えとして出力するという流れです。
提出コード
t = int(input())
p = []
for i in range(10**5*2+5):
tm = 0
m = i
while m:
m //= 3
tm += 1
p.append(tm)
q = [0]
for i in range(len(p)):
q.append(q[-1] + p[i])
for _ in range(t):
a,b = map(int, input().split())
ans = 0
c = a
while c:
ans += 2
c //= 3
ans += q[b+1] - q[a+1]
print(ans)リスト p はその数字が0になるまでに必要な操作回数の一覧です。
リスト q はリストpの累積和です。
補足
累積和を用いた区間和は至るところで出てくる考え方のような気がします。そして、この考え方だけが単独で求められるというよりも、他の考え方をしている中でそれと併せて使うことが求められるパターンが印象です。
累積和の区間和という考え方を使うケースの1つは、1つの大きいところから1つの小さいところを引けば欲しい値が求められるという場合です。
累積和単独だと、Atcoderでは灰色中上位～茶色下位程度の初歩的な問題として扱われることも多そうですので、ふとした時に使えるようになっておくとよいかと思います！
G問題-1 Ruler (easy version)
問題
出題側が「秘密の定規」を持っています。
「秘密の定規」は、目盛りの数字のうち、ある x (2 <= x <= 999)だけが欠けた定規です。
もしある長さ y を「秘密の定規」で測った場合、以下のような計測結果となります。
・もし y < x なら、「秘密の定規」は正しく長さを測ります。すなわち、計測結果として y を返します。
・もし y >= x なら、「秘密の定規」は間違った長さを測ります。すなわち、計測結果として y+1を返します。
あなたは、欠けている数字 x が何かを割り出す必要があります。そのためにあなたができることは、出題側に以下のクエリを投げることです。
"? a b"
出題側はこのクエリに対して、隣り合う2辺の長さがaとbの長方形について、それぞれの辺を「秘密の定規」で計測した結果をもとに、長方形の面積を返します。たとえば、x = 4のとき、クエリが3*5の場合は、「秘密の定規」を用いた計測結果は3*6となり、クエリに対して計測結果をもとにした面積である18を返します。
クエリを投げることによって、x を割り出してください。ただし、クエリを投げられる回数は10回以下です。
t個のテストケースが与えられます。それぞれについて答えてください。
制約
1 <= t <= 1000 (テストケースの数)
2 <= x <= 999 (秘密の定規に欠けている数)
解法
クエリを10回しか投げられない以上、2から999まで1つずつ聞いていって境目を探すことは当然できません。
さて、yが一定の値以下であれば正しい計測値が返ってきます。
いっぽう、一定の値以上だと誤った計測値が返ってきます。
こうした、「一定の値までは条件を満たすが、それを超えると条件を満たさなくなる」(あるいはその逆、とにかくある値を境に条件を満たすエリアと満たさないエリアに分かれる)という性質から値を特定する場合によく使われる方法が、二分探索です。
二分探索はn回行うと2^nの値までであれば特定可能です(逆に言えば、探す範囲がnの場合、logn回程度の二分探索で特定可能です)。
今回はクエリを投げられる回数が10回となっていますので、2^10 = 1024までの範囲は特定できます。したがって、単純な二分探索で十分求まるといえます。
二分探索の基本を抑えつつ実装について考えていきます。探す範囲の左端をok = 0、右端をng = 1001としておきます。初期値は、その値であれば必ずokないしngとなる値にしておきます。今回はxの範囲が2以上999以下ですので、この初期値は妥当です。
二分探索を始めます。今回クエリを投げてみる値mdは、(ok + ng) // 2とします。これが、現在のokとngのちょうど真ん中の値です。
クエリは特段工夫せずに投げます。"? md 1"としておけば、x < mdなら正しい値(= md)が返ってきますし、そうでないなら間違った値(= md+1)が返ってきます。
正しい値が返ってきた場合、x は md よりもっと大きいということなので、ok を md にします。間違った値が返ってきた場合、x は md より小さいということなので、ng を mdにします。
これによって、探すべき範囲は前回の半分になりました。
ここまでが1回の二分探索の操作になります。このあとも同様の操作を続け、10回クエリを処理したところでng-okが1になるはずです。
その値が、正しい値が返ってくるかどうかの境目と分かるので、すなわち秘密の定規の値が欠けている場所ということになります。
答えが分かりましたので、あとは出力するだけです。
提出コード
q = int(input())
for _ in range(q):
ok,ng = 0,1001
while 1:
if ng-ok == 1:
print("!", ok+1)
break
else:
md = (ok+ng)//2
print("?", 1, md)
ret = int(input())
if ret == md:
ok = md
else:
ng = md補足
二分探索も、競技プログラミングにおいては基本的な知識・技術です。
「めぐる式二分探索」で検索してみると、失敗しづらい二分探索の実装について書いた記事が読めるかと思いますので、気になった方はぜひご覧ください。
また、今回のようないわゆるインタラクティブな問題(入力をひと通り受け取って答えを導き出すのではなく、こちらから欲しい情報を投げながら答えを導き出すタイプの問題)は、初心者の方にはやや難しいところもあるかと思います。
ただ、同様に苦手とする方が多い形式でもあるので、問題の内容自体の難しさのわりに正答率が若干下がりがちです。身につけるとライバルのかなり先を行けるかもしれません！気が向いたら勉強なさってみてはいかがでしょうか。
G問題-2 Ruler (hard version)
問題
概要は上のG1と同じです。ただし制約が先の問題と異なり、
投げられるクエリの回数が7回までとなっています。
解法
G1ではクエリが10回投げられることから2^10 = 1024で範囲をカバーできるため、シンプルな二分探索で求められました。
しかし、クエリが7回しか投げられない本問では、2^7 = 128で範囲をカバーできず、単純な二分探索では答えの特定には至りません。
ここで考えるべきは、投げられるクエリがただの長さではなく、長方形の長さであるという点です。ここから、適切に投げたクエリから返ってくる結果から得られる情報は3つあるということになります。
以下、簡単のためにa < bとしておきます。
クエリを投げた際に返ってくる結果は以下の3通りのどれかです。
① a * b (a < b < x の場合)
② a * (b+1) (a < x <= b の場合)
③ (a+1) * (b+1) (x <= a < bの場合)
たとえば、x = 5の場合、
① a = 3, b = 4 (a < b < x) を投げると返ってくる値は12 ( = a * b)
② a = 3, b = 7 (a < x <= b) を投げると返ってくる値は24 ( = a * (b+1) )
③ a = 6, b = 7 (x <= a < b) を投げると返ってくる値は56 ( = (a+1) * (b+1))
となります。
G1の二分探索では、毎回のクエリで範囲を半分に絞っていました。
しかし今回の探索では、返ってくる情報が3通りあるわけですから、毎回のクエリで範囲を3分の1まで絞れるということになります。
毎回3分の1にできるということは、これを7回行う際に特定できる範囲は3^7 = 2187となります。したがって、晴れて問題範囲をカバーできました。
(ちなみにこれは”三分探索”…ではありません。詳しくは下の補足にて)
さて、ここからは実装のお話になります。
二分探索では、変数okとngを置き、それらの中間の値mdをクエリに投げることで範囲を絞っていきました。
今回工夫する必要があるのは、クエリを投げる部分、すなわちmdの決め方になりそうです。
okとngの間を3分の1にしていくということは、okとngを3等分できるmd1とmd2を設定できると、良さそうな気がしませんか？しますよね？そう、するんですよ。
ということで、投げるクエリのaにあたるmd1はok + (ng-ok)//3、
bにあたるmd2はok + (ng-ok)//3*2とします。
これで、xがどの範囲にあるかを判別することで、
xが ①okからmd1の間 ②md1からmd2の間 ③md2からngの間
のどのパターンなのかを割り出すことができます。
あとは、それに合わせてokやngを更新していくことで、答えに近づいていくことができます。
最終的には、二分探索と同様、ngとokの差が1になった場所が境目であり、そこが欠けている数字だとということになります。
提出コード
q = int(input())
for _ in range(q):
ok,ng = 0,1000
while 1:
if ng-ok == 1:
print("!", ok+1)
break
elif ng-ok == 2:
md = ok + 1
print("?", md, md)
ret = int(input())
if ret == md**2:
ok = md
else:
ng = md
else:
mdl = ok + (ng-ok)//3
mdr = ok + (ng-ok)//3*2
print("?", mdl, mdr)
ret = int(input())
if ret == mdl*mdr:
ok = mdr
elif ret == mdl*(mdr+1):
ok = mdl
ng = mdr
else:
ng = mdl説明内でmd1・md2と書いていたものは、コード中ではそれぞれmdl(md_leftの略)、mdr(md_rightの略)となっています。
返ってきたクエリの性質ごとにokやngにどういった更新を行えばよいのかは、コードをご参照ください。
なお、ngとokの差が2になった場合、3分割ができないことからどういった挙動になるのか不安だったので、そこだけ別で二分探索のように処理をするようにしています。
補足
三分探索は、範囲を3分の1に絞る探索ではなく、
範囲を3分の2に絞る、すなわち3分の1を削り取るような探索のようです。
詳しくはよく分からないので、Bingでヤフってください。
二分探索では済まないケースが出てくるとは思ってなかったし初めてするタイプの実装だったので、本番ではおそるおそる実装していました。
方針に気づいたときの道が光に照らされた感覚はやはり何事にも代えがたいものがあります。
さいごに
ご覧いただきましてありがとうございました。
私自身Atcoder緑なのであまり大したことも書けないし、何より正確性が胡散臭いので大きなことは言えませんが、誰かの何かしらの足しになっていれば幸いです。
参考になったよという方はぜひいいねなど残していただけるとありがたいです。あるいは「こういうところが分かりにくいぞ！」というところはコメント等していただければと思います。
こどふぉの日本語解説、増えてほしいな～
そして、B問題とF問題の解法を、教えてください！(B問題 5WA)