whileD'iary

日記とか

蟻本の分割数の問題を整理

目的

僕には何を言っているのかさっぱりだったので、他の方の解説を見ながら整理して理解する

分割数

nをm個以下に順序を区別せずに分割する方法の総数

m=nのとき特にnの分割数と呼ぶ

問題の漸化式

dp[i][j] = dp[i][j-i] + dp[i-1][j]

このdpのメモは、jをi分割したときの総数(dp[i][j] = jをi分割したときの総数)

まずjをi分割するとなったときにi個のものが自動的に最低1の数としてまず確定する

例えば5を3分割した場合、次の2パターン

  • 3, 1, 1
  • 2, 2, 1

7を4分割した場合、次の3パターン

  • 4, 1, 1, 1
  • 3, 2, 1, 1
  • 2, 2, 2, 1

このときどう分割したところで、それぞれの数は1より下にならない

つまりそれぞれの数から1を引いた数であるj-iの、順序を区別しない並べ方と考えることができる(このときは0を含むので注意)

イメージ的にはi個分の箱を用意して、j-i個のボールを重複のパターンがでないように入れる感じ

上記5を3分割した場合では

  • 2, 0, 0
  • 1, 1, 0

7を4分割した場合では

  • 3, 0, 0, 0
  • 2, 1, 0, 0
  • 1, 1, 1, 0

実際にパターン数は合致している

最後に後ろのdp[i-1][j]はjのi未満の分割の総数だからそれを足して

dp[i][j] = dp[i][j-i] + dp[i-1][j]

となる

参考サイト

Tech Tips: 分割数を考える

分割数の漸化式がよくわかんなかったから軽く整理した - 迷いませんか?

コドフォ初参加

Codeforces#467 div.2にでた

やる気がでてきたのでコドフォに出ました

やる気の維持のために振り返りとか何がわからんかったとかまとめたい

もっとやる気がでたら備忘録的に解説でもしようと思います

A.Olympiad

英語が全然できないので、わかってはいたが英文の問題に戸惑う

英語の読む方に時間かかった

言ってることは割と簡単だったので、重複を消して0以外の個数を数え上げてそれを出力して正解

B.Vile Grasshoppers

英語わかんねって思いながらサンプルと注意書きのところみたら理解できた

答えをnだとすると、nはpまでの数全てで割り切れない

ということはsqrt(109)までの素数リスト作ってyからp+1まで試し割りすればいいかなってなって実装して正解

C.Save Energy!

読解力がなさすぎて、翻訳を駆使しても何を言ってるのか全然わからなかった……

40分くらい英語と格闘して結局諦め

ストーブがついてない時間を計算してtに足せばいいのかな、とか思ってた

全体的に

英語がわからん 以上

bit全探索

C - たくさんの数式 / Many Formulas

をやってて、bitで組み合わせの全探索できるなみたな感じには思えたけど実装がわからなかったので覚え書き程度に書く。

bit全探索

ビットを仕切りに見立てて、ビットを全探索することで部分集合などを求める探索

今回の場合ようは、

1234567

という文字列があったとき

000110

というビットを用いて

1234|5|67

のように分割されているとみなすことができる。

計算量は2n

コード

以下提出したコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
using namespace std;
 
int main(){
  string s;
  cin >> s;
  vector<string> nums;
  for (int i=0; i<s.length(); i++) nums.push_back(s.substr(i, 1));
 
  long res = 0;
  long tmp;
  long digit;
  long sum = 0;
  string ssum = "";
  for (int i=0; i< (1 << (nums.size() - 1)); i++) { // bit演算なので条件
    sum = 0;
    tmp = 0;
    digit = 1;
    ssum = nums[0];
    for (int k=0; k<nums.size()-1; k++) {
      if (i & (1 << k)) { // 見てるbitと現在見てる桁に+がついているとき
        sum +=  stol(ssum);
        ssum = "";
      }
      ssum += nums[k+1];
    }
    sum += stol(ssum);
    res += sum;
  }
 
  cout << res << endl;
}

前にビットを使ったとき、アホなので"00000"みたいな文字列作って頑張ってた気がします

bitsetを使えばもっと綺麗にかけそうな気がしないでもない

JS記号プログラミングをやって思ったこと

はじめに

