Twitter

Accounts

巡拝

  • 2015/01 関東三十六不動尊結願
  • 2015/04 江戸三十三観音満願

資格等

  • 英検2級
  • 漢検2級
  • 文検4級
  • 普通自動車AT
  • Master of Integrated Biosciences
  • 日本バイオインフォマティクス学会認定バイオインフォマティクス技術者

  • 以下は受験料が無料だった時に適当に取ったので誇ることもない。

    • Yahooデジカメエキスパート1級
    • Yahooタイピングエキスパート6級
    • (日本将棋連盟)将棋1級

CodeIQ出題

CheckiO

競技プログラミング等

Judge Rate
TopCoder 1016 (緑のまま引退の危機)
Codeforces 1666 (青が1600-1899になったので引退しました)
HackerRank 2303
AtCoder 1700程度
yukicoder Lv 75
AOJ 658問
POJ 275問
CodeIQ バッジ数・スキルピース数トップ
paiza paizaマスター、言語マスター
CheckiO 全問解答
8946 残3問
(少なくとも表彰式が)オンサイトの大会 (成績)
RProcon 2013
CodeSCORE 2014 本選単独満点・優勝/50
Code Formula 2014 本選36位(銀賞)/100
CODE FESTIVAL 2014 112位/200、あさプロ Middle23位(銀賞)/100
Data League 2014 本選17位/18
Code Runner 2014 本選19位/100
CODE FESTIVAL 2015 116位/200、あさプロ Easy7位(入賞)/100 Middle77位/70+α
Data League 2015 12位/46
Code Runner 2015 本選33位/100
CODE FESTIVAL 2016 84位/220、Elimination Tournament Round3進出

音楽ゲーム

ゲーム ID 成績
[TAITO]
グルーヴコースター AC:asn66m4n CS(Android):約2000位。(機種変更回数の上限を知り絶望)ほぼ引退。
AC:500位台。Perfect6、S++51
[SEGA]
maimai 9.74
chunithm 2037702683463 12.58
DIVA CWAAQK79AD
[BNEI]
太鼓の達人 532629126552 モモイロ初級(苦笑)
シンクロニカ 46fade365cce05f806f0445be25bfd761acb2400
[CAPCOM]
crossbeats 51486150 2016/10 RP1600達成
crossbeats REV. 76435928 Class III RP1345.87
(Cytus)
[KONAMI]
jubeat saucer 57710108066051 3.50
jubeat prop 60930017972907 Step 15
jubeat qubell 60930007106643 Stage 5クリア
Reflec Beat VOLZZA RB-6564-2108 CLASS 8
DDR 41242214 Enjoy LV 18
弐寺 3492-2945 (pendual) SP7級、step up ED1
pop'n 4392-2014-5346
BeatStream Beast Rank9
SDVX SV-2080-7171
museca Curator Rank12
GD 0009ee6234 iOSは1600取って放置、ACは引き継ぎだけした(スキルポイント引き継がれないの…?)
[他]
ちくたくコンチェルト 0364886461 exc54
はちはち (削除済)

作ったもの

URL
cTouch https://github.com/cielavenir/ctouch/
https://sourceforge.net/projects/ctouch/
picrawler https://github.com/cielavenir/picrawler/
R on iOS (記入時点でrwikiが落ちている…何たること…)
http://rwiki.sciviews.org/doku.php?id=getting-started:installation:iphone
R on Android http://rwiki.sciviews.org/doku.php?id=getting-started:installation:android
Google TwoFactor Authenticator on PSP http://qiita.com/cielavenir/items/a13215069306eeaa24bf
qinstall https://github.com/cielavenir/qinstall
Ruby multisax https://github.com/cielavenir/ruby-chan
https://github.com/cielavenir/mruby-chan
Ruby chan (bidirectional iterator) https://github.com/cielavenir/multisax
gyao_url_another.rb https://gist.github.com/cielavenir/a858255c4009ecbb9b67
install_npapi.sh/install_ppapi.sh (OSX Flash) https://github.com/cielavenir/flashupdate

発見したバグ

  • mdbtools
    • ODBCドライバにおいて、(MicrosoftAccessと違い)DBQ引数が取れない
    • ODBCドライバでマルチバイト文字列が扱えない
  • ExGame (モバゲーのFlashランタイム)
    • Android Chrome/iOS6で文字が表示できない
  • RVM
    • 古いMac(本来i386だがboot.efiハックでx86_64化が可能なモデル)をMountain Lionにアップデートした時に、カーネルがx86_64に切り替わるが、libyaml.dylibがi386のまま正しく読み込まれず、x86_64用にリビルドもされない
  • Google Chrome
    • filesystem APIのクオータ要求時に警告バーが出るが、この要求を機能拡張のポップアップ画面内で行うと警告バーが出る代わりに(親ごと)クラッシュする
  • 嫁コレ
    • APIトークンにIMEIをハッシュではなく暗号化したものを用いているため、嫁コレサーバー側で生IMEIを取り出すことができる。一部通信はHTTPで行われているため盗聴も可能である
    • 3.4.xで修正された
  • 東京100ガイド
    • WiMAX環境で使用できない
    • 修正済み

