2025-12-19

二分探索を書きたくない

この記事は、CTRL場外乱闘 Advent Calendar 2025 n日目の記事です。競技プログラミングでコードを楽に書こうとした話です。

はじめに

二分探索は、決められた範囲の中からある条件を満たすような最小(もしくは最大)のindexを高速に探す用途で使えます。競技プログラミングにおいてもよく登場するアルゴリズムで、例えば、AtCoder Beginner Contest 227のD問題では以下のように書けます。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long; // long longと毎回書くのは面倒なので省略
int main() {
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  ll ok = -1, ng = 1e18 / k;
  
  /* 二分探索はここから */
  while(abs(ok - ng) > 1) {
    ll mid = (ok + ng) / 2;
    ll sum = 0;
    for(int i = 0; i < n; i++) {
      sum += min(mid, a[i]);
    }
    if(sum >= mid * k) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  /* ここまで */

  cout << ok << endl;
  return 0;
}

ここでは、-1から10¹⁸ / kまでの範囲内で二分探索をしています。これはこれでいいのですが、コンテスト中に急いで書くと途中で間違えてしまうことがありました。abs(ok - ng) > 1をabs(ok - ng) >= 0と書いてしまったり、if(sum >= mid * k)の条件式を間違えたり・・・。 C++には標準でstd::upper_bound（とstd::lower_bound）という二分探索のための関数が用意されています。この関数を使えば、二分探索を自分で書かずに済むのではないかと考えました。

書いてみる

std::upper_boundを使うには配列が必要ですが、サイズが10¹⁸にもなるとメモリに収まらなくなってしまいます。この問題は、std::ranges::upper_boundとstd::views::iotaを使うことで回避できました。std::views::iotaは指定した範囲内の値を列挙する単調増加列です。アクセスした要素のみ生成されるため、必要なメモリが配列よりも少ないというメリットがあります。

ソースコードは以下のようになります。

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <ranges>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  auto check = [&](const ll &x) {
    // cout << x << " ";
    ll sum = 0;
    for(int i = 0; i < n; i++) {
      sum += min(x, a[i]);
    }
    // cout << sum << " " << x * k << endl;
    return sum < x * k;
  };
  auto rng = std::views::iota(0LL, (ll)1e18 / k);
  auto itr = std::ranges::upper_bound(rng, 0, {}, check);

  cout << (ll)(itr - rng.begin()) - 1 << endl;
  return 0;
}

引っ掛かったポイント

std::views::iotaの引数
- std::views::iotaの引数には0ではなく0LLを入れる必要がありました。0にするとint型で計算されるため、オーバーフローを起こしてしまうようです。
itr - rng.begin()の計算
- itr - rng.begin()の計算結果はdifference_typeという型になるのですが、前述のソースコードの場合は__int128になります。__int128は標準型ではなく、cout << __int128のオーバーロードは存在しないため、long longにキャストする必要がありました。
コンパイラの設定
- std::ranges::upper_boundとstd::views::iotaはいずれもC++20で追加された関数です。これまでg++ -std=c++17でコンパイルしていたので、g++ -std=c++20に変える必要がありました。
- 基本的な話ですが、競技プログラミングにおいては（あるいは業務でも）手元の環境と実際の実行環境の違いを把握しておくことは重要と言えそうです。

最後に

コメントを消してからAtCoderのサーバにコードを提出してコード長を比べると、元のコードは693byte、std::ranges::upper_boundを使うように書き直したコードは769byteとなっていました。二分探索を書かずに済むようになったとはいえ、コードが長くなる上に引っ掛かるポイントもあるとなると、楽な書き方とは言えないのかもしれません。

参考資料

2024-12-24

自宅で動かしているOSSをまとめてみる

はじめに

この記事はTCU-CTRL場外乱闘 Advent Calendar 2024　n日目の記事です。 (後から入れているため何日目か分からず……)

自宅で動かしているOSSをまとめてみました。

Ollama

OllamaはローカルでLLM(大規模言語モデル)を動かすためのソフトウェアです。Meta社のLlama 3やGoogleのGemma 2など、自由にLLMを選んで動かすことができます。インストールした環境でNVIDIAのCUDAやAMDのROCmが利用可能であれば、GPUによる推論も可能です。

CLIとAPIのみを提供するので、GUIで操作したい場合は別途UIのツールを用意するか自作する必要があります。