adventar.org

の24日目の記事です

アドベントカレンダーが始まってから24日も経つんですね、はやい

さて今回は、最近JavaScript記号プログラミングをやっていたので、それについて思ったことを書こうと思います

JavaScript 記号プログラミングについて

次のコードを見ていただくと、雰囲気はわかると思います

配列から数値が生成できたり、配列から文字列が作成できる。 しかも次のコードから関数オブジェクトが作成できるので、実質なんでもできます。

[]["constructor"]"constructor"

1 //1
-~[] //1

// constructorと出力
([][$_=([]+{})[-~-~-~-~-~[]]+([]+{})[-~[]]+([][[]]+[])[-~[]]+(![]+[])[-~-~-~[]]+((!![]+[])[-[]])+((!![]+[])[-~[]])+([][[]]+[])[-[]]+([]+{})[-~-~-~-~-~[]]+(!![]+[])[-[]]+([]+{})[-~[]]+(!![]+[])[-~[]]][$_]((([]+{})[-~-~-~-~-~[]]+([]+{})[-~[]]+([][[]]+[])[-~[]]+(![]+[])[-~-~-~[]]+([]+{})[-~[]]+(![]+[])[-~-~[]]+(![]+[])[-~-~-~-~[]])+'.'+(![]+[])[-~-~[]]+([]+{})[-~[]]+(([]+[])[$_]+[])[-~-~-~-~-~-~-~-~-~-~-~-~-~-~[]]+([][$_]+[])[(-~[]<<-~-~-~-~[])+(~-~[])]+"'"+$_+"'"+([][$_]+[])[(-~[]<<-~-~-~-~[])+(~[])]))() 

// constructorと出力
(function(){console.log('constructor')})()

思ったこととか

  • 文字数が少ないほど見にくくなっていい感じになる
    • 使える文字数が増えるにつれ便利になっていくので推測しやすい
  • =や,などの推測可能な文字はできるだけ避けた方がいい
    • 上記のconstructorの例だとわかりやすいが、変数っぽく見える
    • <<などのシフト演算なども避けたほうがいい
  • 改行はしないほうがいい

だいたい以上のリスト通りやるとみにくくなるんじゃないかと思います

シンプルなほどわかりにくいってのはBrainf*ckやwhitespaceが教えてくれている

短く難読化しようとすると、以外にも法則が見つかってしまうので、ここが悩ましいところ

個人的にはダブルクォーテーションや、シングルクォーテーションなど、一発で文字列とわかってしまうのはあまり使いたくなかったのですが、時間なかったのでこれでやってしまった

あと記号プログラミングは先輩がやっていたからやってみたのですが、最初は敬遠していたものの、案外パズルみたいで楽しいですねこれ

皆さんもやってヤバイコード見つけて教えてください

明日のアドベントカレンダー最後の記事を飾るのはかったーさんです

docker使ってC#書いてみた

はじめに

adventar.org

このアドベントカレンダーの19日目の記事です

前回はかがりさんだったのですが、ちゃんと読んだ本をアウトプットしててすごいなと思いました

今回は最近やったこととして、dockerでサクっとC#を書いたという話です

dockerということなので今回はMonoを使用してみました

docker

$ docker run -it mono /bash/bin
$ apt update
$ apt install vim

Mono公式がDockerイメージを配布するのでありえん楽ですね

とりあえずこれでコンテナ内でC#コンパイルと実行ができます

本当は外部ファイルをコンパイルと実行をできるようにしたかったけどよくわからなかったのでやめました

わかる方は教えてください

C

とりあえず車輪の再発明ですがかんたんにスタックを実装

using System.Collections.Generic;
using System;

namespace Info.Whiled {
  class StuckTest{
    public static void Main(){
      Stuck<string> stuck = new Stuck<string>();
      stuck.Push("vim");
      stuck.Push("c#");
      
      Console.WriteLine(stuck.Pop());
      Console.WriteLine(stuck.Pop());
    }
  }
  
  class Stuck<Type> {
    private List<Type> list = new List<Type>();

    public void Push(Type data) {
      list.Add(data);
    }

    public Type Pop() {
      Type data = list[list.Count-1];
      list.RemoveAt(list.Count-1);
      return data;
    }
  }
}

