2016-02-08

Codeforces Beta #92 Div2.A "The number of positions"

自分と同じ悲しみを産む人がいそうなのでメモ。

問題

Petrくんは $n$ 人の並び列の中にいます。Petrくんは自分が何番目の位置にいるのかは分かりませんが、前に $a$ 人以上、後ろに $b$ 人以下がいることが分かっています。Petrくんの位置としてありえる場所の数を出力してください。

考え方

例によって入力例だけで考えると死ぬやつ。何も考えずに解こうとすると「後ろの人の数は0人まで減らせるんだから単純に $n - a$ が答えでいいんじゃないか？」と自分は思ってしまったんですがそうではない。例えば以下の場合を考えてみる。

aaa....bbb (n = 10, a = 3, b = 3)

この時 n - a = 7 なので答えを7にしたくなるが、実は3つのaの真後ろに自分がいると、後ろのbは最大でも3人しかいてくれないため n = 7 となって矛盾する。

aaa#bbb

したがって $a + b \lt n$ の時はbが0人からb人までのb+1通りがある（aは何人でも増やせる）ので $b + 1$ が正しい。

aaaaaa#bbb
aaaaaaa#bb
aaaaaaaa#b
aaaaaaaaa#

逆に $a + b \geq n$ の時は $b = 0$ の時が最も多くの位置を取れるので $n - a$ が正解。

     ----> bを減らしていくと
.....bbbbb
aaaaaaa... <- (n - a)
       <-> 結局ここしか取れないことが分かる（この時bは条件を満たしている）

ソースコード

import std.stdio, std.range, std.string, std.conv, std.algorithm;
import std.math;

void main() {
    int n, a, b;
    readf("%d %d %d", &n, &a, &b);
    if (a + b < n) {
        writeln(b + 1);
    } else {
        writeln(n - a);
    }
}

2015-12-20

夢屋の隠れ大盛り／夢屋，コスパを求めて

同じネタが出てこなかったので2本立てになりました．この記事は夢屋Advent Calendar 2015の20日目の記事です．Advent Calendarは普通1日1ネタだとは思いますが意外と普通のネタがここまで出ていないというのともうすぐ卒業ということで出し惜しみせず2ネタやりたいと思います．すみません．というか前2日がまだ出てないのですが大丈夫でしょうか．

About Me

知識の4年生で，~~大食いサークル~~クイズ研究会T~~食べる~~Q食うS食事に所属しています．このサークルは週2回の活動のアフターにほぼ確実にRanRanと夢屋に行く習慣があるので適当に計算しても100回以上は夢屋に行っていることになり，夢屋のメニューについてだいたいどんなものが出てくるかは知っているつもりです（さすがに日本酒とかは頼んだことがない）．

夢屋の隠れ大盛り

夢屋といえばとりかつカレー両大がラスボスというのは誰もが認めるところとは思いますが，実は裏ボスが存在します．それがこのとりかつ丼（写真はおかず大）．

鶏カツの量はおそらくおかず大でジャンチキ普通レベルがやってくると思われますが問題はご飯．丼なので普通でも多いのにごはん大にするとここからさらに増えるので大変です．そしてさらに凶悪なのが卵とじ部分．出汁が結構濃いので意外と早めに飽きてしまい苦戦します．RanRanの親子丼特盛が意外にキツいのと同じ理論なわけです．

ラスボスとはまた違った感覚を味わえます．是非挑戦してみてください．

夢屋，コスパを求めて

夢屋のコスパを求めて自炊に堕ちたエントリが本ACにも散見されますが，はっきり言って自炊は甘えです（過激派）．ということで私が思う「夢屋で頼める一番コスパの良いメニュー」を紹介します．それはズバリ「揚げ出し豆腐定食」です．（写真は両大）

夢屋では一品料理に220円プラスすることでジャンチキなどのように定食化することが出来ます．そこからさらに両大なので300円追加で結局の値段は720円．チキンカツ定食と同じ値段でなんと12個もの揚げ出し豆腐におかず大分の唐揚げ1個を食べることが出来ます．ジャンチキや焼きからの普通よりも安くタンパク質の塊をここまで食べられるのはかなりコスパが良いと個人的には思っています．ちなみに豆腐は絹で結構柔らかいのでレンゲを使うと食べやすくなります．私のような豆腐スキーの皆さんは是非試してみてください．

