夕立進行会報

色々と使い勝手に思いがあり、 以前作成したMarkdownパーサ を少し修正した。こちらの 実行スクリプトページ でも生成されるhtmlが変わるので注意（使ってる人はいないと思うけど）。 変更点 コードブロック &#96で囲った場合に生成されるコード部分を<code>タグで囲うように変更。またpreに付いていたクラスを削除。コード種別はcodeタグのクラスに設定。 <pre class='codeblock code_c'>//コードブロックです。ハイライトは付きません。 int a = 0; int b = a+1;</pre> ↑旧 新↓ <pre><code class='code_c'>//コードブロックです。ハイライトは付きません。 int a = 0; int b = a+1;</code></pre> インラインコード 同じく<span>から<code>へ変更。 <p>インラインコード表記は&#96;で囲み<span class='inlinecode'>int a=0;</span>ます。</p> ↑旧 新↓ <p>インラインコード表記は&#96;で囲み<code>int a=0;</code>ます。</p> 引用 以前は入れ子の引用を<span>で区別していたが、標準的な<blockquote>の入れ子に変更。 <blockquote> <span class='blockquoteNest'>&gt;は引用です。</span><br /> <span class='blockquoteNest'>ここも引用です。</span><br /> <span class='blockquoteNest'><span class='blockquoteNest'...

気づけばだいぶほったらかしになっていた。今日は競技プログラミングで出てくる「～で割ったあまりの数」についての覚え書き。 AtCoderでよく出てくる以下の文。 ～を10^9+7で割った余りを求めてください。 競プロ特有の表現なので初見は「なんのこっちゃ？」と思った。要は答えが通常の数値型では表現できない大きな数になるので、1000000007の剰余を答えろということ。 当然割る前の数を求めるとオーバーフローするので、途中途中で剰余をしながら答えを求めるわけだが。 (a + b) % m → (a % m) + (b % m) 各四則演算について上記のような置き換えが可能であることを確かめる。 証明 任意の二つの数x1,x2を以下のように定義する。 x1 = aM + c x2 = bM + d ※Mは除数、a,b,c,dは任意の整数 なお以下では除数Mでxの剰余を取ることを「x mod M」と記載する。 加算 y = x1 + x2 = (aM + c) + (bM + d) = (a + b)M + c + d y mod M = c + d = (x1 mod M)+(x2 mod M) よって (x1+x2) mod M = (x1 mod M)+(x2 mod M) 減算 加算と同じである。ただしプログラムの実装では計算過程で負の値が現れる可能性を考慮し、負値の場合Mを加算する処理を入れる。 乗算 y = x1 * x2 = (aM + c)(bM + d) = abMM + adM + bcM + cd y mod M = cd = (x1 mod M)(x2 mod M) よって (x1 * x2) mod M = (x1 mod M)(x2 mod M) 除算 ここまでは感覚的に理解してる人も多いと思う。除算だけ少し毛色が異なる。実はここが本題。 除算は以下のようにこねくり回してもMの倍数と定数項の形にできない。 y = x1 / x2 = (aM + c) / (bM + d) = aM / (bM + d) + c / (bM + d) つまるところ (x1 / x2) mod M = (x1 mod M) / (x2 mod M) は成り立たない。 ここで フェルマーの小定理 というものがある。その詳細や証明はひとまず置いてお...

主にAtcoderでやる競技プログラミングで再利用するために、C#で書いたコードたちを載せてみる。どれも既知のアルゴリズムなのでコピペとかして構わないけど、もし間違っていても責任はとらない。 また何かあれば追加するかも。 公約数／公倍数 最大公約数 static long Gcd(long m, long n) { if (m < n) {var t=m; m=n; n=t;} while (true) { var mod = m % n; if (mod == 0) return n; m = n; n = mod; } } ユークリッド互除法 の実装。 最小公倍数 ※2020/5/13 計算途中でのオーバーフローに対策 static long Lcm(long m, long n) { var x1 = Math.Max(m, n); var x2 = Math.Min(m, n); var gcd = Gcd(x1, x2); return x1 / gcd * x2; } 上のGcdが必要。最大公約数から最小公倍数を求める公式。 演算 累乗 ※2020/5/31 2^32でOFしてたのに対応 static long Pow(long x, long n) { long ans = 1; while (n > 0) { if (n % 2 == 1) { ans = ans * x; } n /= 2; if(n == 0) break; x = x * x; } return ans; } 通常はMath.powを使う累乗の手書き実装。n<0には対応しない。単純ループするとO(n)だが、2乗を入れ子にするアルゴリズムで実装してO(log n)。いわゆる繰り返し二乗法。 x^20 = (((x^2)^2)^2)^2 * (x^2)^2 累乗（Mod） ※2020/5/31 2^32でOFしてたのに対応 static long ModPow(long x1, long x2){ l...

