三年目の初学者(8問目)
問題
AtCoder Beginner Contest 093 D - Worst Case
D - Worst Case
使用言語
C++
方針
・100マス計算の表みたいな感じで行けるものだと思っていたが、細かいところができない。
・解説(https://img.atcoder.jp/arc094/editorial.pdf)を参考にした。下の通りに考えると判りやすい。(丸が最大となるときの候補の一つ)
所感
・簡単そうに見えて難しそうなやつだと思ったら、やっぱりそうだった。
・実装はクソ楽。
・結構力作の解説のつもり。
・桁落ち、負の処理、根号の処理を気をつけたい。
コード
#include <iostream> #include <string> #include <math.h> #include <algorithm> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=a;i<b;i++) #define REP(i,b) FOR(i,0,b) #define INF 1e9 typedef long long ll; typedef unsigned long long ull; void solve(ll a, ll b) { if (a > b) swap(a, b); //常に a <= b if (b - a <= 1) { cout<<2 * (a - 1)<<endl; } else { ll c = (int) sqrt(a * b); if (c * c == a * b) c--; if (c * (c + 1) >= a * b) { cout<<2 * (c - 1)<<endl; } else { cout<<2 * c - 1<<endl; } } } int main(){ int q; cin>>q; ll a[q], b[q]; REP(i,q) cin>>a[i]>>b[i]; REP(i,q) solve(a[i], b[i]); return 0; }