コンパイルして実行

$ mcs Stuck.cs
$ mono Stuck.exe
> c#
> vim

本当にC#コンパイルして実行できた、とか言ってた気がします

次にエラトステネスのふるいを実装

こちらはとりあえず言語触るたびに書いてたのですんなり

特有の構文もいりませんし

using System;

namespace Info.Whiled {
  class Era {
    public static void Main(string[] args){
      bool[] bools = new bool[101];
      for(var i=2; i<bools.Length; i++) bools[i] = true;

      for(var i=2; i<bools.Length; i++){
        if(bools[i])
          for(var j=i*2; j<bools.Length; j+=i)
            bools[j] = false;
      }

      for(var i=2; i<bools.Length; i++){
        if(bools[i]) Console.WriteLine(i);
      }
    }
  }
}
$ mcs Era.cs
$ mono Era.exe
2
3
5
7
11
... 

めっちゃ楽

感想

C#、なかなか書きやすいのではないかと感じた

dockerめっちゃ便利

あと僕に知識がなくそのままコンテナ内でvim使って書いてたのでシンタクッスハイライトとかなにもなしで書いてたのでつらかった

最後に一つ、Windowsがある場合は普通にWindowsで書けばいいなと思いました

内容全然なかったですが、これで終わりです。明日の記事はぬまたさんで「2017年おもしろかったYouTubeの動画を紹介します。」だそうです。きっと面白い記事を書いてくれるでしょう。

Goでnet/httpを使わずに雰囲気でechoしてみる

本記事について

このアドベントカレンダーの2日目の記事です。

adventar.org

まだ寝てないので、寝るまでが今日理論でいくとセーフです。

概要

当日まで何も決まっておらず、「あああああヤバイ!!」みたいな感じだったのですが、寿司を食べて元気を出したところでなんとなーくやってみるかって感じでプロセス間通信をやってみました。

それで実装にあたって下記の記事を参考にとりあえず調べてました。プロセス間通信と聞いて、自分が思ってたのはマップドメモリーだったのですが、めちゃめちゃ種類があってビビりました。

qiita.com

で、見てるとソケット通信ってのがあってめっちゃwebサーバーっぽかったのでそれをやってみました。

実装

他ブログやQiitaの記事などいろいろ参考にさせていただき、雰囲気で書きました。

f:id:whileD:20171203043955g:plain

やってることはポート指定してそこで待機し続けて、入力が来たらその入力を返すしかやってないので、多分説明することもないです。

所感

なんとなーくwebフレームワークとかの実装ってこうなってんのかな、とか思いました。フレームワークの読んだこと無いので雰囲気でですが。

あとはチラっとserver.goとかのソース読んだりしたり、普段書かないようなコードやライブラリとか使ってやる部分を見ると全然知識足りてないことを認識できるので、やる気が上がっていい感じでした。

次は誰がアドベントカレンダーの記事を書くかわかりませんが楽しみにしておきます。(適当な記事書いてすいません)

参考にした記事

net - The Go Programming Language

【Golang】Socket通信するプログラムを書いてみた - くどはむと猫の窓

ソケット通信 - はじめてのGo言語

Socketプログラミング · Build web application with Golang

エロ漫画読み放題サービスに登録するためにデビットカードとクレジットカードを契約した話

皆様、いかがお過ごしでしょうか? 今年もアドベントカレンダーの季節になりました。僕はといいますと、やる気がなくなり、毎日誰かに向かって助けを求める日々。

最近は布団に向かって「ハァああ〜〜〜〜助けてくれ助けてくれ助けてくれーーー!!」と叫ぶのがマイブームなっています。


つらいね。

この記事について

adventar.org

このアドベントカレンダーの初日を務める記事になっています

ノリで登録したのでめっちゃビビってますが、頑張って書こうと思います

内容は記事名通りです

エロ漫画読み放題サービス・komiflo

ところで皆様はkomifloをご存知ですか? そう、エロ漫画読み放題サービスです。おそらく人類史上最も望まれていたサービスです。なんで望んでいるか?こんなことわざわざ言わなくてもおわかりでしょうが、多い人で日に数度、平均的には日1、誰しもが"ソレ"に臨んでいるからです。

