あったこといろいろ

ほぼ自分用備忘録です。

ARC088D Wide Flip

D - Wide Flip 前提 x を 0 以上 |S|-1 以下の任意の整数とすると、[0,x-1]の区間を反転した後に[0,x]の区間を反転するとS[x]のみ反転させることが可能である。 K 解法 全ての要素を '0' または、全ての要素を '1' とするためには、隣接する要素が異なるよう…

ICPC引退を期に競技プログラミングに出会ってからの4年半を振り返る

この記事は、 「競プロ!!」 競技プログラミング Advent Calendar 2017 22日目 の記事です。公開が大幅に遅れてしまい申し訳ありませんでした。 はじめに 本記事は、「ICPCをきっかけに競技プログラミングに出会い、4年半の間ICPCに出場し続けた競技プログラ…

ICPC2017 国内予選 参加記

ゆらふなさん( @yurahuna )とらてあくん( @ratetion )と、「sparsely_populated_regions」というチーム名で参加しました。 チーム名は限界集落の英語表記*1で、口に出して読むと575っぽくなっているのがポイントです。 結果はABCDの4完 35位で、アジア地区に…

プログラミングにおける「半開区間」

はじめに プログラム中では、区間は 閉区間 や 半開区間 など様々な方法で扱うことができます。 扱い方によって実現できる処理が変わることはありませんが、意識的に統一しておかなければバグを生む要因となります。区間の扱いかたのうち、半開区間の特徴を…

AOJ 2527 MLE

問題 MLE | Aizu Online Judge 解法 そのままソートすると時間計算量O(NlogN)でTLE、空間計算量O(N)でMLEする。 そこで、乱数列の各要素の上位16bitをキーにしたバケットソートみたいなことをする。 k 番目の値を調べる部分では、値が小さいキーから順に辿っ…

RUPC2017参加記

RUPC2017の運営・作問・参加をしました 1日目 卒業式がRUPCと被っていたため早朝に大学へ移動した。 会場ではなぜかn_vipさんが保護者席にいて "学部長のありがたい話" の実況をしていてシュールだった。 卒業しながらコンテストを開催するのは初めてだった…

AtCoder上で過去に提出したソースコードをローカルに保存する

この記事は、Competitive Programming Advent Calendar 2016(その2)の9日目の記事です。 ACしたソースコードは削除してしまう運用をしていましたが、ふと過去に提出したソースコードをローカルに保存したくなったので、プログラムを書きました。 同じ気持…

色々なアルゴリズムで「殴る」

この記事は、Competitive Programming Advent Calendar 2016 の7日目の記事です。 あなたは、一部の競プロ勢の間で使われている「セグ木で殴る」という言葉をご存知でしょうか?priority_queueを使えば良いところをセグ木で解いてみたり*1、累積和を使えば良…

橋・二重辺連結成分分解

この記事は、Competitive Programming Advent Calendar 2016の記事……ではなく、僕のAdCの記事を楽しむための予備知識として書かれた記事です。 ちなみに、僕の担当は明後日です。よろしくおねがいします。 グラフ上の「橋*1」となる辺を求め、これによりグラ…

ICPC2016アジア地区つくば大会参加記

10/15~16 に行われたICPCつくば大会に、チームmiyazoy72で参加しました。pic.twitter.com/5Mg3y4EAol— やざてん (@Yazaten) October 15, 2016 最終成績は45チーム中42位と、非常に悔しい結果となりました。チーム練習としては会津さんがvirtual arenaで開い…

ARC056 C問題 部門分け

想定解だと思って書いた解法が、どうやらそうではなかったようなので書きます。 問題 C: 部門分け - AtCoder Regular Contest 056 | AtCoder 解法 最小カットを使います。部門を分割することによって幾つかの絆が切られる事を考えると、ある部門を2つに分割…

ICPCアジア地区つくば大会D問題 「Hidden Anagrams」

※これは参加記ではありません。参加記は別記事で上げます。問題: AIZU ONLINE JUDGE 問題概要 長さ 4000 以下の S1 と S2 が与えられる。 文字列Sの部分文字列を S' と呼ぶことにする。 「S1' が S2' のアナグラムとなるもの」のうち最長のものの長さを求め…

会津合宿2016参加記

9月の17日〜19日に開催された会津合宿2016に参加しました。 会津合宿数日前~前日 大学で一日中作問作業 会津合宿day1 立命館大学セットの作問を担当していました。 講評・解説・入出力ケースは右のリンクから閲覧できます。public - Google ドライブ 会津合…

JAG夏合宿2016参加記

9月の2日~5日にかけて開催されたJAG夏合宿に参加しました 1日目 東京到着・ガイダンス 夜行バスで早朝に到着したので、yurahunaさん,37dbyeさん,T.M君と新宿のロッテリアでたむろしていました。ガイダンスまでは時間があったので、模擬地区2012をyurahunaさ…

NAIST受験記

NAIST 情報科学研究科 第1回 の試験を受験しました。結果は合格で、学生宿舎優先入居の権利もいただきました。どの結果が功を奏したのかはわかりませんが、何かの参考になれば幸いです。NAISTの試験は主に 小論文・数学・英語・面接 からなります。 小論文 A…