イラスト

  • deviantART (私のtwitterアイコン原画等。限定公開)

背景

  • ファミリーマートやローソンのネットワークプリントはプリンタドライバが存在するが、セブンイレブンのネットプリントはプリンタドライバが存在しない。
  • ECCS2012(ゼロックス)のプリンタドライバはネットプリントドライバとしても使うことが出来た。
  • 現在のECCS2016では業者がリコーになったが、ネットプリントドライバ部分はまだ使えるのではないか?
  • しかし、使ってみようとすると、接続エラー(320000)となる。

調査

  • /Library/Printers/FujiXerox/FXCampusGatePrinter/FXCampusGatePrinter.plist から、
  • https://sdb.fujixerox.co.jp:443/CGPPrintPortal/Service.svc
  • という内容が読み取れる。このサーバーは現在停止している。
  • したがって、ネットプリントドライバとして使うことも現在は不可能である。

結論

  • 個人的には当面はネットワークプリントだけを使うことにします…

https://agc009.contest.atcoder.jp/tasks/agc009_b

概要

  • トーナメント戦を行ったところ、1番の選手が優勝した。
  • 他の選手について、誰に負けたのかが与えられるので、条件をみたすようなトーナメント表の深さの最低値を求めよ。

考察

  • ある選手がどの選手を倒したかのグラフを作成し、1番の選手から再帰。
  • 倒した選手(N人)のそれぞれについてトーナメント表の深さを求めようとする(倒した選手がいなければ0)。
  • 深さを降順にソートし、これらに1からNまでの数値を割り当てて、足す。
  • 足した後の配列の最大値が答えである。

再帰の深さ

  • 単純に実装すると、最悪10万回の再帰が必要になり、スタックオーバーフローになるおそれがある。
  • 今回、C++は 偶然 大丈夫であったが、RubyやPythonだと不可であった。
    • スタック拡張テクを使っても依然として通らない。
  • 今回は場当たり的(テストケース依存)な対応になるが、N/2番の選手から一旦再帰しておくことで再帰の深さをある程度減らすことができる。
    • この状態でもスタック拡張テクは依然として必要である。

解答例

余談

http://www.adventar.org/calendars/1388 の12/10分です】

高校

東大はBランクだったが、記念受験とした結果実力を出し切れたらしい。(現役)

学部

今の研究室には学部時代の体験ゼミでお世話になった。生物とコンピュータを両方取り扱う分野ということで興味を持った。 学部の研究室は、今の研究室の教授から紹介してもらった。割と良い論文が書けた。

修士

割と良い論文が書けた、とあるが、これは学士の水準である。これを修士の基準に持っていくのは不可能であった。 1個目のテーマは論文を書いたが、学士よりも酷い内容だったので捨てた。 最終的なテーマを決めるのには結局2年半かかった(※1留)ということになり、半年で修士論文を書いた。こちらはまあまあの出来だった。

博士

博士号取得要件は、論文を査読付き雑誌に掲載することである。 修士論文のテーマでは不可能だった。 結局まともな研究を始めたのは2年秋だった。 博士3年の初めにfastqの話で論文を書いたが、内容に不備があり、修正叶わず投稿には至っていない。 予備審査は通して頂けたが、本当にやる気のある学生なら1ヶ月で仕上げられられる内容の研究しかしていない。 データの不足を痛感しつつも、親の希望により職に就くこととなった。


というわけで2017/3を以って単位取得退学となる。まずは3月までに雑誌に投稿できるかが勝負である。

http://yukicoder.me/problems/no/457

概要

  • 間に部分列^^*を含むような(と)の組み合わせの個数を求めよ。
    • reverse.tr('()',')(')なる処理を加えれば右向きを別に考えなくて良くなる。

考察

