個人的に好きなタイプの問題だったので久しぶりに解説を書きます。 問題 アルファベット小文字('a'-'z')からなる任意の文字列を考える。 長さN以下、含まれる文字の種類数K以下の回文の個数を求めなさい。 ただし、数が大きくなりうるので1234567891の剰余を…
これはCompetitive Programming Advent Calendar Div201315日目の記事です。今回は順列について少し扱おうと思います。 と言っても、僕はそこまで深く順列の知識があるわけでもないので、 こういったことを知っていると問題を順列に帰着したときに役に立つか…
これはCompetitive Programming Advent Calendar Div201315日目の裏記事です。どうも〜、Darseinでーす！ 今までに出題されたD問題のモノマネしま〜す！まずはじめは、会津合宿2013 Day3 D 「Change」 ディー氏「ハフハフハフハフハフハフハフハフ」 続きま…
これはあずにゃん Advent Calendar14日目の記事です。いつもあずにゃんあずにゃん言ってますが実はあずにゃんグッズは「あずにゃんまったりぬいぐるみ」しか持っていないです。 家族とかに見られるの恥ずかしいなーというタチなので、そもそもがアニメグッズ…
これはあずにゃんAdventCalendar12日目の記事です。ぺろぺろ。 (プロコン日記と言ってるけど他にブログ持ってないのでここに書きます。ごめんなさい。)さて、あずにゃんのかわいさの象徴といえばツインテールですよね。 日本ツインテール協会によると、 あず…
会津合宿Day1のD問題に「与えられた真理値表に対応するBDDを構築し、頂点数を求めよ」という問題が出ました。 想定解法は「二分決定木作って頑張って簡約化」らしいですが、これはBDDを構築しなくても解けます。変数をx1,x2,...,xn、与えられた真理値表を表…
2013年ICPC国内予選のA~Dまでの解説らしき何かを書きました。 問題はこちら A 問題： h×wの横長(h 対角線の長さが短い方が小さい 対角線の長さが等しければ、高さが短い方が小さい 与えられた長方形より大きい長方形の中で、最小のものを求めよ。解法： 制約…
Mac Book Pro Retina 13インチ(OS X Mountain Lion 10.8.3)を買いました。初Macです。今回Macを買った理由としては、 Mac使い、なんかかっこいい：厨二病 今のPCが不調だった：キーボードが不調・処理が重い 今の環境に不満があった：コーディングはTerminal…
A,B,C,Dsmallを解きました。問題はこちら A. Tic-Tac-Toe-Tomek 所謂四目並べの盤面が与えられるので、勝・敗・引き分け、あるいはまだ進行中かを答える問題。 解法： さすがにやるだけ。 縦・横・対角のX,O,Tの数をカウントして、X(or O)が4つ、または3つ +…
この記事はCompetitive Programming Advent Calendar Div2012、20日目の記事です。(余談：そういえば本日2012/12/20は良い日ですね！) はじめに 今回はDonald.E.Knuth著”The Art of Computer Programming”のVolume4-1の前半パートであるBitwise Tricks & Tec…
9/3〜5に会津大学で行われた競技プログラミング合宿に参加してきました。この合宿は毎日3〜5時間程度のコンテストを行い、実力向上を目指すのはもちろん、他大学の人と一緒にチームを組むなど、普段会えないような人達と交流を深めることも目的となっていま…
変数を含んだ式が文字列として与えられるので、別情報として与えられる単位系の関係から、式が表している単位を求める問題。 errorになるケースでは空のvectorが返り値になるように処理しています。 #include<iostream> #include<string> #include<map> #include<vector> #define pb push_ba</vector></map></string></iostream>…
HUPPC #1で取り上げた問題について、僕の想定解法＋αを解説します。 コードに関しては、Aizu Online Judge→Virtual Arena→Contest→HUPPC #1→Standingと進めば参加者のコードが読めるようになっていますので、そちらを参考にして下さい。 A. Sum of Consecuti…
若輩者ながらCompetitive Programming Advent Calendarに参加させていただきます。 僕のは体験談のようなものなので、気軽に読んでください&長文で申し訳ないです。 今回は大学の授業としてICPC国内予選を突破するための対策を行ったときの話をしようと思い…
とりあえずテスト投稿です。この日記はCompetitive Programming Advent Calendar用に作ったものです。 今のところそれ以外の用途に使うつもりはありません。 気が向いたらもしかしたら、 TopCoder codeforces AOJ などの問題を取り上げて、解法等について書…