2015-12-14

卒論書いた

嘘です．書いてる最中です．

この記事はklis Advent Calendar 2015のために書かれたものです．今年はちゃんと12月の頭からやってます．すごい．記事としては9本目です．記事を書かなきゃいけないことを23時45分に思い出しました．~~すごい．~~普通に遅刻しました．すごくない．

知識情報・図書館学類の卒業研究のスケジュール感を把握してもらうために，自分が研究室に配属されてからやっていたことを時系列でまとめたいと思います．僕は知識情報システム主専攻なので他の主専攻の人はあまり参考にならないかもしれません．すみません．他主専攻の人書いてください．

12月: 血の配属戦争をギリギリで平和的に乗り越え第一希望の研究室に配属される．最初のゼミでチュートリアル資料を渡される（最初のはただJavaについて書かれたもの，ただしgradleの話とかも書いてあってモダン）．中旬頃にMBAを渡されるのでいじる
1月: この頃から週1でゼミ．新しいチュートリアル資料（ここからは機械学習に関するもの）をもらったりその資料の理解度の進捗を確認したりしながら興味ある分野のサーベイを始める．院に行くかもしれないけど一応という意味で就活を始める．
2月: 冬休みということでゼミは無くて実家に帰ってた．サーベイは多分してた．あとTwilog見たらキレてTwitterからいなくなってた．既に精神状態が危うい．ソーシャルゲーム開発会社とメガベンチャーにエントリーして1次面接で落ちる．Aから始まるコンサルとYから始まるポータルサイトにESで落ちる
3月: ゼミ再開．引き続きもともとやろうと思っていた質問応答についてのサーベイを続けるがある日突然指導教員から「明日のゼミに題目の叩き台を持ってきてください」とのメールが入る．ゼミの方向性と質問応答の相性が悪いのではないかと薄々思っていたのでここで急遽SNS系の題目を提出する．ビビッときたベンチャー企業にエントリーして1次面接・2次面接を受ける．最終面接まで行った中小SIの社長が（検閲により削除されました）でわざと落ちにいく．落ちた
4月: 着手発表．着手のスライドは4月に入ってから作った気がする．ここからはプログラムを書いては実験をし続ける日々．↑のベンチャー企業から内定をもらってこれもう院行かなくてもいいんじゃないかと思い始める
5月: Twitterのデータを使って実験してはゼミで指導教員と議論するみたいなことをやっていた気がする．企業から内定をもらっていたことをゼミで指導教員に報告し院進しないことがほぼ確定する
6月: 実験を続けるうちにこれもっとベースの手法のところから考えたほうがいいんじゃないかという話になり研究対象のレイヤーが1つ落ちる．WebDBフォーラムに出せたら出します（笑）みたいなことを言ったらなんか本当にそういう話になる
7月: たぶん実験してた．何やってたかあんまり覚えてない．ここらへんからだんだん手法がややこしくなってくる
8月: なんか本当にWebDBに出すことになった．精度が出ない→手法を難しくする→精度がもっと出ない→……という負のスパイラルに陥り結局論文を提出できなかった（ネガティブリザルトとしてまとめる可能性もあったけどこの手法だと良くないというのが後々のサーベイで見つかったので自分の意志で提出取り下げを決めた）．この経験を機に大学院に進学する気持ちが完全に無くなった
9月: 実家に帰らせていただいた．実家にいる間は研究のことを一切考えなかった（≒考えたくなかった）
10月: 手法を単純なものにしたほうがいいという知見が先の論文提出用の実験の中で得られたので卒論は素直にそっちの方向で書くことに決めた（つまり手法の新規性からアイデアの新規性に重点を移した）．予備実験を進める
11月: 論文に載せる評価手法をどうしたらいいかを指導教員と相談し，データを揃えて実験し直す．実験プログラムのデータ取得部に想定とは違う動作を指定た部分が結構あり直すのに苦労する．中旬から卒論執筆に着手する
12月: 実験が全て終わり卒論を仕上げる（まだ仕上がってない）

機械学習系はプログラム用のフレームワークがかなり充実してきており，サーベイしてアイデアが思い付けばあとはデータを集めてプログラム実装して実験するだけみたいな感じになってきている気がします．そのため一度実験をして結果を出せばあとはその結果を見て次にやることが動的に勝手に決まるのでこの分野はそこが楽かもしれません．1年過ぎて感じたことは