O(S2 logS)

  • (と)の組み合わせをすべて求めて、それぞれに対し、^^*が含まれることを判定します。
  • まず^^が含まれる一番左の座標を求めます。
    • その座標までに含まれる^の個数を累積和として持ち、(の座標における累積和+2を2分探索します。
  • 次に、その座標から)の座標までについて、*が含まれるかどうかを2分探索します。
  • 以上によりO(S^2 logS)となり、C++では通すことができます。
    • 本家解説によると愚直解はTLEらしいですが、2分探索に落とし込んだことが功を奏したのでしょうか。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int solve(char *s,int len){
  vector<int>al;
  vector<int>ar;
  vector<int>ah(len);
  vector<int>ast;
  for(int i=0;i<len;i++){
      if(s[i]=='('){
          al.push_back(i);
      }else if(s[i]==')'){
          ar.push_back(i);
      }else if(s[i]=='^'){
          ah[i]++;
      }else if(s[i]=='*'){
          ast.push_back(i);
      }
  }
  for(int i=1;i<len;i++)ah[i]+=ah[i-1];
  int ret=0;
  for(auto &l:al){
      for(auto &r:ar){
          if(l>=r)continue;
          int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
          if(hidx>=r)continue;
          auto st=lower_bound(ast.begin(),ast.end(),hidx);
          if(st!=ast.end()&&*st<r){
              ret++;
          }
      }
  }
  return ret;
}
char s[10001];
int main(){
  scanf("%s",s);
  int len=strlen(s);
  printf("%d ",solve(s,len));
  reverse(s,s+len);
  for(int i=0;i<len;i++){
      if(s[i]=='(')s[i]=')';
      else if(s[i]==')')s[i]='(';
  }
  printf("%d\n",solve(s,len));
}

O(SlogS)

  • 以下、最も重いループの計算量を減らすことを考えます。
  • まず、rは単調増加であるため、st!=ast.end()&&*st<rが一度真になれば、そのループの中では常に真になります。よってキャッシュすることができます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(auto &l:al){
  bool f=false;
  for(auto &r:ar){
      if(l>=r)continue;
      if(f){ret++;continue;}
      int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
      if(hidx>=r)continue;
      auto st=lower_bound(ast.begin(),ast.end(),hidx);
      if(st!=ast.end()&&*st<r){
          ret++;
          f=true;
      }
  }
}
  • さらに、hidxおよびstはrに依存しないため、ループrの外で計算しておいて問題ないことがわかります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(auto &l:al){
  // if hidx>=r, l>=r is assured because hidx>l.
  int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
  // if hidx==ah.size(), st==ast.end() is assured because hidx==len.
  auto st=lower_bound(ast.begin(),ast.end(),hidx);
  bool f=false;
  for(auto &r:ar){
      if(f){ret++;continue;}
      if(st!=ast.end()&&*st<r){
          ret++;
          f=true;
      }
  }
}
  • arのループはFF...FFTT...TTのようになるので、このTになる場所を2分探索できます。
1
2
3
4
5
6
for(auto &l:al){
  int hidx=lower_bound(ah.begin(),ah.end(),ah[l]+2)-ah.begin();
  auto st=lower_bound(ast.begin(),ast.end(),hidx);
  if(st==ast.end())break;
  ret+=ar.end()-lower_bound(ar.begin(),ar.end(),*st);
}
  • 最後に、範囲を狭めるためのtweakを入れます(必要ではありませんが…)。
1
2
3
4
5
6
7
8
auto ist=ast.begin();
auto ir=ar.begin();
for(auto &l:al){
  int hidx=lower_bound(ah.begin()+l,ah.end(),ah[l]+2)-ah.begin();
  ist=lower_bound(ist,ast.end(),hidx);
  if(ist==ast.end())break;
  ret+=ar.end()-(ir=lower_bound(ir,ar.end(),*ist));
}

O(S)

  • 動的計画法によりO(S)に落とせるようです。コードがより短い実装はそうなっているものが多いようです。

https://cf16-relay-open.contest.atcoder.jp/tasks/relay_k

概要

  • 問題文がそれなりに読みにくい。
  • いわんとしていることは、選んだ頂点については2回通ってはならないということである。この状況で選ぶ頂点の数を最大化すれば良い。
  • 答えは木の直径以上になることは容易に想像がつく。

考察

  • 枝分かれする(辺が3本以上ある)頂点については、つながっている辺の先にある葉(辺が1本ある頂点)を選んだほうが良いのは明らかである。
  • 問題は辺がちょうど2本ある頂点であるが、木の直径上にある頂点を選ぶ方法でサンプルは通る。
  • しかし、たとえばこういう入力の場合、sub-optimalになってしまう。
1
2
3
4
5
6
7
8
9
o-o-o-o-o
    |
  o-o-o
    |
  o-o-o
    |
  o-o-o
    |
    o
  • 対処するには、木の直径を求めるコードを変形し、頂点の重みを、辺が2本ある場合のみ1に、それ以外は0とすれば良い。

解答例

感想

  • これを時間内に思いつくのはやはりすごいと思いました…

参加記です。

予選

  • A: C早解きでぎりぎり通過。ただし、剰余のあたりバグらせてしまい若干危うかった。
  • B: 本番の時間では参加しませんでしたが、自力で解けたのはBまででした。
  • C: (同上)、自力で解けたのはAだけという悲惨さ。
  • 予選Aで通って本当に良かった…。

11/8

  • 博士予備審査を通す。まあ、退学は予定していましたが、予備審査は通したかったので。
  • ちなみに通っていなければ 本選辞退案件 でした…

