プログラムコンテスト

#include "check.h"
namespace Problem {
  bool makeRoute(const BridgeList& bridgeList, Route& route)
  {
    static int numProblem = 0;
    if( numProblem < 100000 ) {
      numProblem++;
      // 普通のプログラムを書く。ただし、20000程度のスコアを取る速度は必要かと思われます。
      // return 文まで含める。
    }
    return false;
  }
}

オイラーの定理

Fleury (フラーリー) のアルゴリズム

BridgeList bridgeList; // 橋のリスト。問題で与えられたやつ。
int        steps = 0;  // 渡る島を何個記録しているか。

void fleury(int island)
{
  for( i = 0 ; i < bridgeList.size() ; ++i ) {
    if( bridgeList[i].isletA == island ||
        bridgeList[i].isletB == island   ) {      // 渡れる橋が見つかった場合
      int nextIsland = bridgeList[i].isletA + bridgeList[i].isletB - island; // 対岸の島番号を記録
      bridgeList.erase( bridgeList.begin() + i ); // 今渡った橋を消す
      fleury(nextIsland);                         // とりあえず渡る
    }
  }
  
  // island番目の島から移動できなくなったらその島を記録
  route.set(steps++, island);
}

解答用プログラムを作る前なのに、練習用の問題数が足りないと思って問題を作るプログラムを組んでしまいました。使い方は

$ ./makeprob <ノード数> <平均接続数>

パラメータに関してですが、ノード数はそのままの意味で、平均接続数とは1つのノードに繋がるエッジの平均数です。 プログラムの中身としては全体で (ノード数)*(平均接続数)/2 本のエッジをランダムにかけているだけです。

実験してみた結果、元のサンプル問題と同じ程度の難易度の問題にするには

通信関係

解法関係

while(時間が来るまでループ) {
  初期解を作る
  for( clearcount = 0 ; clearcount < clearcountの上限となるパラメータ ; clearcount++ ) {
    解を更新する(サンプルプログラムとほぼ同じ)
    score = 新解のカット数を数える
    if( 自己ベスト < score ) {
      最良解を更新する
      clearcount = 0;
    }
  }
  if( 知っている中での最小カット数 > 自己ベスト ) {
    マスターに自己最良解を送信
    自己ベストのカット数をGXPで知らせる
  }
}

while(無限) {
  解を得る();
  AnswerAPI();
}

while( 時間 < 制限時間 ) {
  usleep(10);
  時間取得API();
}

感想

超易問。0問正解のチームは、そもそもやっていないか、Submitがうまくいかないかの2択だと思います。大雑把に言って2通りの解答方法が挙げられます。

まずは素数判定用の関数を作り、a,a+d,a+2d,… と順番に素数判定にかけていく方法。大半の人はこの方法でやったんじゃないでしょうか。そんな流れで作ったソースを載っけました。

もう一つは、数の範囲が100万未満ということから、エラトステネスの篩でも使って100万未満の True/False 表を作っておき、素数判定を表引きで行う方法。最初の表を作るのに多少時間がかかるかも知れないが、Inputデータが極端に多い場合はこちらの方が総時間としては速いはず。優勝したMakegumiはこちらの方法だった。

易問。でも自分は'+'を文字列に含むんだと勘違いしてTimeOverした。

C++で書いている場合にはstirngクラスとSTLのsetが役に立つ典型例。1:n-1～n-1:1に切り分け、前半、後半、両方を逆転させて再接続した文字列を詰め込んでいくだけ。Cで作っていると以前作ったものとの重複を管理するのが面倒になる。Javaだと…知らない。

難問。見かけ倒し…というと語弊があるが、実はパッと見で想像する程には難しくない。ただコーディング量がかなり多くなる。

基本的な考え方は詰めオセロみたいな感じ。初期状態から動かせる範囲を列挙→そこから動かせる範囲を列挙→…みたいに繰り返す。接続が切れる条件や死ぬ条件を考えると意外に探索範囲が狭いのでこんな横型探索でも十分行けるはず。ただし重複の可能性があるのでC++のsetをお勧めしたい。

問題なのは、1ステップ毎のループと、どの節を動かすかというループがあること。混乱せずに解いて欲しい。

普通。慌てず、騒がず、きちんとシミュレートすること。

私の実装では、再帰呼び出しをする際に石の現在地と何手目なのか、という情報だけ渡している。しかも縦型全探索。氷が隣接していたり石が落ちたりして意外に枝狩りが頻繁におきるらしい。

バックトラックする際に消した氷を元に戻すことを忘れないよう気を付ければ難しくないと思う。

普通問。単純に、与えられたままに文字列を展開しようとすると(サンプルの4問目とかで)メモリが足りなくなること必至。そこで別の工夫が必要となる。

リスト構造を作るのが本質的な解答だろうか。ループ用と文字列用の2種類(を内部で見分けられる)構造体を用意し、文字列をパージングして後はひたすらツリー構造を辿りまくる。

その際に、ループをどう処理するかが時間的に問題になってくる…はず。単純に1文字ずつ追っていって間に合うのかな？十分間に合います。想像で言うが、ループ用構造体ではループ内の文字列長を記憶しておくと速く処理できる気がする。

上においている実装では構造体を作らずstringクラスを事ある毎にコンストラクト＆デストラクトしているので見にくく、遅くなっています。

超難問、と言われているがどうなんだろう。実際に与えられる問題データを試していない(下記で述べる方法でAccept取れるなら)私からの印象としては、CやEと同レベルの難易度。とりあえず問題データを通してみたい。正解するプログラムじゃなければタダの机上の空論だから。

解析的な解法が思いつかないので数値解を兎に角やってみる。2案。

どちらの手法も、基本的には角度θによる長さを与える関数f(θ)が連続、かつ微分結果がでかい区間は無いものという想定がある。要するに10^-3π程度に小刻みに探索すれば大丈夫だろう、という前提だ。

…とかいろいろアルゴリズムを考えてたけど、本当に重要なのはそこではなく有効桁数では？ということに思い至った。実際、double→long doubleに変更したら型以外は全く同じプログラムで成功している。θに関する精度が求められているのに、比較すべきなのが影の長さというのでdoubleの有効桁数(15桁ちょい)とεの差が消えたのでは？

1/10000スケールで段々狭く…案

局所解から全て正確に求めよう…案

#include "answer.h"
#include "check.h"

typedef struct Board Board;
void answerCrossWord(Board* board)
{
  int i, j, size = board->size;
  Board* ans = board - 1; // 配布コードでは ans = board + 1;
  for( i = 0 ; i < size; i++ ) {
    for( j = 0 ; j < size ; j++ ) {
      board->cell[i][j] = ans->cell[i][j];
    }
  }
}