サーベイは英語でしよう（日本語という言語に着目した研究を除く）
- 何も思い付かん場合はトップカンファレンスのAccepted Papersを見て面白そうなタイトルの論文を読む→参考文献を芋づる式に読む
最初は小さいところから実験を始めて結果を逐一指導教員に報告しよう
- なんかしらフィードバックがもらえるはずなのでその後の方針がどんどん決まる
就活するなら早いうちに決めてしまおう
- 上にもある通りああいう業界はスケジュールがめっちゃ早いです

研究に向いてなかった学生の例ですが参考になれば幸いです．卒業研究頑張りましょう．

2015-12-06

CODE THANKS FESTIVAL 2015 参加記

経緯

今年はCODE FESTIVAL行くぜ
A3問目で爆死（30分3完）→B15分で3完やったぜ→ち〜ん(笑)

ということで今年もTHANKSです．CODE FESTIVAL行くぜとか言ってる割にこの1年特に対して勉強してなかった（Codeforcesにはちょくちょく出るようになった）ので残当．

行く前

7時半起きですよろしくお願いします
— YousackはMマスLVつくば (@antefest) 2015, 12月 4

アニメ見てソシャゲして3時半に寝た．最近眠くなる時間帯が早まってきているのでよい．

当日

起床チャレンジ成功 (@ つくば駅 (Tsukuba Sta.) in つくば市, 茨城県) https://t.co/kzD1eqL4RS
— YousackはMマスLVつくば (@antefest) 2015, 12月 4

無事起床．寝る時間が短くても目覚ましへの応答速度は速い．テレコムセンターに行ったら1回のホールにそれっぽいことを前日から示唆していた学類の後輩がいてやっぱりなと思った．ちょっと早く来すぎたので会場があるフロアをさまよいながら5分ほど待つ．

開場したら交通費の精算チェックを済ませてTシャツを受け取って自分の席へ．Tシャツは今年は黒でかっこいいなと思った（黒なら何でもいい？）．席次は39番と意外と真ん中の方だった．キャンセル多かったんだろうか．誓約書に署名してMBAをWi-Fiに接続したら早速後ろの机に置いてあったお菓子を乞食しに行く．開始直前の弁当争奪戦はなんとか焼肉弁当をゲットする．席次が上の方が弁当に近いのが社会の縮図っぽい（適当）．

コンテスト中

A(100): なぜか意味不明な考察を始めてAとBの正負で場合分けする意味不明なコードを提出したら通った．よくよく考えたら絶対値で考えなかったのが問題だった．数学の苦手な高校生かよ
B(100): 問題文の読み解きがJ問題だった．2-3分ぐらいかけて題意を理解してサッと書いてサッと出した．昇順で出力するというのを完全に見落としていたけどD言語にSetがないおかげで answer.sort.uniq したら必然的に昇順になるので気にせずパスできてよかった．Pythonでやってたら落ちてた
C(100): 1-indexedで解答するのと大小の比較演算子でちょっと混乱したけどすぐ出せた．AtCoderの問題は入力例にコーナーケースが入ってることが多くて優しい世界
D(100): 紙に書いてシミュレーションして考察．最大値は割とすぐ分かったけど最小値の出し方に数分悩む．5分近くかけてようやく理解したので実装したら通った
E(100): 最初左から右に順番に探していけばいいじゃんというアイデアで実装したけど1種類文字を消すとそれが全て文字列が消えることに気付いて再考．文字列長の制約がガバガバだったので「これもしや必要ない文字を2重ループで照合して全部消してからfindしたら上手いこと通るのでは？」と思いその方針で実装したら普通に通った．CODE FESTIVALだったらもっとキツい制約で出そう（やり方は分からん）
F(-): 問題読んでああゲーム理論であることだなあと思いつつ弁当を食べ始めた．紙に書いて考察しようとするもなんか難しそうだと思い込んでしまう．難しそうだと思うくせに「これ別にポイントがどうこうじゃないし意外と簡単な解法なのかもなあ」と思いつつG問題を見たらグラフの問題だったのでそこでFの考察をやめて飛ばしてしまう．ここが5完と6完の分かれ道だった
G(1×): 問題文読んでなんかダイクストラがベースっぽいなあと思う．開始前に撮ってきたお菓子を食べつつWikipediaでダイクストラの記事を見ながらアルゴリズムを実装しているときに「prevにノードとそこに到達した時の色を持たせとけばいいのでは？」と思いついたのでその方針で進めたものの入力例1がWAになる（というか紙の上でのシミュレーションもなぜか出力例1と違っていた）．とりあえず2つ目は答え合ってるし〜と思って思い出Submitしたものの結果見たらそこしか合ってない上に後半TLEだった．そのままなすすべなく終了