水曜日〜金曜日

  • この時期にバス旅行とか色々とあれ。
  • 本選ページを見て、パーカーボーダーに愕然とする。ABCD+E部分点が必要。
  • 実は一回スーツケース(含PC)をホテルに忘れかけそうになった(これも 本選辞退案件 )

1日目

  • 9:50起床、 Code Festivalの伝統的正装とされるパーカー を来て出発。汐留のサブウェイで食べようと思ったけど中止。結局昼食は歌舞伎揚げで済ませた。
  • スタンプラリー、今年はないみたい。スケジュールを巻かなくてよいので楽。
  • 席、学年順なんですか?老人を固めるのはやめてくだされ。

本選

時間 言語 問題(A-J) コメント
0:02 Ruby A WA
0:07 Ruby B 順番に足していって後で1問だけ消せばいいでしょ AC
0:12 Ruby A H,Wを逆に取るくそミスに気付く。 AC
0:15 D 最大マッチングだと思ったけど、制約がでかすぎるなぁ。
0:30 C++ C 言語についてUnion-Findして根の数が1ならいいよね AC
0:45 C++ E 個数と速度について幅優先探索。TLE
0:58 C++ E 色々手を尽くすも依然TLE
1:02 C++ E 枝刈りの仕方を改善。RE (部分点制約に合わないなら切腹する意味なのでREでOK)
1:30 Ruby D 全部のチーを取ってから残りのカードでできるだけポンする。多分嘘解法。AC パーカー確定 。軽食を取る。
2:45 C++ E unordered_mapいらなかったんや…少しつらい^^;;
3:00 あとは座るだけ。84位。お疲れ様でした。なおパーカーボーダーは124位。少し減りましたねぇ
  • D問題、嘘解法だと思っていたのが想定解法だったらしく、びっくり。今年も運が良かった。
  • 帰宅してから思ったけどDは一般マッチングであって二部グラフじゃないですよね…

夕方

  • tourist氏トークライブ。
    • everything except gifted brain
    • FAR Manager (そこか)
  • 体力測定。11ptだった。だめすぎ。
  • ペアプロライブ。二人ゲームは難しいです…。でもコードは短いという…
  • エキシビション、さらに難易度上がってませんか。
    • sevenkplus氏が、tourist氏のPCのFAR Managerの使い方がわからず苦戦していた模様(そこか)
  • リレー顔合わせ。自己紹介(英語)がぐだってしまった。
    • ショートコードランキングについて。丸写しはまれですが、 写経はそれなりにしてます。すみません。

  • 起床フェーズがやばいことは明白なのに今年は宿泊なしですよ?酷いよ?
  • 特に理由もなくセガ神楽坂に寄ってから帰宅した。

2日目

  • 7:50起床。 コンテストはACだけど開会式はTLE

Elimination Tournament

Round1 (group19)

時間 言語 問題 コメント
0:11 Ruby B メモ化再帰。WA
0:26 C++ A 2頂点からPrim法。WA
0:28 Ruby B off-by-oneエラーだった。 400点 1位通過、Round2進出
  • A問題、後で確認したら、long long案件だった。これは酷い。

Round2 (group10)

時間 言語 問題 コメント
0:01 Ruby A 自明解。 200点
0:09 Ruby B 愚直解。 200点
0:30 かろうじて逃げ切れました。4位通過、Round3進出

Round3 (group5)

時間 言語 問題 コメント
0:08 Ruby A 最大K個を拾う。当然誤解法。
0:12 Ruby B N-S.index('m')個の中の最大を取って、その最小では? → WA
0:30 0点。くそすぎました…

まあ、下以外のステッカー、計3枚もらえてうれしかったので、その場で貼ってしまいました。

  • 知床鮨。
  • LT。きゅうりさんの擬人化の よさみ
  • 休憩時間にちょろっと退出しUFOキャッチャー。まあ、1回のトライではタオルはおろか何も取れるはずはない。ご苦労様でした。
  • りんごさんの挑戦状。おもしろかった。

早解きリレー

  • W4yneb0t氏のチームでした。
  • Tシャツの色、不幸にも去年と同じ色…。あの色を2着というのは厳しい…。
  • ゼッケン。アルファベットにしてくれと去年要望出したのにどうしたー。
  • 順位順でGを担当。思いついた解法がどう考えてもTLEだったが、状態を配列に取っておけばいいことを教えてもらった。実装は一発ACだった。
  • 9完でFinish。
    • 役に立てなくてすみません。 W4yneb0tさん、Grand Final優勝おめでとうございます。
  • Kは、最長パスの接点2の数+葉の数が答えらしい。

帰路

  • 他の人の実装見たりしていた。

まとめ

  • ゆっくり楽しめました。ただ、ゆっくりすぎて太鼓やらなかった(でもまあ太鼓はメイン機種じゃないのでいいか…)
  • お土産少なくないですか。パーカーあるからいいですが…