qwen2.5

qwen2.5はアリババ社が開発したLLMです。LLMはソフトウェアではないと思いますが、一応書いておきます。先述のOllama上で動かしています。今のところ14Bのモデルを利用していますが、OSS版では最大で32Bのモデルまで用意されています。

翻訳や要約用途であれば、意外と使えます。文章を全部放り込んで、最後に一言「要約して」と付け足すだけです。中国製だからなのか、日本語で応答しているのに途中から中国語に変わることがよくあります。

Open WebUI

Open WebUIは、OllamaやOpenAI互換のAPIなどに対応したLLM向けのWebUIです。LLMとのチャットの履歴を保存したり、ユーザーを管理したりする機能を持っています。先述のOllamaと組み合わせて、ローカルのLLM環境を実現するために利用しています。

UIがどことなくChatGPTに似ていますが、恐らく気のせいです。未検証ですが、月20ドル払ってChatGPT Plusを契約するよりは、Open WebUIを利用してAPI経由でChatGPTにアクセスするほうが安上がりかもしれません。

Portainer Community Edition

Portainerは、コンテナを簡単にGUIで管理することができる軽量の管理ソフトウェアです。コンテナに加えてイメージやボリューム、ネットワークも管理できます。大量のコンテナを管理したいときに便利です。

オープンソースのCommunity Editionに加えて、有料で機能が多いBusiness Editionもあります。

Nextcloud

Nextcloudはオンラインストレージを構築するためのソフトウェアです。オンラインストレージ機能に加えて、チャット機能やビデオ会議機能、カレンダーや連絡先の機能も持っています。

スマホアプリと連携させて、容量に制限のあるGoogleフォトの代替バックアップ先として利用しています。また、スマホー PC間のファイル移動にも利用しています。ストレージのサイズをいくらでも拡張できること、ローカルのLANで通信が完結するのでファイル移動も速いことがメリットです。

最後に

ここで取り上げたもの以外でも自宅で動かせるOSSを探したい、という場合は「awesome self hosted oss」で検索すると色々出てきます。

正直に言うと、自宅で動かすよりも、課金して有料のサービスを利用したほうが楽です。ハードウェア故障のリスクがなく、快適で質の高いサービスを享受することができます。それでも自宅で動かしてみたいという~~変わった思考回路をお持ちの~~方は、ぜひ一度試してみてください。

2022-12-09

競プロをしていて役に立ったこと

はじめに

この記事は競プロ Advent Calendar 2022 八日目の記事です。卒業研究の中で競プロをしていてちょっとだけ役立ったことを書きます。

競プロ要素がどこにあったか

現在自分が進めている卒業研究では、処理にかかる実行時間を測定することでうまくいったかどうかの評価を行います。同じ研究室の先輩が書いた論文を読んだところ、プログラムを100回程度繰り返し動作させた場合の処理時間の最大値、最小値、平均値が記載されていたので、自分もそれにならって最大値、最小値、平均値を求めることにしました。その中でも、平均値を求めるところで落とし穴があったのでそれを書きます。

実行時間を測定する

研究ではC言語を使っているので、C言語で細かい単位で時間を測定できる方法を探しました。その結果、 timespec という構造体と clock_gettime() という関数を使うことでナノ秒単位で時間を測定できることが分かったため、これを採用しました。疑似的なソースコードで表現すると下のようになります。

#include <stdio.h>
#include <time.h>
int main()
{
    struct timespec before, after;
    clock_gettime(CLOCK_REALTIME, &before);
    // ここに処理時間を測定したい関数を入れる
    clock_gettime(CLOCK_REALTIME, &after);
    printf("%ld.%9ld\n", before.tv_sec, before.tv_nsec);
    printf("%ld.%9ld\n", after.tv_sec, after.tv_nsec);
    return 0; 
}

あとは after - before を計算するだけ、と言いたいのですが、構造体なのでそう簡単には計算できません。timespec は時間を秒で表現したときの整数部分を表すメンバ変数と小数点以下を表すメンバ変数に分かれているので、繰り上がりが起きた場合のことを考慮する必要があります。これを踏まえた上で、 after - before を計算するコードを書くと以下のようになります。

