1日9時間寝たい

本当は10時間寝たいです

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;
}