お土産

  • パーカー
    • 白だと汚れるので家宝として封印かなぁ。
  • 本選Tシャツ、リレーTシャツ(カーネーション?)
  • ステッカー(本選、トーナメント3枚)
  • トートバッグ
    • 今回も手提げショルダー両用
  • ボールペン、ノート

無矛盾な単位系

概要

  • 無向グラフが与えられるので、誤った閉路がないかどうか判定せよ。なお点は文字列として与えられる。

方法

  • まだ訪れていない点を調べる。
    • には深さ優先探索とありますが、実装が適切であれば幅優先探索でも大丈夫っぽいです。ただ、2倍ほど遅くなります。
    • memoに加えるのは、深さ優先探索では入れる時出す時のいずれでも良いですが、幅優先探索だと入れる時に加える必要があります。
    • 訪れていたら、最初に訪れた時の値と同じかどうか確認します。
  • なお、独立な単位系が複数存在するかもしれない(連結成分が1個ではないかもしれない)ので、グラフが空になるまで取り出し続ける実装にする必要がある。

  • コード(深さ優先探索と幅優先探索をベンチマークするためにdequeにしていますが、深さ優先探索だけで良いならvectorの方が速いです)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <string>
#include <cstdio>
#include <unordered_map>
#include <deque>
#include <algorithm>
using namespace std;
typedef string key;

char b1[99],b2[99];
void main2(int n){
  unordered_map<key,deque<pair<key,long long>>>m;
  for(;n;n--){
      int d;
      scanf(" 1 %s = 10^%d %s",b1,&d,b2);
      string s1=b1,s2=b2;
      m[s1].emplace_back(s2,d);
      m[s2].emplace_back(s1,-d);
  }
  for(;!m.empty();){
      auto s=m.begin()->first;
      deque<pair<key,long long>>st={ {s,0} };
      unordered_map<key,long long>memo={ {s,0} };
      for(;!st.empty();){
          auto p=*st.rbegin();st.pop_back();
          auto cur=p.first;long long d=p.second;
          for(auto &e:m[cur]){
              if(memo.find(e.first)==memo.end()){
                  st.emplace_back(e.first,d+e.second);
                  memo[e.first]=d+e.second;
              }else if(memo[e.first]!=d+e.second){
                  puts("No");
                  return;
              }
          }
      }
      for(auto &e:memo)m.erase(m.find(e.first));
  }
  puts("Yes");
}
int main(){int n;for(;~scanf("%d",&n)&&n;)main2(n);}

マス目と整数

  • 入力を変更し、連結成分重み判定を加えるだけで、マス目と整数の解答に変更することができる。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
--- utpc2010_10125(aizu2207)_stack.cpp    2016-10-13 04:19:40.000000000 +0900
+++ atcodercodefestival2016qualaD.cpp 2016-10-13 04:42:46.000000000 +0900
@@ -1,22 +1,22 @@
-#include <string>
 #include <cstdio>
 #include <unordered_map>
 #include <deque>
 #include <algorithm>
 using namespace std;
-typedef string key;
+typedef int key;

-char b1[99],b2[99];
-void main2(int n){
+int main(){
+  int r,c,n;
+  scanf("%d%d%d",&r,&c,&n);
  unordered_map<key,deque<pair<key,long long>>>m;
  for(;n;n--){
-      int d;
-      scanf(" 1 %s = 10^%d %s",b1,&d,b2);
-      string s1=b1,s2=b2;
-      m[s1].emplace_back(s2,d);
-      m[s2].emplace_back(s1,-d);
+      int s1,s2,d;
+      scanf("%d%d%d",&s1,&s2,&d);
+      m[s1].emplace_back(s2+r,d);
+      m[s2+r].emplace_back(s1,-d);
  }
  for(;!m.empty();){
+      long long a=-1LL<<61,b=1LL<<61;
      auto s=m.begin()->first;
      deque<pair<key,long long>>st={ {s,0} };
      unordered_map<key,long long>memo={ {s,0} };
@@ -29,12 +29,17 @@
                  memo[e.first]=d+e.second;
              }else if(memo[e.first]!=d+e.second){
                  puts("No");
-                  return;
+                  return 0;
              }
          }
+          if(cur<=r)a=max(a,d);
+          else b=min(b,d);
      }
+      if(a>b){
+          puts("No");
+          return 0;
+      }
      for(auto &e:memo)m.erase(m.find(e.first));
  }
  puts("Yes");
 }
-int main(){int n;for(;~scanf("%d",&n)&&n;)main2(n);}

あとがき

  • Code Festival 予選中、無矛盾な単位系が類似問題として頭に浮かんだのですが、当時書いていたコードが 一行入力するごとにグラフを全走査する くそコードだったため、どうしようもできませんでした。
  • 結果的には復習になってよかったです。
  • ただ、連結成分重み判定はやはり本番中に思いつかなかったと思います…

URL

結果

  • ---ox△△◎oo-oo△-ooo△△--△- 1752.66点で2位でした。