#include <stdio.h>
#include<time.h>
int main() { 
    struct timespec before, after, result;
    clock_gettime(CLOCK_REALTIME, &before);
    // ここに処理時間を測定したい関数を入れる
    clock_gettime(CLOCK_REALTIME, &after);
    printf("%ld.%9ld\n", before.tv_sec, before.tv_nsec);
    printf("%ld.%9ld\n", after.tv_sec, after.tv_nsec);
    if(after.tv_nsec < before.tv_nsec) {
        result.tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
        result.tv_sec = after.tv_sec - before.tv_sec - 1;
    } else {
        result.tv_nsec = after.tv_nsec - before.tv_nsec;
        result.tv_sec = after.tv_sec - before.tv_sec;
    }
    printf("%ld.%9ld\n", result.tv_sec, result.tv_nsec);
    return 0;
}

平均値を求める

実行時間を測定することができたので、それを元に平均値を求めます。

WAになる実装

研究では100回繰り返して平均値を求めるのですが、この記事の中では10回だけ繰り返して計算することにします。

#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main() { 
    struct timespec before, after, result[100], average;
    int i;
    average.tv_sec = 0, average.tv_nsec = 0;
    for(i = 0; i < 10; i++) {
        clock_gettime(CLOCK_REALTIME, &before);
        // ここに処理時間を測定したい関数を入れる
        usleep(999499);
        clock_gettime(CLOCK_REALTIME, &after);
        if(after.tv_nsec < before.tv_nsec) {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
            result[i].tv_sec = after.tv_sec - before.tv_sec - 1;
        } else {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec;
            result[i].tv_sec = after.tv_sec - before.tv_sec;
        }
        average.tv_sec += result[i].tv_sec;
        average.tv_nsec += result[i].tv_nsec;
        printf("%ld.%9ld\n", result[i].tv_sec, result[i].tv_nsec);
    }
    average.tv_sec /= 10, average.tv_nsec /= 10;
    printf("%ld.%9ld\n", average.tv_sec, average.tv_nsec);
    return 0;
}

これを実行すると

1.   328800
0.999643800
1.   716000
0.999598500
0.999711900
0.999845900
0.999581600
0.999785400
1.   607300
1.   112100
0.599993130

という結果となりました。このように、1.0秒以上のケースと0.9秒のケースが混ざると明らかに間違った答えが返ってきてしまいます。

ACになる実装

timespec の変数を一度 long long 型に変換してから平均値を求めることで、このバグを修正できます。

#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main() { 
    struct timespec before, after, result[100];
    long long average;
    int i;
    average = 0;
    for(i = 0; i < 10; i++) {
        clock_gettime(CLOCK_REALTIME, &before);
        // ここに処理時間を測定したい関数を入れる
        usleep(999499);
        clock_gettime(CLOCK_REALTIME, &after);
        if(after.tv_nsec < before.tv_nsec) {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
            result[i].tv_sec = after.tv_sec - before.tv_sec - 1;
        } else {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec;
            result[i].tv_sec = after.tv_sec - before.tv_sec;
        }
        average += (long long)result[i].tv_sec * 1000000000;
        average += (long long)result[i].tv_nsec;
        printf("%ld.%9ld\n", result[i].tv_sec, result[i].tv_nsec);
    }
    average /= 10;
    printf("%lld.%9lld\n", average / 1000000000, average % 1000000000);
    return 0;
}

これを実行すると

0.999956600
1.   362300
0.999662700
0.999860000
1.   495200
0.999632900
0.999929000
0.999637000
1.   339900
1.   311800
1.    18740

という結果となりました。これは信用できそうです。

まとめ

感想

解法自体は特に難しくないのですが、研究ではジャッジサーバは存在しないため、バグが生まれそうなケースを自分で考えなければなりません。バグが残っている状況を考えるところで競プロが役に立ったと感じました。

その後

教授に相談した結果、ソースコードの中に平均値を求める実装を書くのではなく、

1回ごとに実行時間を画面に出力し
結果をExcelに貼り付けて計算

したほうが良いということでした。そのほうが実行時間の分布も見ることができる上に、実行時間を記録として残すことができるというメリットもあるそうです。（実は競プロは役に立たない？？？）

最後まで読んでいただき、ありがとうございました。

2022-07-12

ICPC 2022 国内予選参加記

はじめに

