Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

KCSは復活するのか?

はじめに こんにちは、かがみずです。去年まで ICT 委員会に所属していました。いわゆる老害です? この記事は ICT Advent Calendar 2016 の 23 日目の記事として書かれる予定でしたが 3 日遅れで書かれました。コレ宣伝なんですけど, 去った 12 月 21 日に 2…

JOI Open Contest 2015 - Sterilizing Spray ふたたび

kagamiz.hatenablog.comこの問題、さすがに実装も定数倍も重い解法を書いてしまっていたので、別のアプローチで解き直してみました。

Polish Olympiad in Informatics X Stage III - Sums

問題文 : http://main.edu.pl/en/archive/oi/10/sum問題概要 : 数列 $a_1,\ a_2,\ \cdots,\ a_n$ が与えられる。次のクエリに $k$ 個答えよ。 数 $b_j$ は 非負整数$x_1,\ x_2,\ \cdots,\ x_n$ を用いて $\displaystyle\sum_{i=1}^{n} x_i a_i$ と表せるか?…

AOJ 2439 - Hakone

問題文 : Hakone概要 : (日本語なので略)

JOI Open Contest 2015 - Sterilizing Spray

しばらく競プロをやっていなかったのと、ちょっと卒論の気晴らしをしたかったので、昔解いていなかった問題を漁ってました。 結果恐ろしいくらい時間を溶かしました……今から進捗出します。ごめんなさい(´;ω;`)ジャッジもテストデータも今は無いので、サン…

2016 年の目標

今年も大きい目標のみを掲げます。

2015 年の目標振り返り

kagamiz.hatenablog.comさて振り返ります!!

20 歳になりました。

おはようございます, かがみずです。 気づけば今年の 12 月 21 日で 20 歳になっていました!本当にここまで早かったです。この記事では, これまでを振り返ってみて 自分が良く出来たと思ったこと 自分がうまくできなかったと思ったこと を軽くまとめようか…

4 年間 JMC を開催して

はじめに こんにちは, かがみずです。競技プログラミング 5 年生です。 この記事は http://www.adventar.org/calendars/850 の 21 日目の記事として書かれました。コレ宣伝なんですけど, 今日 20 歳になりました! 1/5 世紀, 三十路 2/3 って感じの歳です。 …

老害の引退記事

はじめに こんにちは, かがみずです。沖縄高専 ICT 委員会に所属している 5 年生です。 この記事は ICT Advent Calendar 2015 の 21 日目の記事として書かれました。コレ宣伝なんですけど, 今日 20 歳になりました! 1/5 世紀, 三十路 2/3 って感じの歳です…

ICPC Asia Regional Tsukuba 2015 E - Bringing Order to Disorder

問題文 : Bringing Order to Disorder 概要 leading-zero を含む $n$ 桁の数に次の順序 $\prec$ を導入する。1. 数$x$ の各桁の和を $\text{sum}(x)$とあらわすとき, $\text{sum}(x) 2. 数$x$ の各桁に 1 を足したものを掛け合わせたものを $\text{prod}(x)$…

CODE FESTIVAL 2015 本戦 A ~ I

CODE FESTIVAL 2015 決勝に参加しました。 本番では 5 問しか解けませんでしたが, 解説を聞いて 6 ~ 9 問目も解けました。 解説はここから見ることができるので, 各問題に対する自分の簡単なアプローチとコードを書きます。

UnKoder Challenges - XOR Graph

すぎむさんが問題を書いている UnKoder の問題をちょっとずつ解いています。 解いていて面白かった問題を紹介しようと思います。 UnKoder の問題には, このリンクから挑戦することができます。今回はこの問題セットの中から XOR Graph の解法を紹介しようと…

AOJ 2629 : Manhattan

問題文 : Manhattanめちゃくちゃ時間を書けたので思考の整理に解法をまとめます。

東京大学 編入学試験受験記

こんにちは, kagamiz です。 この度東京大学工学部 計数工学科の編入学試験に合格致しました。 長い受験期間で, その間何度も挫けそうになりましたが, 結果として実って嬉しいです。後輩に向けて, 少しでも参考になればと思い受験記を記すことにしました。

ICPC 国内予選 2015 参加記

こんばんは, kagamiz です。今日は @tanishi345 と @orisano と一緒に ICPC の国内予選に参加しました。 まだ確定した順位ではありませんが, ABCD の 4 問を解いて全体の順位は 22 位でした。4 問のうち, C と D が僕の担当でした。去年やらかした件もあって…

ネイピア数の定義の数列の有界性と単調性の検証

問題 数列$$a_n = \left(1 + \dfrac{1}{n}\right)^n \hspace{1.0cm} (n \in \mathbb{Z}^{+}) $$を考える。① $a_n$ は単調に増加することを示せ。すなわち,$$a_n を示せ。② $a_n$ は上に有界であることを示せ。

積分記号の下での微分で遊ぶ

名古屋大学での演習問題 の 8 番を解いていたらすごく悩んだので解法をメモすることにします.

よく見る微分方程式とその解法

はじめに こんにちは, kagamiz です.最近は編入試験に向けて勉強しています. 編入試験の数学では, よく微分方程式が出題されます.出題されるものは簡単なものから, 見たことがないと厳しい物まで多岐に渡ってあります. その中で出会った微分方程式の解法を, …

Gamma 関数の相反公式

問題 Gamma 関数の相反公式$$\Gamma(z)\Gamma(1-z) = \dfrac{\pi}{\sin(\pi z)} (z \in \mathbb{C}, 0 を示せ.ここで, $\Gamma(z) = \displaystyle\int_{0}^{\infty} t^{z-1}e^{-t}\,dt$ です.たとえば, この公式を認めると$$ \left\{\Gamma\left(\dfrac{1}{…

JOI2015 本選 1 ~ 4

試験前の予備日なので, 家で引きこもっていました. やるべきことに追われ辛かったので, 気晴らしに JOI の問題を解いていました. 今年の目標も昨年と同じく後輩ズに勝つことでした.オンライン参加して 3 問目まで解いたくらいのところでサーバー障害が起きた…

2015 年の目標

来年は大きな目標のみを立てることにします.

2014 年の目標の最終結果+α

何が達成できたのかというと何も達成できなかった年になってしまった気がする.この記事の集計結果です.

最近の 45 度回転事情

こんばんは, kagamiz です! ちょうど 1 歳老けたところです :).この記事は Competitive Programming Advent Calendar 2014 の 21 日目の記事として書かれました.この記事では, 最近ぼくが見た範囲で出題された 45 度回転の問題を紹介していこうと思います.ち…

ミズゴロウを愛する 7 の理由

こんばんは, kagamiz です. この記事はポケモンアドベントカレンダー の 19 日目の記事です. 3 回めの寄稿です. 今日はミズゴロウを愛する 7 個の理由を語ります. 本当は 356 (ミズゴロウ) 個語りたかったのですがこの記事にそれを書くには時間がありません…

ポケモン不思議のダンジョンのすすめ

こんばんは, kagamiz です. この記事はポケモンアドベントカレンダーの 17 日目の記事です. 今日はポケモン不思議のダンジョンシリーズについて思いを語らせていただきます.

JOI 予選 2014-2015

JOI 予選2013 - 2014 参加記 - Lilliput Steps JOI 予選2013 - 2014 参加記 - Lilliput Steps懲りずに今年も 6 色に挑戦しました. 結論から言うと 1 / 6 です Ω\ζ°)チーン. 俺が J 言語だ!! 答えとひとことコメンツも書いておきます. kagamiz 解が一応書かれて…

JOI 模擬予選 2014-2015 解説++

JOI

こんばんは, kagamiz です. この記事は JOI 模擬予選 2014-2015 の 解説pdf の補足(というかひとことコメント)を目的として書かれた記事です.それぞれの問題の kagamiz 解 / yosupot 解を載せます.あと, なるべく早くに KOJ に今日の模擬予選の問題はアップ…

今週の目標(12 月 第 2 週)

予定詰めすぎている気がするので減らします. 英語は急ぐ案件でもないので 2 月位からペース上げることにします..

AOJ と歩いた 4 年間

こんばんは, kagamiz です. 12 月ですね. 沖縄では気温が 16 ℃で, 温度差に苦しめられています. 皆さんのお住まいは過ごしやすい気温でしょうか.この記事は ICT Advent Calendar 2014 の 2 日目の記事として書かれたものです.今日は, 僕の AOJ 半生後輩に AO…

ミズゴロウ Advent Calendar 1 日目

こんばんは, kagamiz です. 12 月ですね. 沖縄では未だに気温が 26 ℃になったりします. 皆さんのお住まいは過ごしやすい気温でしょうか.この記事は ミズゴロウ Advent Calendar 1 日目の寄稿として書かれたものですが, この記事を書いた時点で寄稿者がぼく以…

今週の目標(11 月 第 5 週 / 12 月 第 1 週)と月次目標

緊急案件が入ったのでずっと開発してました... 自分のキャパ見積が下手くそなのを実感しました. (タスクは今週のものを引き続き).時間を大切に使いたいですね...

今週の目標(11 月 第 4 週)

一週間 twitter から離れてみる, というのを実施したけど, 自分には合わなかったかな. 依存し過ぎはよくないけど, 一気に断つのも違うかな. バランスが大事.

今週の目標(11 月 第 3 週)

K4PC が終わってしまって空虚さが頭をいっぱいにしています. 楽しかったなあ. 早く受験終わらせないとなあ.あと先週の目標を書きそびれた(2 回目?). 先週は絶望してたし多少はね...

「あと一歩」との戦い

自分を見つめなおす良い機会を得られたので, ここに記します. 言葉にして後で見直せるようにしたい. 今週の目標は日付が変わった後に書くと思います.

株式会社 ABEJA のインターンに参加しました.

8 月 11 日 (月) から 8 月 29 日 (金) の間, 株式会社ABEJA でインターンを行いました. 3 週間の間, インターン業務中のサポートにとどまらず, 宿泊先を提供していただいたり, 美味しいランチを一緒に食べに行けて本当に幸せでした. (でも何故かインターン…

今週の目標(11 月 第 1 週) と月次目標

微妙っすね...

今週の目標(10 月 第 5 週)

ICPC で慌ただしかったから 4 週目がかけなかった. 次からは気をつける.

Japan Alumni Group Summer Camp 2014 Day 4 D - 夕食

問題文 これ 概要 原文が日本語なので省略.

ICPC Asia Tokyo Regional 2014 G - Flipping Parentheses

問題文 これ 概要 対応のとれた括弧からなる文字列が与えられる. 括弧の向きを変えるというクエリが大量にくるから, 最も左の別の括弧の向きを変えてまた対応がとれているようにせよ.

ACM-ICPC Asia Tokyo Regional Contest 2014 参加記

こんにちは, kagamiz です. 2014/10/18 - 2014/10/20 に行われた ICPC アジア東京地区コンテストにチーム "Heart of Master" で参加しました. チームメンバーは @kagamiz @li_saku @gawaki です. だれも修士課程に所属していません. この記事ではコンテスト…

Codeforces 472D - Design Tutorial: Inverse the Problem

問題文 Design Tutorial: Inverse the Problem 概要 $n$ 頂点の有向グラフの隣接行列 $A$ が与えられる. この行列が各辺に重みがついた無向グラフであり, 木を表していれば YES を, そうでなければ NO を出力せよ. 制約 $n \leqq 2000$

先週の目標の達成具合と今秋の目標(10 月第 3 週)

今回は結構出来た気がする. ちゃんとみてみよ.

先週の目標の達成具合と今週の目標

半分くらい達成できて半分やってないですね...()

AOJ 2382 - King Slime

問題文 : King Slime解いている人数が少ない問題はなんかドキドキする(小並)

AOJ 2317 - Class Representative Witch

問題文 : 委員長の魔女AOJ-ICPC の難易度設定には納得だけど実装つらかった(小並)

NPCA Summer Contest 2014 問6 - 蝉ヌード(Cicada Nude)

問題文 : Cicada Nudecatupper 先生から問題利用の許可を得たので去った 9 月 10 日の PCK 対策コンテストに出題していました.ところでこの問題では $O(n^2)$ の DP が出来るのですが, 実は $n \leqq 10^5$ でも解ける問題となっています (ということを catu…

9/29 - 10/4 の週次目標, 10 月の月次目標

見られてたほうが意識すると思うので, 週ごと & 月ごとの目標を公開することにします. 来週からは達成具合も書きます.

Codeforces 160D - Edges in MST

問題文 : Edges in MST 概要 $n$ 頂点 $ m $ 辺からなる連結な無向グラフが与えられる. ある辺がグラフの最小全域木に 必ず使われるなら "any" 少なくとも 1 つの最小全域木に使われるなら "at least one" 使われることがなければ "none" と出力せよ. 制約 $…

Codeforces 235B - Let's Play Osu!

問題文 : Let's Play Osu!概要$n$ 個のマスがある. マス $i$ は確率 $p_i$ で "○" になり, 確率 $1 - p_i$ で"×"になる. $n$ 個のマスのうち, "○"で繋がったそれぞれの連結成分の大きさを$S_i$ とすると, スコア $\displaystyle\sum_{i = 1}^{連結成分数}S_i…