A:BonusMondai

  • 解いたらあかんやつやこれ
  • てか負の配点って設定できちゃだめやろ

B:NA RI KI RI knapsack

  • よくある問題だけど得点が謎。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
  int N,W;
  scanf("%d%d",&N,&W);
  vector<pair<int,long long>>v(N);
  for(int i=0;i<N;i++)scanf("%d%lld",&v[i].first,&v[i].second);
  vector<long long>bag(W+1);bag[0]=1;
  for(auto &e:v){
      for(int j=W;j>=e.first;j--){
          if(bag[j-e.first]&&bag[j]<bag[j-e.first]+e.second)bag[j]=bag[j-e.first]+e.second;
      }
  }
  printf("%lld\n",*max_element(bag.begin(),bag.end())-1);
}

C:Number Guessing Master

  • 8桁の数値の当該桁がヒットならACになるかと思ったけどそうでもなかった
  • 最初の4ケースがhit、後ろの4ケースがblowだそうです…

D:ポッポカウント(AC)

  • 素直に解いて良い。なおNの最大は100であるようだ。
1
2
3
4
5
6
7
#include <stdio.h>
int main(){
  long long N,i,j,R=0;
  scanf("%lld",&N);
  for(i=1;i<N;i++)for(j=i+1;j<=N;j++)R+=__builtin_popcountll(i*j);
  printf("%lld\n",R);
}

E:Hedgehog(TLE)

  • 入力拾うだけでTLEになる のでどうしたもんだろう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
  long long v[1000];
  long long R=0;
  int N,M;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
      scanf("%d",&M);
      for(int j=0;j<M;j++)scanf("%lld",&v[j]);
      std::sort(v,v+M);
      for(int j=1;j<M;j++)R^=v[j]*j;
  }
  printf("%lld\n",R);
}

F:ライツアウト(部分点)

  • 5x5を反転させるのでは満点にならないらしい。サイズ、いくらなんだろう。
  • 解説読んだけどあれはひどい–;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
0 0
0 1
1 0
1 1
1 3
1 4
2 2
2 3
2 4
3 1
3 2
3 3
4 1
4 2
4 4

G:Surprising Language(部分点)

  • Perlで解いたものをBashに埋め込んで210/300点。300点は難読言語専用かな?
  • Whitespaceで解くと満点なの?テストケース埋め込みが必要やん…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/perl
use feature qw(say);
use strict;
my($x,$y)=split(/ /,<>);
my $M=10**9+7;
my @I=(1,1);
my @F=(1,1);
my @R=(1,1);
for(my $i=2;$i<=$x;$i++){
  my $z=($M-($M/$i^0))*$I[$M%$i]%$M;
  $I[$i]=$z;
  $F[$i]=$i*$F[-1]%$M;
  $R[$i]=$z*$R[-1]%$M;
}
say $F[$x]*$R[$x-$y]%$M*$R[$y]%$M;

H:OCR Killer(AC)

  • FAです。やった^ω^
  • http://kjjk.weblio.jp/ の手書きに頑張って書く。途中から疲れてiPadになった(twitter 自分宛DMでPCに転送)。タッチパネル最強^^
  • 問題文(一部おかしいけど、まあ。これでもGoogle翻訳結果見ながら手直しした方ですよ?)
1
2
3
4
5
6
7
8
9
10
11
달의 구면 상의 러리를 구하심시모
달의 구면 상의 점은 두 실수
(a,b) 로 주어진다 이건 지구의
"동겸a 도, 북왼 b도", 와 같다
서경, 남위는 음수를 사용 찬다
단, 이 몬세에서는 달을 위키백라
기사에 쓰이는 직경의 구라고
가정해야 찬다
(出力)
주머신 두 점의 거리를 츨력한다
오차는 적담히
  • 要約
  • 東経aと北緯bが2組入力される。月における2点間の距離を求めよ。月の半径はWikiにあるものを使え。

  • 答案

  • 北緯と東経が(慣習と)逆に入力されることにさえ注意すれば、難しくはない。
1
2
3
4
5
6
7
8
9
#!/usr/bin/python
import sys,math
def calcdist(a):
  lat1,lon1,lat2,lon2=map(lambda e:e*math.pi/180,a)
  return 3474.3/2*math.acos( (math.sin(lat1)*math.sin(lat2)+math.cos(lat1)*math.cos(lat2)*math.cos(lon1-lon2)) )

b1,a1=map(float,sys.stdin.readline().split())
b2,a2=map(float,sys.stdin.readline().split())
print(calcdist([a1,b1,a2,b2]))

I:雑な問題(AC)

  • piyo

J:雑な問題2(AC)

  • 問題IDが「the-answer-is-to2ange2an」である。
  • to2ange2an

K:Classical Cipher

  • もういいや
  • 鍵がT,Z,Nであることからエニグマだと思ったんですけどね、 ローターの選択とプラグボード配線もエニグマの鍵に含まれますよね??

  • 問題文