小ネタ。IISでは接続元のIPアドレスによってアクセス制限を設定したりできる。説明を見ると大抵フォルダー単位で設定をしているが、それをファイル単位で設定する方法。 IISマネージャで 通常はこのようにフォルダまでしか表示されていないが 上にあるアドレスバーでファイル名までパスを入力してエンターを押すと そのファイルだけツリーに表示される。これでフォルダにするのと同じようにファイルに設定を加えることができる。変な動作。 configファイル 結局のところIISマネージャで設定したものは.configファイルに書かれる。Default Web Siteの配下なら"C:\inetpub\temp\appPools\DefaultAppPool\DefaultAppPool.config"など。アクセス制限は以下のような記述。 <location path="Default Web Site/ARFusen/Contents"> <system.webServer> <security> <ipSecurity> <add ipAddress="192.168.1.1" allowed="false" /> </ipSecurity> </security> </system.webServer> </location> このpath属性にファイルのパスを入れれば別に普通にファイルでも動作する。まあでもIISマネージャーがインストールされている場合は、上書きされたりしても嫌なのでGUIで設定できたほうがいいよね。 以上 設計としてはフォルダで分けるほうが妥当なんだけど、今回は既に稼働済みのシステムでURLを変えずに特定ページのみ制限したかったのでやってみた。

WPFでページ遷移を作る場合、XAMLでFrameコントロールを置いてナビゲーションするのが手っ取り早い。しかし今回はちょっとした罠に掛かってしまった。 ページ遷移でメモリリーク？ なんか画面移動するたびにメモリが増えていく。まあPageのインスタンスをその都度newしてるので一時的には増えるが、そのうちGCされるだろう。そう思ってたがいつまでも減らない。試しにGC.Collect()してみても減らない。Page内で残ってる参照なども心当たりがない。はて。 犯人はナビゲーション機能 Frameコントロールにはナビゲーションの機能が付いている。NavigationUIVisibility="Visible"を付けると[戻る]とか[進む]のボタンが出てくる。 こういうやつ。見た目がいまいちだしあまり使われてる気はしない。しかしどうもこの[戻る][進む]機能のために、Frameは表示したインスタンスの参照を保持しているようだった。 これはNavigationUIを非表示にしてもやめないし、履歴保持数などのプロパティも設定できない。いったいどの程度持ち続けるのだろうか。まさかメモリが枯渇するまで残し続けることは無いと信じたいが。 対策 前述の通りプロパティなどで無効化することはできないので、履歴を手で消してやる。以下のようなコードをどこかしらに実装する。 while (Frame.CanGoBack) { Frame.RemoveBackEntry(); } RemoveBackEntry()は最後の履歴を1件削除する。全クリアなどのメソッドは無いらしい。しかも履歴が一件も無い状態で呼ぶと例外が発生する。 これをページ遷移の処理部なりで呼んでやれば、とりあえず延々増えてくことは回避できる。確実なのはFrameの遷移完了イベントあたりか。 しかしAddなんちゃらみたいなメソッドではなく、Content=～という代入でキューイングされるのはちょっとイマイチな実装だと思う。

より入力しやすいように専用ページを作りました。以下を利用してください。 Markdown Box 2020/4/23 パーサを修正し生成コードが変わりました。変更内容は こちら。 2020/5/31 codeタグのclass名に自動でprefix"code_"が付かなくなりました。 BloggerはWebエディターかHTML直打ちしか対応しておらず少々書きにくい。私は以前作ったパーサを使ってMarkdownを書いてHTMLに変換して投稿している。 JavaScriptでMarkdownパーサの作成 ふと、HTML直打ちができるということは記事の中にformやscriptを書けば動くんじゃないかと思い、パーサスクリプトを埋め込んで記事作成用ページを作ってみる。 Markdown記事作成ページ 公開終了

空き時間に AtCoder というサービスをやってみたので感想や環境など。 概要 AtCoderは日本企業が運営している競技プログラミングのサイト。毎週主に土曜日の夜に定期コンテストが開かれていて、Webから登録すれば簡単に参加することができる。 コンテストの流れ コンテストは事前に告知された時間にみんなで一斉に行う。 開始時間になるとページに問題が表示されるので、それに沿うようにコーディングを行う。 ソースコードをWeb画面から送信するとサーバでコンパイル、テストケースが実行され成否が判定される。正解した問題数と回答時間で順位が決まるようだ。 プログラミング言語はC++やJavaなどの選択肢から選ぶが、主要なものはほぼ揃っている。COBOLなんかもあるが流石に利用者はほぼ見当たらない。自分はC#でやっている。 所感 プログラミングというよりはアルゴリズムのコンテストといった感じで、数学的な問いをプログラムで実装するようなものが基本。 評価は「インプットに対するアウトプット」「計算時間」「回答時間」でされるので、コーディングのフォーマットやエラー処理なんかは特に問われれない。 難易度 毎週やってるBeginner Contestは難易度準にA～Fまでの問題がある。 ABは初学者教本にあるような基礎。足し引きと分岐・ループができればだいたいOK。 Cは数1Aぐらいまでの内容で、プログラミング的にも再帰やコレクションの使い分け、計算量を想定した実装が必要になってくる。普通のプログラマはこのあたりが及第点だろうか。 Dからは動的計画法や漸化式みたいな考え方が出てくるし、既知のアルゴリズムをベースにしたりする必要があるので、現役理系学生以外は対策しないと厳しい。 実務に活かせるか 内容がアカデミック寄りなので、ほとんどの現場ではあまり直接的な関係はなさそう。実際の業務コーディングではアルゴリズムより機能の切り分けや将来設計、速度より安全な実装と適切なエラー処理などの方が大事になってくる。 検索エンジンやミドルウェアを作るならそういう機会もあるかもしれない。 就職アピールなら評価の対象は問題そのものよりも、プログラミングへの興味の高さや、やっていくうえでの工夫や学習法あたりになるだろうか。 コーディング環境とか 一応Webサイト上にデバッグ環境みたいなのはあるが、すべてそれで...