No Such Blog or Diary

寝付けないので自前で考えた解き方を試しに実装してみた．解説聞いてないので合ってるかどうかは知らんけど．

A: LinkedList で普通に要素を抜いてくだけ．最大サイズでも一瞬で終わるのでこれで問題なさそう．

B: エラトステネスのふるいで素数求めたら終わり．与えられた数から前後の素数を探索するのは前後を順に見てくだけでいい．

どうせすぐ近くに素数があるだろうから．

C: 状態遷移行列を T乗すると考えるかT回の状態遷移を計算すると考えるか…　状態遷移行列が疎なのでグラフ上で状態遷移をシミュレートするイメージの実装．スタートに戻るマスへの遷移はスタートへ足しこむ．一回休みは一回休み用のノードを作って一度そのノードへ遷移するようにする．計算量は O((N+L)T) なので時間も問題ないでしょう．

D: 面倒なので考えてない．一つの三角形を決めたら他も決まるから全部の点を試せばいいのかな？

E: これもグラフを作るまでが面倒．グラフさえできれば最短路なので楽．

F: ソートした辺のリスト上で最大重み用のポインタと最小重み用のポインタをスライドさせてく．二つのポインタの間にある辺集合で全域木が作れるなら最小のポインタを進める．作れないときは最大側のポインタをするめる．全域木ができるかの判定は連結しているかの判定でできるので適当に Unon/Find でやった．これで全体としては O(E^2) だけど…　手元では最大サイズが一秒以内なのでギリギリオッケー．

G: 状態空間のサイズが 2^24 程度なので普通に幅優先でいい気がする．ただ最大サイズのサンプル入力で４秒かかるのでもう少しコードを特化した方がいいかもしれない．

H: 再帰下降で Exception なげて帰ってくる．Hashtable とか使わないとインデックスで困るけどそれだけだと思う．

I: 面倒なのでパス．多角形を周りから削っていって最後に残ったところか？何となく島が海に沈んでくイメージ…

J: 連立方程式立てて解けば終わりなのだけど…　有理数で一次方程式を解かねばならないし（doubleとかでもいいのかな？），そもそも方程式の係数を求めるのも面倒．コード書きたくないから二乗根の場合に関して手で解いてみただけ．久々に 4x4 の一次式を解いた．

とりあえず，ABCFGH の実装に（テレビ見をながらではあるけど）５時間ほど．やっぱ９問解いたチームってのはすごいなぁ．

風船運びと後片付けがメインの仕事．今年の問題はA, B が異常に簡単だったので開始直後はこれらが出まくって忙しかった．でもこのスタートのラッシュを過ぎたあとはゆったりと風船を補給してただけ．ついでに途中で元気のなくなった風船の交換もあったけど　（例年こんなのあったっけ？）

あとは飾りのための風船を大量に膨らませたのは面白い仕事だった．というか他の人の仕事を奪ってしまったのだけど．とりあえず遅めの作業を見ていたら思わず手を出していた…

そういやコーチと選手が廊下やトイレで接触しないように見張る仕事もあったなぁ．もう少し場所のアレンジを考えてほしいと思う．コーチは二階席から見るようにするとか．そもそも仕事マニュアルに書かれてなかったなので接触の可能性に後で気づいたんでしょう．今回の大会は全体的にスタッフ陣のアレンジが甘い印象を受けた．まあ大変なんだろうけど．

裏方の仕事って結構大変（面倒）だったんだなぁと実感．英語の受け付けも結構あたふたしてた気がする．シーツ配りもそれなりに重労働だったかな．

それはさておき，色々な部分でスタッフの準備というか対応が甘い点が多かった気がする．案内が無くて分かりにくい，効率の悪い作業をする，ジャッジとの間のプロトコルがおかしい，とか．ついでに名札にチーム番号書いといてほしい．変な札にだけ番号書いて渡すってのはどうかと．とにかく色々な部分の情報を取っといてマニュアルにできるものはしてしまえと思う．そうすりゃ回を重ねるごとに改善されていくだろうから．とくにＰＣの用意の仕方とか受付とかの対応とか風船の用意の仕方とかどうにかしてほしい．

頭をぶつけたら血が…　　蛇口ごときに負けるとは情けない．

住民票と違って証明願に書いた事項が住民票と同じことを証明するものらしい．ふつうはもらって来いと指令するところが様式を用意するようだけど…　特定の様式ないけどもらって来いと言われた場合どの事項が必要なのやら？　とりあえず必要項目を聞いてみるか…　二度手間だ．

キーで認証するのがうまくいかない．普通にプライベートキーを変換して認証キーの設定をしただけなのに．何が悪いんだ？しばらく格闘するか．