今年もICPC国内予選に参加しました。今年のチームメンバーはあめふり君とノブチ君です。今年は対面でもOKだったようなのですが、去年同様オンライン形式で参加しました。去年から変わった点を挙げるとしたら、Zoomの教育機関向けの支援が終了したため、代わりにDiscordのグループ通話を使った点ですね。

開始前日

全く見ないのはどうかと思ったので、過去問をほんの少しだけ解きました。解いたのは「国内予選2017A」「国内予選2017B」「国内予選2018A」「国内予選2018C」です。本当はもう少し解こうと思ったのですが、前日だったので寝不足になるほうがデメリットが大きいと思い、切り上げて寝ました。

当日

ノブチ君はA問題、あめふり君はB問題、自分はC問題を読んで、実装できそうなら実装を進めることにしました。今年は去年のように開始した途端にシステムが落ちるといったことがなくて安心しました。以下、各問題の感想です。

A問題

ノブチ君が特に詰まることなく通してくれました。なので、コンテスト中は問題を読んでません・・・

B問題

あめふり君が、「実装が重い」と言ってました。実際に問題を見ると何だか面倒な感じでした。ただ、解法が全く分からないという訳ではなさそうだったので、バグ等で詰まるまでは任せることにしました。

C問題

自分が担当した問題です。練習日が連続するとn²に比例してパワーアップして、休息日が連続するとn²に比例してパワーダウンするので、上手いことスケジュールを組んだときの実力の最大値を答えてね！という趣旨の問題でした。何となく休息日-練習日-休息日の順にすると良さそうな気がしたので実装したところ、ほとんどのサンプルは通りました。しかし、練習日が7日で休息日が9日の場合だけ答えが合いません。

20分以上考えても分からないので、bit全探索で答えを探したところ、最初の考えは間違いであることが分かりました。どうやら休息日を小分けにする形で練習日を入れて、余った練習日をひとまとめにすることが最適であるようです。ここで、休息日をどれくらい小分けにするか悩んだのですが、制約を踏まえると休息日をk個に分割するとしてkを全探索しても問題ないと気付きました。

これを踏まえて実装し、何とか正解することができました。ただ、ここまでで1時間半近く経過していました。

D問題

恐らく列の中で切っては（別のゲートに誘導しては）いけない人達がいて、逆に自由に切ってもいい場所があるんだろうなぁということは予想できました。なぜなら、そうでないと答えが非常に大きくなることがないためです。

ただ、どこが1つのゲートに誘導すべき人達なのかがさっぱり分からず、手も出ませんでした。

E問題

自分がD問題を考えている間にノブチ君がある程度まとめてくれていました。正気度は最初0であること、正気度が途中で負になると村から出られないことを考えると、村から出られた人のところは最初に「美しい像」があるということまで考察してくれていました。

次に、村から出るときに正気度が正の場合は村から出られなくなるという条件を踏まえると、最後に通る交差点には「恐ろしい像」があることが分かりました。この2つを合わせると、リストと矛盾しない像の配置があるかどうかを判定できそうです。実際に実装するとサンプルではYes/Noのみを正答できるようになりました。

ただ、リストから確定できない中間部分にどちらの像を配置するべきか分からず、正解にはたどり着けませんでした。

F問題

あめふり君が構文解析できるということだったので、任せました。ただ、復号する際に先頭と末尾のどちらを消すのかが決められず、正解には至りませんでした。一見サンプルなら通りそうな考察まではあめふり君がしていたのですが、自分が反例を見つけてダメだということが分かりました。

G・H問題

難しそうだったので深く読んでいません・・・

感想

結果は3完、109位となりました。欲を言えばもう1問通したかったのですが、難しいですね。反省点としては、どの問題を通すのにも予想以上に時間がかかっていたので、練習量が明らかに足りない点が挙げられそうです。また、オンラインでは進捗状況が共有しにくかったので、対面で参加したほうが有利なのではないかと思いました。

去年の時点では今年参加するのか不確かな状況でしたが、引退したにも関わらず部の人達が誘ってくれたお陰で無事参加することができました。本当にありがとうございます！！

自分は院進しないので、今回が人生最後のICPCとなりました。悔いの残る結果でしたが、これからも別の形で競技プログラミングを楽しんでいきたいです。

2022-06-12

AHC011参加記

AHC011に参加した感想です。

はじめに

まず問題文を読むと、空きマスを上手く動かして木を作る問題のようです。もちろん木とは言ってもグラフの木です。そんなことできるのか？というのが始めに思ったことでした。