1
2
3
4
5
6
7
8
YOUAREGIVENASTRING
WRITEAPROGRAMTODECODETHESTRING
THESTRINGISENCODEDINFOLLOWINGWAY
FIRSTCONVERTEACHCHARACTERBYTHETABLE
THETABLEISGIVENRIGHTBELOW
KSYWQJDRZUIPGOLMXEBTVAFNHC
NEXTCHANGEKTHCHARACTERTOITSKTHNEXTALPHABET
FOREXAMPLEIFAFOURTHCHARACTERISYTHENCHANGEITTOC
  • 答案
1
2
#!/usr/bin/ruby
puts gets.chomp.bytes.map.with_index{|b,i|((b-65-i)%26+65).chr}.join.tr('KSYWQJDRZUIPGOLMXEBTVAFNHC','A-Z')

L:洞窟(AC)

  • Googleフォームを開いたらソースを開くと答えを見つけることができる。
  • SNUKEGORM_BY_DARUDE

M:Matryoshka(AC)

(1)

  • CPUに 10時間ほど 頑張って頂きました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/ruby
s=DATA.gets
314161.times{|i|p i
  s=IO.popen('php','r+b'){|io|
      io.puts s
      io.close_write
      io.read
  }
  puts s if i%1000==0
}
puts s
# <?printf($a=($b=0)?'<?printf($a=($b=%d)?%c%s%c:"%s-%s",$b-1,39,$a,39,dechex($x=%d),dechex($y=%d),$x+$x+$y,-$x);':"bf-cbc",$b-1,39,$a,39,dechex($x=3642),dechex($y=-191),$x+$x+$y,-$x);
# bf-cbc
__END__
<?printf($a='<?printf($a=($b=%d)?%c%s%c:"%s-%s",$b-1,39,$a,39,dechex($x=%d),dechex($y=%d),$x+$x+$y,-$x);',314159,39,$a,39,'','',-1084159067,1084162518);

(2)

  • こちらもCPUに10分ほど頑張って頂き、後半戦には入れたのですが、そこで死にました。
  • funzip、こういう目的には割と良いツール。
1
2
3
4
5
6
#!/usr/bin/ruby
loop{
  system("<data.zip funzip -bf-cbc >data.bin")
  break if File.binread('data.bin',2)!='PK'
  File.rename('data.bin','data.zip')
}
  • ヒントに助けられました。
1
2
3
4
5
6
7
8
9
10
#!/usr/bin/php
<?php
$s='';
for(;;){
  $stdin=trim(fgets(STDIN));
  if(!$stdin)break;
  $s.=$stdin;
}
for($i=0;$i<39;$i++)$s=openssl_decrypt($s,'bf-cbc','bf-cbc');
echo $s;

(3)

  • これもヒントに助けられました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/ruby
require 'net/http'
s=''.dup
Net::HTTP.start('goo.gl'){|http|
  key='xFnLDH'
  location=''
  loop{
      resp=http.get('/'+key)
      h=Hash[*resp]
      break if !h.has_key?('location')
      location=h['location'][0]
      domain,key=location.split('/')[-2..-1]
      s<<domain.scan(/\d/).join
      sleep(1)
  }
  puts location
}
puts s.tr('10','ls')
  • Herbert Online Judgeに流し込む。

  • 答案

1
2
3
bf-cbc
xFnLDH
SHRIFT

N:Answer the Number(部分点)

  • (1)だけです
1
2
def f(n) r=1.0;(1..1/0.0).find{|i|(r=r*(n-i)/n)<=0.5}+1 end
p f(10000)

O:THE EMPTY

  • 問題文は透過pngになっているのですが、画像中の暗号を解読できず。
  • 0,6,8,9の輪っかでπを表現するとか…うーむ。
1
2
3
#!/usr/bin/ruby
s=Math::PI.to_s.tr('.','')
puts s[gets.to_i-1]

P:THE EMPTY 2(AC)

  • 解答言語としてWhitespaceを選択すると問題文が現れます。
1
2
3
4
#!/usr/bin/ruby
require 'prime'
a,b=`dd`.split.map(&:to_i)
p Prime.each(b).drop_while{|e|e<a}.size

Q:THE EMPTY 3(AC)

  • Download sample test casesすると、output00.txtに問題文があります。
1
2
3
4
5
6
#!/usr/bin/ruby
require 'prime'
class Integer
  def divisornum() self.prime_division.reduce(1){|s,(n,p)|s*(p+1)} end
end
p (gets.to_i**2).divisornum

R:正しいダジャレギュレーション(AC)

  • 落ち着いて問題文を読みましょう。sの種類数と同じ意味です(ただしsが1文字の場合は無効)。
1
2
3
4
5
6
7
#!/usr/bin/ruby
n,a=gets.split.map(&:to_i)
if n<2
  p 0
