競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 215 メモ 高速きたまさ法

間違ってるかもしれないけど解法の方針が分かった気がした。 実装している時間がないのでとりあえずメモまずM項間漸化式をで作成する。 これはEASY,MEDを解いてる人ならできてると思うので省略。 きたまさ法の説明は省略。 剰余環での畳み込み和をフーリエ変…

ARC #039

ARC

あまり更新をしている暇はないけれどB問題のもやもやが晴れたのでメモ。 D問題はまだ解いてないです。 コンテスト本番はCの実装が間に合わず200点 - A問題「A - B Probrem」 (http://arc039.contest.atcoder.jp/tasks/arc039_a)問題概要: 3桁(100以上999以下…

yukicoder 24/25/26

- 24 数当てゲーム 問題概要 0から9までの数字に一つだけあたりの数字があります。 4つの数字が与えられ,その中に当たりの数字が含まれていないならNO,含まれているならYESが与えられます。 これが複数回与えられ、答えが特定できるような入力が与えられるの…

yukicoder 21/22/23

- 21 平均の差 問題概要 N個の数字をK個のグループ(要素数が1以上)に分けます。 グループ内の数字の平均値が最大のものと最小のものの差が最大になるようにグループ分けをしたときの差を答えよという問題です。 解説 タイトル詐欺です。 平均を最大にする組…

yukicoder 18/19/20

- 18 うーさー暗号 問題概要 文字列の復号をします。 文字列の暗号方法がi文字目の文字をi回右にずらす(Aを2回ずらすとC,Zを1回ずらすとA)という変換をします。 暗号が与えられるので復号した文字列を出力してください。 解説 逆の操作をするだけです。 i回…

yukicoder 15/16/17

- 15 カタログショッピング 問題概要 合計金額と、各商品の金額が与えられます。 何を買ったのか答えてくださいという問題です。 解説 商品の金額が小さければDPの典型です。 DPで解きたいのですが商品の金額が大きすぎるためTLEになってしまいます。 商品数…

yukicoder 12/13/14

- 12 限定された素数 問題概要 ある整数の区間[L,R]を選んだとき、その区間に含まれる全ての素数の各桁に使われる数字(0~9)を調べる。 0~10の整数が与えられ、区間に含まれる全ての素数の桁にちょうどのみが使われる[L,R]のうち、最大のR-Lを求めよという問…

yukicoder 9/10/11

- 9 モンスターのレベル上げ 問題概要 モンスターのレベル上げをする。 手持ちのモンスターの一番弱いもの(レベルが一番低い、複数いるなら一番戦闘回数が少ない)を戦闘に参加させます。 敵モンスターが円上に並んでいて、どこから戦闘を始めてもいいとき、…

yukicoder 6/7/8

なんか素数扱う問題がやけに多い気がします。 - 6 使い物にならないハッシュ 問題概要 ある素数pの各桁の和をp'とします。p'が二桁以上ある場合はもう一度各桁の和をとりそれをp'とします。 p'が一桁になったとき,それをp'のハッシュ値とします。 K,Nを素数…

yukicoder 3/4/5

GWのうちに問題数を稼ぐ - 3 ビットすごろく 問題概要 10進数kを2進数に変換したとき,ビットが1になっている部分の個数をbit(k)とする。 頂点kからはk-bit(k),k+bit(k)に移動することができる。 1からNに移動するときの最短距離を求めてくださいという問題で…

yukicoder 1/2

1は20分、2は諦めて解説読みました。 2の解法が衝撃的でした。 - 1 道のショートカット 問題概要 1,,,Nの番号がついた町があります。 道路がM本あって各道路には移動に必要な時間とお金が設けられています。 道路は一方通行で、番号の小さい町から大きい町へ…

yukicoder 199/200

4/28に行われたコンテストの後半です。 3問目までは解けたのですが4問目の解法が全く思いつかず3完 - 199 星を描こう 2次元座標の点が5つ与えられます。 どのような順で結んでも良いので星を描くことのできるかどうか判定せよという問題です。 解説 5角形の…

yukicoder 197/198

見やすさを維持するのと負担軽減のために問題数が4問以上のときは分割します。 - 197 手品 思いつくのは10秒かからなかったけど実装に10分ぐらいかかった() 問題概要 一列に並んだ3個のハットの中にボールがいくつか配置されていて、K回ハットの位置を交換し…

yukicoder 194/195/196

yukicoder open 2015 small後半 コンテスト中解けなかった3問になります. 6問目があと20分あれば解けたので悔しいです. 早解きの練習をしてもっと早く解けるようになりたいです. - 194 フィボナッチ数列の理解(1) 問題概要 初項 で与えられる数列のを求めよ…

yukicoder 191/192/193

yukicoder open 2015 small前半 一応この3問はできました。 ICPCを意識してマクロ縛りをしています。 - 191 供託金 問題概要 得票数が全票数のうち1/10に満たない候補者数*30を出力せよという問題です。 ざっくりです。 解説 for文で計算するだけなのですが…

ABC#022

ABC

なぜかタイトルイニシャルが全てBBのABC ライブラリの用意不足により実装時間が足らず3完部分点で撃沈しました. - A問題「Best Body」 (http://abc022.contest.atcoder.jp/tasks/abc022_a)問題概要: 体重の変化記録が与えられるので,S以上T以下であった日数…

yukicoder 188/189/190

本番20分遅れで参加して189から解き始めたが実装時間が足らず0完。 yukicoder3問を1時間で解ききるのが今のところの目標です。 yukicoderは時間設定が短すぎる気がします。 188 HAPPY DAY - 問題概要 2015年のxx月yy日について、xx=yyが成り立つ日の数を出力…

ABC #021

ABC

ちょっと前だけど実際に参加したコンテストです。 modについてCodeChefでたくさん戯れたおかげで今までで最速の全完出せました。 しかしちょっともたついた部分もあったので反省です。 - A問題「足し算」 (http://abc021.contest.atcoder.jp/tasks/abc021_a)…

CodeChef April long Challenge 2015 まとめ

4/3~4/13日の十日間開催。 初めて長期開催のコンテストに参加したがすごく勉強になるアルゴリズムが多かった。 これのせいでしばらく更新できなかったのでその穴を埋めていきます。 結果は8完+部分点2つ(92.14+13)で905.14点。全体27位でした。 Broken Tel…

CodeChef April long Challenge 2015 Black-white Board Game(BWGAME)

注:この記事はCodeChef終了後に更新しています。 本番中解けませんでした。 自分なりに理解して実装してみたのですが計算量が怪しいです。 - 問題概要 N*Nマスのボードがあります。 i行について、までのマスが黒色に塗りつぶされています。 黒じゃないマス…

CodeChef April long Challenge 2015 Little Party(LPARTY)

注:この記事はCodeChef終了後に更新しています。 ACできた問題。まさか論理回路系の問題が出るとは。 全体のAC人数が最も少ない問題となっていますが絶対にBWGAMEのほうが難しいと思う、、、 - 問題概要 上手く問題文が読めなかったので上手く訳せているか…

CodeChef April long Challenge 2015 Chef and Array(FRMQ)

注:この記事はCodeChef終了後に更新しています。 RMQの手法が沢山あることを知ることができた問題です。 空間計算量O(N)の方法もあるらしいですがちょっと難しそうだったのでわかりやすいスパーステーブルに逃げました。 - 問題概要 N個の数字が与えられま…

CodeChef April long Challenge 2015 Broken Telephone(BROKPHON)

注:この記事はCodeChef終了後に更新しています。たぶん一番簡単です。正答数も一番高いです。 - 問題概要 N人で壊れた電話を使って数字の伝言ゲームをする。壊れている電話は正しく数字を伝えることができない。 ゲーム終了後にN人にインタビューをし、どの…

yukicoder 175/176/177

初めてのyukicoder参加。 176で詰まり結果1問どまりです。 177を先にやればよかった。 175 simpleDNA - 問題概要 A,Bを好きなだけ使ってL文字の解のうち、指定された終端3文字を含む文字列は何文字あるか答えよ。 - 解法 指定された終端3文字の種類をNとする…

東京大学プログラミングコンテスト(UTPC)2014 D問題 ラボライブ タフグローバルフェスティバル

http://utpc2014.contest.atcoder.jp/tasks/utpc2014_d タイトルがすごい、、、 状態数がとても増えそうだったので本番中飛ばした問題です。 complexのrealとimagをいちいち入力するのが面倒でどうしたものか考え中です。 - 問題概要 m本の指の初期位置とn個…

東京大学プログラミングコンテスト(UTPC)2014 F問題 チェックディジット

http://utpc2014.contest.atcoder.jp/tasks/utpc2014_f 本番中時間がなくて露骨に部分点を狙いにいった問題。 一度見た問題は解かないと気が済まないので満点出すまでやりました。 - 問題概要 10桁の整数がT個与えられます。 整数が入力したとき整数を出力す…

東京大学プログラミングコンテスト(UTPC)2014 E問題 宝くじ

初めてのSegment-Tree 値を二つ持つタイプのSegment-Treeです。 ちなみに本番では解けてません。 - 問題概要 宝くじの実況中継をします。 当選番号aと賞金bが発表されます。 このとき、宝くじの番号の下桁がaであるとき賞金bがもらえます。 この(a,b)がn回与…

東京大学プログラミングコンテスト(UTPC)2014 A,B,C問題

以下本番中に解けた問題です。 1時間遅れで参加して3問とFの部分点で83位でした。 4問+部分点はいけるようになりたいです。 - A問題「二重否定除去法則」 (http://utpc2014.contest.atcoder.jp/tasks/utpc2014_a)問題概要: not not 何か という文字列の並び…

ABC #020

ABC

昨日参加したコンテスト。 D問題が難しすぎたため全完ならず315点。 - A問題「クイズ」 (http://abc020.contest.atcoder.jp/tasks/abc020_a)問題概要: 1が入力されたら大会の名前、2が入力されたらAtCoder社長のハンドルネームを出力するというもの。 社長の…

TopCoder SRM 144 div2

はじめてのTopCoder過去問。 一番最初のdiv2を解いてみました。 結構時間による減点がシビアでびっくりしてます。 普段はVisual Studioを使っているのですがTopCoderの環境にVSが適してないっぽいのでeclipseCoderプラグインをつかってeclipseでコーディング…

幾何コンテスト C:泥棒

突然の幾何コンテスト。 幾何ライブラリを前々から作るべきだと思っていたので軽い気持ちで解き始めたら痛い目を見ました。 - 問題概要 http://geocon2013.contest.atcoder.jp/submissions/363487C: 泥棒 - 幾何コンテスト2013 | AtCoder泥棒が(0,0)のアジト…

Indeedなう 予選B 全部

リアルタイムで解いた問題です。 開始時間が15分遅れていなければ20位ぐらい上がっていたかも。 何はともあれ全完で一安心。 - A問題「高橋君とマンハッタン」 (http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_1)問題概要: 京都みた…

UVa 111 - History Grading

UVa

- 問題概要 n個の整数が与えられます。 これはi番目のイベントが番目に発生することを示している。 学生の提出したテストが続いて与えられ、 i番目のイベントが番目に発生したと記述されています。 最も長い正しい年代順の部分列長を答えよという問題です。 …

Indeedなう 予選A D:パズル

実際に参加して解けなかった問題です。 大事なことを二つほど学びました。 - 問題概要 H*Wのスライドパズルが与えられます。 このパズルを解くのに必要な最小の移動回数を答えよという問題です。 移動回数の最小値は24回以内であるという入力の制約が存在。 …

UVa 110 - Meta-Loopless Sorts

UVa

-問題概要 Pascalのソースコードを出力するソースコードを書けという問題です。 メタプログラミングといってもいいのかな? 条件としては変数名をアルファベットとして宣言し、readlnを使って入力処理。 繰り返し分を使わずにif文のみでソートを行うプログラ…

Typical DP Contest T:フィボナッチ

解くのに1年かかった問題です。 Typical DP Contest、通称TDPCと呼ばれるDP限定のAtCoderで開催された過去のコンテストの問題。 TDPCはDPの練習にもってこいだと思います。 - 問題概要 N,Kが与えられ、Kボナッチ数列のN項目を出力せよという問題です。 - 解…

m項間漸化式の高速なアルゴリズム

3/22:テンプレート追加しました。m項間漸化式のk項目を高速に求める方法。通称「きたまさ法」と呼ばれるアルゴリズムについての(簡単な)解説。 考案者が蟻本作者の方でその名前からとられたみたいです。計算量は 入力 第k項: 初項 : で定義されるm項間漸化…

C++のvectorの比較のお話

問題じゃないけど重要なことなのでメモ。 C++のvectorはvectorオブジェクトに対して比較演算子が定義されている。 これはvector配列を辞書順で比較する。 2次元のvectorに対してsortを使えば辞書順での昇順になるしmapのキーにも使える。 盤面を二次元配列で…

UVa 109 - SCUD Busters

UVa

今までで一番読みづらい英文でした。 幾何ライブラリを作るべきだと思った問題です。 - 問題概要 王国同士が戦争をしています。 一つの王国は発電所一つと複数の民家で構成され、王国の領地は最も外側の民家もしくは発電所で囲まれています。すなわち、発電…

AOJ 0068 - Enclose Pins with a Rubber Band

AOJ

趣向を変えてAOJの問題を解きます。 この問題で使うアルゴリズムが次に解く予定の問題に必要なので確認のために解きました - 問題概要 n個の釘のxy座標が与えられます。 すべての釘を一本の輪ゴムで囲んだとき、輪ゴムに触れていない釘は何本あるか。 - 解法…

UVa 108 - Maximum Sum

UVa

- 問題概要 N*Nの重みつき正方形、もとい行列が与えられます。 考えうる部分行列の要素の和の最大値を求めてください。 - 解法 部分累積和問題の基礎中の基礎の問題です。 入力で与えられる行列のi行j列目の要素をm(i,j)とし、 (1,1)から始まるi*jの大きさの…

UVa 107 - The Cat in the Hat

UVa

今回からfor文のマクロを一新してみましたが結局repを使っております。 慣れたものを使うほうがやはり早いのでしょうかね - 問題概要 猫のお話です。 ある身長の猫がいます。その猫は自分が働く代わりに身長が自身のの猫をN匹働かせることができます。 同様…

UVa 106 - Fermat vs. Pythagoras

UVa

C++でinlineというテクニックを覚えました。 再帰をしないが何度も使用する関数に用いるとメモリの許す限り高速化が図れるということなので意識していきたいと思います。 繰り返しのマクロ文が何が適切なのか定まらなくてもやもやします。 今まではrep(i,a,b…

UVa 105 - The Skyline Problem

UVa

ようやく当日投稿が間に合いました。 ABCが全て終わってしまったのでとりあえずUVaを解いていこうと思います。 - 問題概要 ある町があって、ビルが並んでいます。 ビルのx座標の左端、右端、z座標の高さが与えられ、y軸上の十分に遠いところから町を眺めたと…

UVa 104 - Arbitrage

UVa

WA出しても正答率が分からない恐怖。 問題の読みとばしが原因のWAだったので反省。 - 問題概要 Arbitrage、すなわり価格差を利用して利益を得る取引のことです。 裁定取引や鞘取引といったりもするそうです。 ある物品A,B,Cがあって、 AをBに交換、BをCに交…

UVa 103 - Stacking Boxes

UVa

UVa第3回です。 今回は英語がパッと見理解不能だったので翻訳に英文丸ごと突っ込んだのですが 余計わけわからなくなったので結局自力で読みました。 - 問題概要 n個の数字が入った箱がk個存在します。 二つの箱(c,dは整数)について、 を並び替えてできたがを…

ABC#019

ABC

リアルタイムで解いた問題。 スタート時間が遅かったが何とか時間内に全完しました - A問題「高橋君の年齢」 (http://abc019.contest.atcoder.jp/tasks/abc019_1)問題概要: コンテスト中は中央値という単語しか見えなかったので問題文を読んでいませんでした…

ABC#018

ABC

修正予定地 - A問題「」 (http://abc018.contest.atcoder.jp/tasks/abc018_1)問題概要: 解法: ソースコード: [] - B問題「」 (http://abc018.contest.atcoder.jp/tasks/abc018_2)問題概要: 解法: ソースコード: [] - C問題「」 (http://abc018.contest.atcod…

ABC#017

ABC

修正予定地 - A問題「」 (http://abc017.contest.atcoder.jp/tasks/abc017_1)問題概要: 解法: ソースコード: [] - B問題「」 (http://abc017.contest.atcoder.jp/tasks/abc017_2)問題概要: 解法: ソースコード: [] - C問題「」 (http://abc017.contest.atcod…

ABC#016

ABC

修正予定地 - A問題「」 (http://abc016.contest.atcoder.jp/tasks/abc016_1)問題概要: 解法: ソースコード: [] - B問題「」 (http://abc016.contest.atcoder.jp/tasks/abc016_2)問題概要: 解法: ソースコード: [] - C問題「」 (http://abc016.contest.atcod…