ビジュアライザを見る

文章で読んでもよく分からないので、次にWeb版ビジュアライザを見に行くことにしました。 seed=0の初期状態でもscoreが71429となっていました。どうやらどこかが木になっていればOKのようです。

また、共有された画像を見ると木が完成している画像が多数出てきました。どうやら木を作るのはアルゴリズム的に可能なようです。

このパズル、どこかで見覚えあるような？

空きマスを動かして絵を完成させるパズルをどこかで見たはずなのですが、名前が分からないので検索できないことに気付きました。ただ、OpenSiv3Dのサンプルプログラムの中に載っていたことを思い出したので、それを確認しました。どうやら「15パズル」と呼ばれるもののようです。15パズルで検索すると、解法が色々出てきました。完成図さえ分かれば、木を完成させることは可能ということでした。ただし、木を作ることができなかったので、15パズルの解法を使うことはありませんでした。

ランダムに動かす

木を作る方法が分からないので、とりあえずランダムに動かしてみて得点が上がるならその操作を採用するという方針で実装してみることにしました。

まずは何も操作しない場合を試してみます。

Submission #32106280 - AtCoder Heuristic Contest 011

得点は2869199でした。

次に、試しに操作して点数が上がるならばその操作を採用し、どの操作でも点数が同じならばランダムに操作するように実装しました。ここまで来ると、最初に空きマスがどこにあるか探す関数を作ったり、評価関数を作ったりとヒューリスティックっぽく？なってきました。評価関数については木のサイズが大きいほどスコアが上がるという条件だったので、UnionFindでそれぞれ木のサイズを求めて、最大値を返すようにしました。すると、得点は5695968になりました。最初は実行時間制限に間に合うか分からなかったので操作回数を上限の1/3に抑えていたのですが、どうやら余裕で間に合うようです。上限まで操作するようにしたところ、得点は6502898になりました。

ビジュアライザで確認する

これはかえでさんのブログを読んで、この方法は良さそうだな～と前から思っていた方法です。

実録！MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）参加記 - 競プロ始めました

ビジュアライザを活用し、seedの値を色々変えてバグを探すというものです。本来ならseedを0から100まで全部試すほうが良いのですが、面倒なので切りの良い数字だけ試しました。明らかに得点が低かった例は、seed=10の場合です。

このように閉路を持つグラフがある場合、その部分が塊のようになって、スコアが下がってしまうようでした。そこで、閉路を解消するように評価関数を変えました。幸い、UnionFindを使っていたので閉路検出は簡単に実装できました。

閉路検出を使った実装を提出すると、得点は6656767になりました。期待したほど伸びていません。ただ、もう一度ビジュアライザを確認すると、確かに閉路はなくなっていることが確認できました。（なぜ得点が伸びなかったのかは不明ですが……）

回数を増やす

ここで、実行時間に注目するとわずか30~40ms程度で終了していることが分かりました。そこで、「与えられた初期の盤面から空きマスを移動させて得点を伸ばす」という処理を複数回(20回程度)独立して行い、その中で一番高得点だったものを解答として出力することにしました。その結果、得点は8852284になりました。この方法は上手くいったようです。

移動を効率化する

ここまでランダムに空きマスを動かしてきたのですが、よく考えると上に移動した直後に下に動かしたり、左に動かした直後に右に動かしたりするのは無駄ということに気付きました。そこで、直前の移動を打ち消してしまうような移動となった場合は移動させず、操作回数としてもカウントしないという実装にしました。また、評価関数の実装を変えて閉路が存在する場合は得点を減点するようにしました。これにより、より積極的に閉路を解消するようになりました。

提出したところ、最初はバグで操作回数を超えてWAになったり、実行時間制限に間に合わせる目的で試行回数を20回から 10回に減らしたために得点が下がったりしました。しかしそれらを修正した結果、得点は約9000000点（システムテストによって得点が書き換えられたので正確な点数は不明）となりました。

まとめ＆反省点

システムテストの結果、得点は547024686点、順位は486位となりました。反省点としては、問題文をよく読むことが挙げられます。実行時間制限を2秒だと思い込んでいたり（本当は3秒なのに、終わってから他の人の解説を見るまで気付かなかった）、パネルの規則性を読み落としていたり（自力で思いついて勝手に感動していたけど問題文にちゃんと書いてあった）、木ではなくただの連結グラフを作っていたり……

