ICPC 2018 国内予選 参加記
はじめに
ACM-ICPC 2018 Asia Yokohama Regionalにチーム super_ikd で参加しました。結果はABCの3完103位でした。
チーム
チーム名:super_ikd
メンバー
niyarin さん
研究が忙しそう!
srup さん
問題の解法検索したらブログがよくヒットする!
ikd (自分)
無
コンテスト
- BとCとDの問題文を印刷します
- 事前に話し合っていたとおり、Aをniyarinさん、Bをsrupさん、Cをikdがやります
- ikdがCを誤読してる間にniyarinさんがAを通します (00:08:11) 神
- srupさんがBの解法(方針)をniyarinさんに伝えて、ほどなくしてniyarinさんが実装を始めます。ikdはまだ誤読をしています。srupさんはDとEを読んでいる?
- 誤読に気づいて、ちょっと問題が簡単になりました
- O(n), n≦109 の解法ができてsrupさんに説明すると、よさそう感を共有できたので紙に簡単なコードを書いていきます
- Bの実装がつらくなったそうなので、一旦交代してikdがCを書きます
- 紙に書いておいたのを書き写すだけなので簡単です。バグります
- printfデバッグしてもよく分からなかったので、適当に不等号のイコールを取ったり外したりするとサンプルが合います
- テストケースをダウンロードして手元で実行すると、O(n)だけあってすぐには終わりません。10秒くらい待ってると結果が出力されます。簡単なケースを見つけて、出力が手で解いたのと一致しているのを確認して提出します。通ります (01:17:25)
- niyarinさんがBのバグの原因が分かったとのことで実装を再開します
- またまたsrupさんにDの解法を説明すると、よさそう感を得られたので実装を詰めます
- 実装無理では・・・
- ...
- ...
- ...
- niyarinさんがBを通します (02:16:28) 神
- ikdがパソコンの前に座ってDを書きます。niyarinさんとsrupさんはEを考えています
- 書けません
- ...
- ...
- ...
- コンテストが終わります
おまけ
全問題はここから見られます → All Problems
C問題を担当したのでそれについて書きます。
C問題の概要
入力として整数$b$が与えられます ($1\le b\le 10^9$)
$\displaystyle\sum_{i=l}^{r}i=b$となるような$l, r$のうち、$r-l$が最大のものを求めてください
解法
条件を満たすl, rのうち、lが最小のものを答えればよさそう。
区間[l, r]の和がbを超えるような最小のrはlに対して単調なので尺取り的にやるとO(b)
実装
#include<iostream> using namespace std; int main(){ while(true){ int b; cin>> b; if(b==0) break; for(int l=1, r=1, sum=0; l<=b; ){ while(sum<b) sum+=(r++); if(sum==b){ cout<< l<< " "<< r-l<< endl; break; } while(sum>b) sum-=(l++); } } return 0; }