懇親会

疲れたので解説の後半全然聞いてませんでした．すみません．懇親会のコンテンツは去年とだいたい同じで音ゲーの課題曲もPARANOiA MAX -DIRTY MIX-と地平線のエオリアだった．パラマックスダーティー激は何回見ても後半が足15ぐらいに見える．今年はTHANKSにもスタンプラリーがあったのでスタンプを貰うために挑戦したらやってるうちにポジションが前の方にどんどんずれていって序盤ですぐ落ちた．マットは厳しい．DDRで疲れたので書道コーディングでD言語くんを書いたり（スタッフさんに「去年も見た」と言われた）コード川柳でD言語のアピールをしたりして遊んでたら川柳のほうが宇宙ツイッタラーXさんの目に止まったらしく賞をいただけた．去年は id:osyoyu がDDRでベストスコアを出して表彰されていたのでTHANKSで2年連続筑波大生が懇親会表彰を受けるという栄誉ある記録を打ち立てた．来年あったら誰かよろしくお願いします．

D言語 FFTが入ってます #csenryu
— YousackはMマスLVつくば (@antefest) 2015, 12月 5

D言語の話をしていたらなぜか賞をいただけました、ありがとうございます https://t.co/h39jleZNHH #dlang #code_festival pic.twitter.com/hG33u8qyfM
— YousackはMマスLVつくば (@antefest) 2015, 12月 5

まとめ

冒頭にもある通り2年連続のTHANKSということで個人的には不名誉と言うと言葉は悪いもののあまり良いことではないなあと思っていたので心持ちも微妙だったのですが，結果的には今年もD言語で5完できたし順位もそこそこだったしD言語の押し売りが結実したしでやはり今年も参加できてよかったなと思いました．僕は来年就職なので参加資格を失いますが，この大会が学生競プロerの強いモチベーションになっていることは確かだと思うのでこれからも続けていってほしいなあと思います．今年もありがとうございました．

提出した問題の解法とコードは別記事で．

2015-10-12

図解・セグメント木

ARC045#B がセグメント木で殴るタイプの問題だった（頭が良い人は 2 回 imos ると簡単に解ける）んですが僕は頭が悪いのでそろそろ自分でセグメント木を実装できるようになろうと思い立ったのでした．が，調べてみたところいろんなサイトの説明を読んでもなかなか理解できず……．複数のページを見比べて数時間かけてようやく実装できたのですが，どうも文章でしか解説されてないせいで全然理解できなかった気がするのでここではちゃんと図（のようなもの）で示しながら説明していきたいと思います．

セグメント木とは

「配列に対する操作の結果をセグメントごとに保持したもの」を木にしたもの．例えば [2, 3, 8, 4, 1, 5, 7, 6] という配列があったとして，「l 番目から r 番目の要素の中で最小の値は何？」というクエリが何回か投げられるとする (Range Minimum Query: RMQ)．これぐらいのサイズの配列なら単純に全部見比べればいいけど，例えば数が 10 億個並んだ配列の中で「1 番目から 10 億番目までの中で……」みたいなことを 10 万回言われると絶対 TLE で落ちる．で，「あらかじめ「全体の中で最小」「右半分で最小」「左半分で最小」……みたいに再帰的に 2 分割しながら結果を持っとけばいいよね」というアイデアなのがセグメント木．上の配列を使うと，

[           1          ]               0
[     2    ][     1    ]       1,             2
[ 2  ][ 4  ][ 1  ][ 6  ]    3,    4,      5,      6
[2, 3, 8, 4, 1, 5, 7, 6]  7, 8, 9, 10, 11, 12, 13, 14 (k)
                          0, 1, 2,  3,  4,  5,  6,  7 (i) (n = 8)