elsif
  p a**n%100000007
end

S:健康計算機(部分点)

  • こういう問題の相場として、複雑な字句解析ってのがあるんですが、どうにもならなかった感じがします。ぐぬぬ。
  • まじめ版の字句解析器が通らなかったのは「x'y」という入力のせいですかあーあーそこまで考えてなかったわ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def bmi(kg,m)
  kg/m/m
end
a,b,c,d=gets.downcase.scan(/([\d'"\.]+)|([a-zA-Z]+)/).map{|e|e.compact[0]}
if a.scan(/\d/).empty?
  a,b=b,a
end
if c.scan(/\d/).empty?
  c,d=d,c
end
if b.end_with?('g')
  a,c=c,a
  b,d=d,b
end
a=a.to_f
a*=0.3048/12 if b=='in'
a*=0.3048 if b=='ft'
a*=0.9144 if b=='yd'
a*=1000 if b=='km'
a/=100 if b=='cm'
a/=1000 if b=='mm'
c=c.to_f
c*=1000 if d=='t'
c/=1000 if d=='g'
c/=1000000 if d=='mg'
c*=0.45359237 if d=='lb' || d=='lbs'
p bmi(c,a)

T:明日使えない英単語(部分点)

  • 知るかいな
  • 本番中は2,4に正解。
  • alopecoidという単語は「プログレッシブ英和・和英中辞典」「ウィズダム英和・和英辞典」「New Oxford American Dictionary」「Oxford Dictionary of English」のいずれにも載っていない単語ですよ
    • OSXの辞書ってこんなにくそでしたっけ(んなわけはない) ^ω^#
1
2
3
#!/usr/bin/ruby
T=%w(eaglet camaraderie oblast thesaurus alopecoid)
puts T[gets.to_i-1]

U:うんちくビ〜ム

  • 解説すら読めない。

V:Side Story of WolfHockeyTeamEasy/Hard

  • 問題、読めず。私の国語力も地に落ちたもの。
  • jpg埋め込みかよ
  • HOUSTON COSMONAUTS

W:Shiritori(部分点)

  • 知るかいな(2回目)
  • 本番中は1,2,3,4,5,7,8,9に正解できました。
  • ウルフサザ?なんですかそれGoogle検索結果0件なんですが…?「sothe」は不正解だしねぇ。
1
2
3
#!/usr/bin/ruby
T=%w(ke-ki ki kitune nezi zi ziyu-nomegami idou u uruhusaza huryoku kuku donou)
puts T[gets.to_i-1]

X:Please ignore.

  • 解いたらあかんやつ(2回目)
  • 先日iPad Air 9.3.2を脱獄してから久しぶりにいろいろ遊んでます。
  • ech0chrome iPhone Repo on Cydia (昔私がビルドしたソフト群)も一部使えました。ncompressとか(tar.Zとか今は使われてるんでしょうか…)
  • しかし、nkfやPuTTY、OpenHSPは「Illegal Instruction: 4」と出て動かない。
  • 少し調べたところ、http://theiostream.tumblr.com/post/63923259800/patching-iphone-gcc-binaries-to-armv7s に行き当たりました。ldr r3, [r3]命令がarmv6/v7専用命令になっていて、armv7sで解釈できないのが原因とのこと。armv7sで解釈できるように手直しすればよいそうです。crt1.oだけがおかしく、原因は不明とのこと。
#!/bin/sh
for file in "$@";do
sed -i'' 's/\x00\x30\x93\xe4/\x00\x30\x93\xe5/g;s/\x00\x30\xd3\xe4/\x00\x30\xd3\xe5/g;' $file
ldid -S $file
done
  • まあ、当時はiPhone 3GSやiPhone 4の時代だったので、v7sのことなんて頭になかったですからねぇ…
  • ビルドスクリプト、もしあったら、パッケージ化しようと思います。バックアップは今何処^^;(開発機のiPod Touch 3rdはヒューズが飛んだ状態)
  • てか、私の出してるiOS gccは間違いなく壊れたバイナリを出力するんですが、どうしたもんか。3.1.2用のtoolchainをセルフコンパイル用にポートしただけなので、新たにtoolchainを作る能力は私にはない^^;

  • ちなみに、Illegal Instruction: 4はこのパッチで直せますが、mmap error 22は直せません。

  • https://forums.developer.apple.com/thread/7524 によると、32bit dylibを読み込むにはMach-Oのヘッダがどうこうという話っぽいです。

  • 話は変わりますが、アプリ領域にアクセスするのが不便なのでapplinkなるソフトを作ってましたが、これもiOS8で使えなくなってた模様。com.apple.mobile.installation.plistがなくなったため。
  • 突貫工事で新たに作りました。Pythonが必要ではありますが。しかもリンク名がアプリ識別子になる制限付き。
  • https://gist.github.com/cielavenir/089ae47301458db8e2e04a67f72132b3