次回は、もう少し順位を上げたいですね。

2022-04-18

ZinniaをRaspberry Piにインストールする

オンライン手書き文字認識エンジンのZinniaをRaspberry Piにインストールする。

本体のインストール

前提条件は次の2つ。

g++が使える。
文字コードはLFにする。(CRLFではconfigureが壊れる)

次のコマンドを実行する。

$ git clone https://github.com/taku910/zinnia.git
$ cd zinnia
$ ./configure -build=arm
$ make
$ sudo make install

認識モデルのインストール

Zinnia download | SourceForge.netから、認識モデル(zinnia-tomoe-0.6.0-20080911.tar.gz)をダウンロードする。

$ tar zxfv zinnia-tomoe-XXXX.tar.gz
$ cd zinnia-tomoe-XXXX
$ ./configure

Makefileの中から、handwriting-zh_CN.modelやhandwriting-zh_CN.model.txtなどを消す。

$ make
$ sudo make install

以上でインストールは完了。

実際に使う

taku910.github.io

上の記事を参考にコードを書く。コンパイル時は

g++ Main.cpp -lzinnia

として、zinniaをリンクさせる。

参考資料

taku910.github.io

www.servernote.net

qiita.com

2021-11-06

ICPC2021国内予選参加記

今年もICPC国内予選に参加しました。

今回のチームメンバーはあめふり君とパーシー君です。

去年と同様オンライン形式だったので、メモ帳代わりにhackmd、通話はzoomを使ってやり取りしました。

A問題

恐らく簡単だろうと思って問題を読まずにパーシー君に押し付けました。ごめんなさい。特に引っかかることなく通してくれたので助かりました。

B問題

あめふり君が解きたいと言ったので任せました。ここで時間を浪費してしまいました。何もアドバイスできなくてごめんなさい。

C問題

去年や一昨年のC問題はそこまで難しくなかったので、今年も解けるだろうと思ったら全然違いました。がっつり構文解析で困りました。+のところはどうしようもないですが、-のところは入れ替えることで値が変化します。引く数をできるだけ小さくすることで最大化できそうですが、それ以上のことは分かりません。

D問題

C問題とは違って問題文も比較的単純で一見解きやすそうでした。実際、A, Bの次に正解チーム数が多かったので、ずっと考えていました。

まず風船を多い順に並べてみました。しかし、実装してサンプルを試すと1人少ない結果が返ってきてしまいました。そこまで単純ではなかったようです。サンプルを手作業で実験したところ、

4 3 3 3 3 4 3 3 1
↓3人に渡す
1 0 0 3 3 4 3 3 1
↓1人に渡す
0 0 0 2 2 4 3 3 1
↓2人に渡す
0 0 0 0 0 2 3 3 1
↓2人に渡す
0 0 0 0 0 0 1 1 1
↓1人に渡す
0 0 0 0 0 0 0 0 0

とすると、9人に渡せるようです。残念ながらここまでしか分かりませんでした。何か法則性がありそうなのですが……

E問題

ここが一番時間をかけるべき問題だったのかもしれません。問題文を一通り読むとダイクストラ法で解けそうです。そこで、手元にあったダイクストラ法のライブラリをこの問題の形式に合うように改造していきました。

途中でpairをtupleに書き換えるところで詰まりました。pairでは.firstなどを使えたのにtupleにはそのようなものは存在しなかったのです。ここで、tieを使えばいいとあめふり君が教えてくれたので、その通りに実装することで要素を取り出すことができました。ただ、最初tie(pf, v, pt) = p;　とすべきところをtie(pf, v, pt)　としていて、segmentation faultが発生していました。

実装が終わってサンプルを試したところ、答えは合いませんでした。残念ながらここで時間切れとなってしまいました。

結果

2完、151位でした。去年より順位が下がってしまいました。

感想

ICPCは実装が重めなので、簡単なA, B問題だけでも過去問を解いて慣れておくべきでした。また、構文解析をある程度練習しておけばと後悔しました。

今年まではサークル[*1]のメンバーと出ていたのですが、今年で引退なので来年はどうなるか分かりません。いずれにしても、これからも競技プログラミングを楽しんでいけたらと思っています。

最後まで読んでいただき、ありがとうございました。

*1:正確には部らしいです