これは完全 2 分木になっていて，根ノード＝min(左の子，右の子) になっていることが分かる．さらに完全 2 分木にすると何が嬉しいかというと，これを 1 次元の配列で扱えるようになる．上図右は左の 2 分木をルートから BFS で 0-indexed の添字を付けたもので，左の子＝2 * 親 + 1，右の子＝2 * 親 + 2になっている．また，元の配列の長さが 8 で，元の配列の 0 番→ 2 分木配列の 7 番，1 番→ 8番，……という関係なので，元の配列の長さ (8) を n とすると，元の配列の i 番目の要素は 2 分木配列では k = i + n - 1 番目になっている．これで 2 分木配列と元の配列の間でインデックスの変換ができるようになった．

値の更新

セグメント木で出来るのは配列内の 1 要素の更新と，木のある範囲に対する reduce 操作である（max, min, gcd, sum など）．要は親＝操作(左の子，右の子) が常に成り立てばいい．完全 2 分木では，k 番目のノードの親ノードの番号は (k - 1) / 2 （切り捨て）で求まる．ということで，値の更新の擬似コードは以下のようになる：

def update(元の配列の番号, 新しい値)
  2分木内の番号 k = 元の配列の番号 + n - 1
  2分木配列[k] = 新しい値

  while k > 0:
    # 1個上の親に上がる
    k = (k - 1) / 2
    # 子を使って親の値を更新する
    2分木配列[k] = 操作(2分木配列[2 * k + 1], 2分木配列[2 * k + 2])

値の取得

[           1          ]               0
[     2    ][     1    ]       1,             2
[ 2  ][ 4  ][ 1  ][ 6  ]    3,    4,      5,      6
[2, 3, 8, 4, 1, 5, 7, 6]  7, 8, 9, 10, 11, 12, 13, 14 (k)
                          0, 1, 2,  3,  4,  5,  6,  7 (i) (n = 8)

例えば，上図で「元の配列で言う 2 番から 7 番までの中で最小の値が欲しい」と言われたら，2 分木配列の添字を見て，直感的に「2 分木配列で言う 2 番，4 番のうち小さい方を返せば良さそう」と思うだろう．思うことにしよう．で，これはどういう直感に基づいているかというと「2 分木配列のノードの中で，欲しい範囲に完全に包含されておりかつもっとも大きい範囲を担当するノード」を返せばいいことになる（これはたぶん iwi さんのスライド 53 枚目が一番分かりやすい）．そのためには，2 分木配列の k 番目のノードが元の配列で言う何番から何番までを担当しているかを教えながら再帰的に 2 分探索する必要がある．ということで擬似コードは以下の通り：

# この補助関数を getValue(a, b) = __getValue(a, b, 0, 0, n - 1) と呼べば
# 上から順に探索できる
def __getValue(元の配列の左端 a, 同右端 b,
               2分木配列中の番号 k, k番が担当している元の配列の左端 l, 同右端 r):
  if k番が担当している元の配列の範囲 l:r が a:b に完全に含まれている:
    return 2分木配列[k]

  if l:r が a:b から完全に外れている:
    return 単位元（minならint.MAX，sumなら0とか）

  return 操作(__getValue(a, b, 2 * k + 1, l, (l + r) / 2),
             __getValue(a, b, 2 * k + 2, (l + r) / 2 + 1, r))

この関数では，特に l と r が 2 分木内の添字ではなく元の配列の添字を指していることに注意．また，他の例ではよく半開区間で考えると左の子の右端と右の子の左端が同じになって分かりやすいみたいなことが書いてあったけど，僕にはそれをプログラム内でどう扱えばいいのか分からなかったので普通に閉区間にした．ぶっちゃけ開区間とか閉区間の概念を理解していればどっちでもいいと思う．

プログラム例を挙げるだけでは再帰の処理が何をやっているのか分かりづらいので，例を出して処理を追ってみよう．例えば，getValue(2, 7) とすると補助関数の中では変数が以下のように動いている．

             0
     1,             2
  3,    4,      5,      6
7, 8, 9, 10, 11, 12, 13, 14 (k)
0, 1, 2,  3,  4,  5,  6,  7 (i) (n = 8)
2, 3, 8,  4,  1,  5,  7,  6 (元の配列)
      a                   b
