gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

ACM-ICPC

ACM-ICPC 大崎(Osaki) 

問題 Osaki | Aizu Online Judge電車が走行する時間帯が与えられるので、最低電車が何台あれば運行できるかを出力する。解説 入力の運行時間が少しでも被っていれば、その時間帯は複数の電車が運行しないと矛盾してしまいます。よってすべての運行時間を見て…

ACM-ICPC When Can We Meet?

問題 When Can We Meet? | Aizu Online JudgeN人分の空いている日程が与えられるので、M人以上が参加できる日程の中で最も多くの人が参加できる日程を出力します。同じ人数参加できる日が複数存在する場合、一番早い日を出力します。解説 N人分のデータが与…

ACM-ICPC 「月曜土曜素因数」

2008のB問題です。問題 Monday-Saturday Prime Factors | Aizu Online Judge 素数とは、「1と自分以外に約数を持たないもの」です。普段はこれを「すべての自然数」について考えていますが、これを「7で割ると1または6余る数の集合」に絞って考えるとど…

AOJ-ICPC 「Prime Gap」

問題 Prime Gap | Aizu Online Judge素数を並べた要素数10^5の数列 { 2,3,5,7,11,13,17....1299709 } がある。この時、「prime gap」を考える。例えば、10であるときには、数列の[7 11]の間に入るので、prime gap は11-7=4となる。解説 上の問題文は要約です…

AOJ-ICPC 「君のプライバシーを守れ!」

問題 Save Your Privacy! | Aizu Online Judge解説 少し入力がめんどくさいのですが、一つずつ流れを追えば大丈夫です。結局、解答が定まる時は、「各データセットの最後にあるK個ある番号を、全部知っている構成員がただ1人いる時」です。情報を漏らした構…

AOJ-ICPC 「審判は君だ!」

問題 You Are the Judge | Aizu Online Judge解説 問題の方針は「ICPCの順位づけ」と変わりません。ほぼ同じ問題です。 gotutiyan.hatenablog.com正解したかどうかのAC、不正解数のWA、ペナルティのtimをそれぞれ準備して、R個のデータについて格納していき…

AOJ-ICPC 「王様の視察」

問題 King's Inspection | Aizu Online Judge解説 まずはアルファベットをずらしていくため、順番通りに並べた配列を用意します。 alp[]={'a' , 'b'..'z','A'....'Y','Z'} のような配列です。また、「いくつずらすか」を保存した配列は何周もする可能性があ…

AOJ-ICPC 「かけざん」

問題 Kakezan | Aizu Online Judge解説 値は文字列で管理するのが良いですね。 文字列長より1少ない数だけforを回して、文字列をstring::substr(開始位置, 何文字切り抜くか)で分割の仕方を全探索し、結果が最大になったものを次に持ち越す感じです。文字列…

ACM-ICPC 「ICPCの順位づけ」 解説

問題 ICPC Ranking | Aizu Online Judge解説 少し考えることが多いのですが、とりあえず ・tim: 各チームの所要時間を格納する1次元int配列 ・solve :各チームの各問題の解けたかどうかを格納する2次元bool配列 →solve[チーム番号][問題番号]=true or fals…

ACM-ICPC 「ICPC Score Totalizer Software」 解説

問題 ICPC Score Totalizer Software | Aizu Online Judge n個の数字が入力されるので、その中から最大値と最小値を除いたものの中での平均を求めよう。解説 n個の整数を全て足し合わせたsum、最小値を格納するmi、最大値を格納するmaを用意し、処理をします…

AOJ Numeral System 解説

問題 Numeral System | Aizu Online Judge解説方針としては、文字列を読み込んで、数字に直し、足し算した後で再びMCXI文字列に直します。まずは、読み込んだ文字列をどう処理するかを考えます。 まず、1000,100,10,1の時は、m,c,x,i の文字が単体で置かれま…

AOJ Amida, the City of Miracle 解説

問題 Amida, the City of Miracle | Aizu Online Judge 解説 あみだくじの問題です。 あみだくじ系の問題では、最初、i番目には番号iが繋がっていますが、横棒が追加されるたびに繋がる先が入れ替わると考えることができます。例えば最初、縦棒1 2 3 4 5には…

AOJ 列車の編成パート(Organize Your Train part II) 解説

問題 Organize Your Train part II | Aizu Online Judge 解説 文字列を2分割した後は以下の操作ができます。以下、分割した後の2つの文字列をA,Bとおきます。・A,Bはそれぞれ反転できる。 ・文字列を AB 、またはBA のどちらの順でも連結できる。これ以外…

AOJ 宇宙ヤシガニ(Space Coconut Grab) 解説

問題 Space Coconut Grab | Aizu Online Judge 解説 3つの変数をループで回して全探索すると、O(10^9)となってTLEします。 しかし、x+y*y+z*z*z=eになることから、y,zが分かればxが分かります。よってy,zを2重ループで回して、残りのxをx = e- y*y - z*z*z…