ICPC2016 国内予選 コード置き場

ICPC2016 国内予選の問題を解いたコードを載せておきます。 解法の説明はざっくりです。参加記はこっちです。 ICPC2016 国内予選 参加記 - あったこといろいろ問題文はこっちです。 All Problems A問題 ソートして、隣り合う要素の差の最小値を出力 #include…

ICPC2016 国内予選 参加記

先輩( @LazyMii )と後輩と、「miyazoy72」というチーム名で参加し、33位でした。 恐らくアジア地区予選に出場できるのではないかと思います。「SIMrit」という、熱意のある学内のライバルチームも参加していたので、学内1位の順位を取れたのは本当に運が良か…

AOJ 2282: Problem B

Problem B | Aizu Online Judge 問題が長くてややこしいけれど、考察すると意外と簡単 考察・解法 問題文を素直に読むと自分より前の申請を考慮した場合分けが必要に見えるが、考えると実は不要であることがわかる。 申請の時点で自分が担当者にならない申請…

RUPC2016参加記

参加記です 問題の概要が雑であることなど、参加者でないと理解不能な内容があるのはご容赦ください day1 立命館大学セット B問題とD問題の作問を担当していました。 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=B http…

AOJ 0151: Grid

Grid | Aizu Online Judge実装が面倒なやるだけっぽいですが、DPで書くとさくっと解けました。 遷移 左から、左上から、上から、右上からの4パターン。 状態の持ち方 dp[i][j][0] = i 行目 j 列目まで見た時、横向きにいくつ連続しているか dp[i][j][1] = i …

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B問題 ディスコ社内ツアー

コンテスト中に解法を思いつけなかったので、AtCoderの解説とTwitteを参考に解きました。 問題 B: ディスコ社内ツアー - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder 面白さがそれぞれA_iの部屋が環状にならんで…

CODE FESTIVAL 2015 参加記まとめ

CODE FESTIVAL 2015 の参加記まとめが少し寂しかったので、僕が観測できた範囲の参加記をメモしておきます。togetter版 -> CODE FESTIVAL 2015 参加記まとめ - Togetterまとめ 参加記 投稿日が新しい順に並んでいます。 CODE FESTIVAL 2015 参加記 - あった…

CODE FESTIVAL 2015 参加記

CODE FESTIVALの参加記です。 前日 自費前泊したかったが試験があったので断念 当日遅刻が怖いので21時くらいに寝ました。 1日目 3時過ぎに起きる 今起きたからこどふぇす当日入り余裕っぽい— やざてん (@Yazaten) November 13, 2015新幹線の切符の予約予約…

ラズパイでMeCab-Pythonを使えるようにした

このへん見ながらやった MeCab: Yet Another Part-of-Speech and Morphological AnalyzerUbuntu12.04にMeCabをインストールする - Pythonに萌えているか - Is Python Burning?Ubuntu 10.04にMeCabをインストール - へにゃぺんて@日々勉強のまとめ

ラズパイの固定IPの設定をイジった

ルータを買い替えたので固定IPの設定をイジった。 /etc/network/interfaces を変更してもwebページが見れなかった/etc/resolv.conf に書かれたDNSが古いルータの時のままになってて、書き換えたらできた 参考文献 固定IPアドレスの設定

RUPC2015参加記

いまさらだけど2週間くらい前にあった立命館大学競技プログラミング合宿の参加記です day1 集合30分前頃に立命館大学到着。同じバスに乗っていた にっしーさん、ぬまさん、向日葵さんと会場へ お昼ごはんに学内のSUBWAYに行きたかったけど、時間がなかったの…

東京へハッカソンに行きました

3/23[月]~3/27[金]の5日間ハッカソンへ行きました 一日目 朝ごはん メロンパンを食べました 昼ごはん 宝田水産 八重洲地下街店 (東京/寿司)tabelog.com 晩ごはん ハッカソン先でピザを食べました 二日目 朝ごはん ホテルでビュッフェ形式のやつを食べました …

思い出の問題を解いた

ICPC2013国内予選Cの 階層民主主義 ( Hierarchical Democracy | Aizu Online Judge )を解きました。 2013年7月 ICPC国内予選 興味本位で出たICPC国内予選でこの問題を読み、全くもって意味がわからなかった。*1当時は プログラミングチョットデキル と天狗に…

CODE FESTIVAL 参加者の参加記一覧

たくさん参加記読みたいし、需要もあるっぽいのでつくった (togetter版はこっち CODE FESTIVAL 参加記まとめ - Togetterまとめ) 参加記収集アルゴリズム これに引っかからなかった場合、ここにまとめられていない可能性が高いです。 「("code" "festival”) O…

Yosemite で MinecraftとかArduino IDEとかが起動できなかった

MinecraftとかArduino IDEのappファイルを起動しようとすると、以下のように「"Minecraft.app"を開くには、以前の JavaSE 6 ランタイムをインストールする必要があります。」とか言われた。適当にググったらなんとかなった。 使用した環境 MacBook Air (11-i…