l                         r  k = 0     => min(4, 1) => 1
l         r                  k = 1   => min(MAX, 4) => 4
l  r                         k = 3 => MAX
      l   r                  k = 4 => 4
              l           r  k = 2   => 1

2 分木配列の初期化

2 分木配列を初期化するときは，元の配列の長さ以上で最も小さい 2 の冪を求めたあと（完全 2 分木は末端のノード＝葉の数が必ず 2 の冪になる），それ * 2 - 1 の長さで中身を単位元で埋めた配列を用意して，k = i + n - 1 番目から順に update していけばいい．たぶんコンストラクタに元の配列を渡してコンストラクタの中で全部やればいいと思う．

まとめ

セグメント木は，大きい配列の中の部分配列に対する reduce 操作を完全 2 分木を使って出来るようにしたもの
値を更新するときは 2 分木を下から上に辿り，値を求めるときは 2 分木を上から分割しながら辿っていけばいい

間違ったこと・分かりづらいことを言ってるところがあったらコメントください．随時修正します．

ちなみに

これを Python 3 で書いて提出したら TLE になった．悲しい．

Submission #525117 - AtCoder Regular Contest 045 | AtCoder

参考

プログラミングコンテストでのデータ構造 from Takuya Akiba

www.slideshare.net

d.hatena.ne.jp

taku-k.hatenablog.com

2015-07-23

Codeforces Round 313 Div. 2 AからC

Python 3で参加したらデバッグが大変だった．公式のEditorialとほとんど同じだけど一応……．

560A Currency System in Geraldion

貨幣が5種類与えられるので，その貨幣をそれぞれ0回以上使った時にどうしても表現できない最小の値を答える．任意の値を表現できる場合は -1 を出力する．

解法

1 があったら 1 を無限に使うことで任意の値を表現できる．1 が無かったら他の何を使っても 1 を表現できない．これは最小の unfortunate sum．

プログラム

さすがにここまで単純とは思わなくて怖かったけど普通に通った．ちなみに今見たら他の誰かのコードと一致したのか Skipped になってた．そらこんな簡単なの誰かと一致するだろ．だからレート下がったのか．

n = int(input())
a = map(int, input().split())
if 1 in a:
    print(-1)
else:
    print(1)

560B Gerald is into Art

長方形の絵を2つ買った．長方形のでかいフレームの中に収まるかどうかを判定したい．

解法

（横に並べる・縦に並べる），（1つ目の回転），（2つ目の回転）で $2 \cdot 2 \cdot 2 = 8$ 通りある．左上に詰めて置くと考えればいいので，横に並べる時は横の長さが sum で縦の長さが max，縦に並べる時は縦の長さが sum で横の長さが max になることが分かる．8通り全部やる．

プログラム

愚直も愚直．

a1, b1 = map(int, input().split())
a2, b2 = map(int, input().split())
a3, b3 = map(int, input().split())

if (max(a2, a3) <= a1 and b2 + b3 <= b1) or \
   (max(a2, b3) <= a1 and b2 + a3 <= b1) or \
   (max(b2, a3) <= a1 and a2 + b3 <= b1) or \
   (max(b2, b3) <= a1 and a2 + a3 <= b1) or \
   (a2 + a3 <= a1 and max(b2, b3) <= b1) or \
   (a2 + b3 <= a1 and max(b2, a3) <= b1) or \
   (b2 + a3 <= a1 and max(a2, b3) <= b1) or \
   (b2 + b3 <= a1 and max(a2, a3) <= b1):
    print("YES")
else:
    print("NO")

560C Gerald's Hexagon

正三角形から成る六角形の中に詰まっている三角形の数を数える．

想定解法

始めに，正三角形から成る正三角形は，上の列からそれぞれ個数を数えると 1, 3, 5, … というように奇数列になっていることが分かる．奇数列は $2k - 1$ で表せるので，この sum を取ると ${n}^2$ になることが分かる．問題で与えられるような六角形は，1辺が $a_1 + a_2 + a_3$ の大きい正三角形から上と右下と左下の小さい正三角形を削り取ったものと考えられるので， ${(a_1 + a_2 + a_3)}^2 - {a_1}^2 - {a_3}^2 - {a_5}^2$ で答えが求められる．Editorial もうちょっと詳しく書いてくれ．