またエロ漫画は平成の見る抗うつ剤とも言われています。人々はソレほどまでにエロ漫画に興味と関心を持っているのです。

いやそれにしえもエロ漫画、ロマンがありますよね。特に僕は童貞なのでロマンしか感じられないです。

komiflo.com

komifloとの出会い

今年の5月7日経緯は忘れてしまいましたが、大先輩から「komiflo契約しよう」と誘われて言ってきて調べたら「最高……!最高〜〜〜!!!!」ってなったのが始まりです。

そのときのツイートです。 なんかメチャメチャ冷静になっていますが、相当なカルチャーショックを受けこの時すでに股間で物事を考えています。 多分この日はトップ画面のパソコンいじってる娘でヤッたのではにでしょうか?覚えていません。

komiflo契約編

デビットカードの章

股間と脳みそに衝撃を受け、思い立ったが吉日ということで即銀行にデビットカードを契約しにいくことになりました。

3限が空きコマの月曜日、昼に友人とメシを食べる前に少し待っててもらい、ウキウキで銀行に直行。 「これから僕の人生はバラ色に変わっていくんだ……!」と期待感をあらわにオタク特有のニチャニチャした笑いを浮かべながら行ったら、何があったのか詳しくは忘れた(多分印鑑忘れたとかそんな)のですが、そこでは契約できないことが判明。ただ気持ち悪い顔を晒しに行っただけで無駄足でした。

最悪ですね。その日はちょうど駅付近でザーメン色のモンスターエナジーを配っていたのでそれを飲みながらメッチャ溜息をついていたと思います。

後日、近所の銀行に行き契約を行いました。


それから一週間後無事デビットカードが届き再びニチャ笑い。「今度こそ俺は"""最高"""になれる……!」という気持ちでウキウキだったのですが、なんと契約したデビットカードは対応してないことが判明。

2つのアカウントで同じことを言っているあたり、相当ショックだったことが伺えます。

その後、僕の行動はなんだったんだといった気持ちになり、腹いせにkomifloのトップ画面の娘でヤリました。 あとエロ漫画を一冊購入しました。

クレジットカードの章

さる日からおよそ4ヶ月程。 「やはり諦めきれないぞ……!」となり、今度はクレジットカードを契約する決意を固めました。

デビットカードの失敗から次は店頭に行かずにネットを介して契約することに。

そして即申請。

1週間後、サークルの合宿でドチャクソ意識が高くなってるところで必要書類の送付のお願いの電話がかかりました。適当な受け答えをし、帰ったらこちらも即送付するぞと股間への意識の高まりも見せていました。

しかし、実際に帰って来て即送付しなかったのが失敗。

大学が始まり、後期の実験の班が留学生と留年生3人という新旧共演のスーパーチームになったりなどの激アツ案件が多数発生し、全てのやる気が地に伏しました。

現実を受け止めたくなさすぎて実験中に一心不乱に2048のプレイを研究したり、グラブったりしていると、だんだんとうつに。そこでようやく己の本分を思い出します。ARMSばりにエロ漫画を求め始めました。

――エロ漫画が読みたいか……


――エロ漫画が読みたい!


――エロ漫画が読みたいならくれてやろう!

気がつけば僕の手の中にはクレジットカードが存在していました。

それから

クレジットカードを作ったはいいものの、諸事情により直後は見送っていました。

そして講義中思い出し、即座に契約。ニチャニチャしながら講義を聞いていました。

その日の夜は疲れマ○みたいな感じだったのですが、家の脱衣所で「最高〜〜〜!!!最高最高〜〜!」と叫びながら興奮が最高潮に達したことを覚えています。あと、親が脱衣所に入ってきそうになってビビった。

このようにkomifloを契約すると人生が最高になってくるので、皆さんも契約してみては?

終わりに

komiflo、僕の先輩の使用率が高く、やはり全人類が望んでいる……という気持ちにさせてくれます。

まだ改善したほうがいい点は多くありますが、普通にいいサービスです。

TUT 今年もTwitterしかしてません Advent Calendar 2017 - Adventarの、次のライターはわたりんべー(@wtrnby)さんです。よろしくおねがいします。

余談

致した後は即エッチなコンテンツをタブから削除するので、komifloのブックマーク機能が永遠に使えない現象、どうにかなりませんかね。