プログラム

想定解法とは違うやり方で提出していました．だいたい同じですが，平行四辺形を作って右上と左下を削るみたいな計算をしました．上底の長さは $a_1 + a_2$ で，1列にはその2倍の三角形が詰まっているので，平行四辺形の中にはそれに高さ $a_2 + a_3$ を掛けた分だけ三角形が詰まっています．後は右上と左下を上と同じように引くだけ．奇数列の総和が ${n}^2$ という公式に辿り着くまでの計算を渋って補助のメソッドを書いたのがダサい．ちなみにこの解法の式を整理したら $2(a_1a_2 + a_2a_3 + a_3a_1) + {a_2}^2 - {a_5}^5$ とかいう基本対称式の線形結合みたいな式が出てきて特別綺麗でもなく何とも言えない気持ちになりました．

def f(x):
    ans = 0
    for i in range(1, x + 1):
        ans += 2 * i - 1

    return ans

a = list(map(int, input().split()))
print((a[0] + a[1]) * 2 * (a[1] + a[2]) - f(a[1]) - f(a[4]))

DとEは愚直に書いたら両方TLEで落ちた．お疲れ様でした．C問題はDiv 1のA問題なわけだしこれからもコンスタントにDiv 2で3完していきたいなあと思いました．

2015-07-07

PRML 演習9.3

こんなところにもやるだけの問題が．

混合ガウス分布の問題．2値確率変数 $\boldsymbol{z}$ は1-of-K符号化されていて，

$\displaystyle p(\boldsymbol{z}) = \prod_{k=1}^K \pi_k^{z_k}\\ \displaystyle p(\boldsymbol{x}|\boldsymbol{z}) = \prod_{k=1}^K \mathcal{N}(\boldsymbol{x}|\boldsymbol{\mu_k}, \Sigma_k)^{z_k}$

とする．このとき $p(\boldsymbol{x},\boldsymbol{z}) = p(\boldsymbol{z})p(\boldsymbol{x}|\boldsymbol{z})$ だから，

$\begin{align} p(\boldsymbol{x}) &= \sum_{\boldsymbol{z}} p(\boldsymbol{x},\boldsymbol{z}) = \sum_{\boldsymbol{z}} p(\boldsymbol{z})p(\boldsymbol{x}|\boldsymbol{z}) \\ &= \sum_{\boldsymbol{z}} \left\{ \prod_{k=1}^K \pi_k^{z_k} \prod_{k=1}^K \mathcal{N}(\boldsymbol{x}|\boldsymbol{\mu_k}, \Sigma_k)^{z_k} \right\}\\ &= \sum_{\boldsymbol{z}} \prod_{k=1}^K \pi_k^{z_k} \mathcal{N}(\boldsymbol{x}|\boldsymbol{\mu_k}, \Sigma_k)^{z_k}\\ &= \sum_{\boldsymbol{z}} \prod_{k=1}^K \left\{ \pi_k \mathcal{N}(\boldsymbol{x}|\boldsymbol{\mu_k}, \Sigma_k) \right\}^{z_k} \end{align}$

総積の部分は典型的な1-of-K符号化の確率の形になっている．これを $z_1 = 1$ のときから $z_K = 1$ のときまでのものを全部足し合わせればいいので， $k$ についての総和になる．よって

$\displaystyle p(\boldsymbol{x}) = \sum_{k=1}^K \pi_k \mathcal{N}(\boldsymbol{x}|\boldsymbol{\mu_k}, \Sigma_k)$

これ以外の問題は全然分からない．

矮小

井の中の蛙

Codeforces Beta #92 Div2.A "The number of positions"

問題

考え方

ソースコード

夢屋の隠れ大盛り／夢屋，コスパを求めて

About Me

夢屋の隠れ大盛り

夢屋，コスパを求めて

卒論書いた

CODE THANKS FESTIVAL 2015 参加記

経緯

行く前

当日

コンテスト中

懇親会

まとめ

図解・セグメント木

セグメント木とは

値の更新

値の取得

2 分木配列の初期化

まとめ

ちなみに

参考

Codeforces Round 313 Div. 2 AからC

560A Currency System in Geraldion

解法

プログラム

560B Gerald is into Art

解法

プログラム

560C Gerald's Hexagon

想定解法

プログラム

PRML 演習9.3